We now consider the formal theory that tells us which functional dependencies are implied logically by a given set of functional dependencies.
formal = 공식적인
formal theory 고려할건데 어떤 functional dependency에서 logical(ex: 이행적 함수종속)하게 적용되는지?
We then develop algorithms to generate lossless decompositions into BCNF and 3NF
We then develop algorithms to test if a decomposition is dependency-preserving
클로저
많이 쓰인다.
Given a set F set of functional dependencies, there are certain other functional dependencies that are logically implied by F.
For e.g.: If A -> B and B -> C, then we can infer that A -> C
The set of all functional dependencies logically implied by F is the closure of F.
closer of F라고 읽는다.
We denote the closure of F by F+.
F+라고 표기함.
We can find F+, the closure of F, by repeatedly applying
Armstrong’s Axioms:
if , then (reflexivity)
if , then (augmentation)
if , and , then (transitivity)
These rules are
sound (generate only functional dependencies that actually hold), and
complete (generate all functional dependencies that hold).
sound : (알고리즘 등에서 형용사로 쓰일 시)경고하다로 쓰임
해당 rule들로 확장 시 F가 나타내지 않는 functional dependency는 적용하지 않는다.
F가 가지는 모든 functional dependency를 적용할 수 있다
Example
R = (A, B, C, G, H, I)
F = {A B, A C, CG H, CG I, B H}
some members of F+
A H
by transitivity from A B and B H
AG I
by augmenting A C with G, to get AG CG
and then transitivity with CG I
CG HI
by augmenting CG I to infer CG CGI,
and augmenting of CG H to infer CGI HI,
and then transitivity from CG CGI and CGI HI
Procedure for Computing F+
To compute the closure of a set of functional dependencies F:
F + = F
repeat
for each functional dependency f in F+
apply reflexivity and augmentation rules on f
add the resulting functional dependencies to F +
for each pair of functional dependencies f1 and f2 in F +
if f1 and f2 can be combined using transitivity
then add the resulting functional dependency to F +
until F + does not change any further
reflexivity and augmentation rule을 이용해 확장 후, 모든 functional dependency fair(확장 된 dependency도 포함)에 대해 transitivity가 존재하는 지 확인
확인할 수 없을 때까지 반복한다.
Additional rules:
If and , then (union)
and =>
If , then and (decomposition)
=> and =>
If and , then (pseudo-transitivity)
=>
The above rules can be inferred from Armstrong’s axioms.
Armstrong's axioms 즉, 클로저 만드는 과정에서 전부 커버되는 rule들이다.
실제 정규화 과정에서는 Closure of Attribute Set이 많이 쓰인다.
Closure of Attribute Sets
Given a set of attributes a, define the closure of a under F (denoted by a+) as the set of attributes that are functionally determined by a under F
Algorithm to compute a+, the closure of a under F
result := a; (-> 수도코드에서 := 는 대입연산자)
while (changes to result) do (확장이 없을 경우 중지)
for each in F do
begin
if result then result := result
end
a -> b가 있을 경우 b의 함수 종속을 a에 추가하는 것임.
F에 기반한 클로저 a는 주어진 F에 대해 a에 의해 결정될 수 있는 속성 집합을 정의할 수 있다.
-> 수정해라
Example of Attribute Set Closure
R = (A, B, C, G, H, I)
F = {A B, A C, CG H, CG I, B H}
(AG)+
1. result = AG
2. result = ABCG (A C and A B, A AG)
3. result = ABCGH (CG H, CG ABCG)
4. result = ABCGHI (CG I, CG ABCGH)
Is AG a candidate key?
Is AG a super key?
Does AG R? => is (AG)+ R
Is any subset of AG a superkey?
Does A R? => is (A)+ R
Does G R? => is (G)+ R
실제로는 이렇게 복잡하지 않다. 전부 비슷한 정보를 가지고 있기 때문에 상식만으로 테이블 구성가능.
BCNF 할때
모든 functional dependency 찾기
후보키 만들고 포함되는지 확인 or 후보키인지 전부 확인하기
lossless composition 시 functional dependency도 보존해야하는 걸 잊지 말자....
ER 다이어그램으로 테이블 만들기 가능. anomally가 생길 수 있기 때문에 정규화 진행?
Uses of Attribute Closure
There are several uses of the attribute closure algorithm:
Testing for superkey:
To test if is a superkey, we compute +, and check if + contains all attributes of R.
Testing functional dependencies
To check if a functional dependency holds (or, in other words, is in F+), just check if +.
That is, we compute + by using attribute closure, and then check if it contains .
Computing closure of F
For each R, we find the closure +, and for each S +, we output a functional dependency S.
Is a simple and cheap computation, and very useful (-> 함수종속 클로저 < 속성 클로저 효과적)
Canonical Cover
Sets of functional dependencies may have redundant dependencies that can be inferred from the others
For example: A C is redundant in: {A B, B C, A C}
Parts of a functional dependency may be redundant
E.g.: on RHS: {A B, B C, A CD} can be simplified to
{A B, B C, A D}
E.g.: on LHS: {A B, B C, AC D} can be simplified to
{A B, B C, A D}
Intuitively, a canonical cover of F is a “minimal” set of functional dependencies equivalent to F, having no redundant dependencies or redundant parts of dependencies
functional defendency를 최소한의 집합으로 표현하는 것을 canonical cover라고 함.
RHS : right handle side
LHS : left handle side
Extraneous Attributes
Consider a set F of functional dependencies and the functional dependency in F.
Attribute A is extraneous in if A
and F logically implies (F – { }) {( – A) }.
Attribute A is extraneous in if A
and the set of functional dependencies in
(F – { }) { ( – A)} logically implies F.
Example: Given F = {A C, AB C }
B is extraneous in AB C because {A C, AB C} logically implies A C (I.e. the result of dropping B from AB C).
Example: Given F = {A C, AB CD}
C is extraneous in AB CD since AB C can be inferred even after deleting C
Testing if an Attribute is Extraneous
Consider a set F of functional dependencies and the functional dependency in F.
(F는 함수 종속의 집합이니 주의)
To test if attribute A is extraneous in
compute ({} – A)+ using the dependencies in F
check that ({} – A)+ contains ; if it does, A is extraneous in
To test if attribute A is extraneous in
compute + using only the dependencies in
F’ = (F – { }) { ( – A)},
check that + contains A; if it does, A is extraneous in
Canonical Cover
A canonical cover for F is a set of dependencies Fc such that
F logically implies all dependencies in Fc, and
Fc logically implies all dependencies in F, and
No functional dependency in Fc contains an extraneous attribute, and
Each left side of functional dependency in Fc is unique.
To compute a canonical cover for Fc :
repeat
Use the union rule to replace any dependencies in Fc
1 1 and 1 2 with 1 1 2
Find a functional dependency with an
extraneous attribute either in or in
If an extraneous attribute is found, delete it from
until Fc does not change
Note: Union rule may become applicable after some extraneous attributes have been deleted, so it has to be re-applied
Computing a Canonical Cover
R = (A, B, C)
F = {A BC, B C, A B, AB C}
Combine A BC and A B into A BC
Set is now {A BC, B C, AB C}
A is extraneous in AB C
Check if the result of deleting A from AB C is implied by the other dependencies
Yes: in fact, B C is already present!
Set is now {A BC, B C}
C is extraneous in A BC
Check if A C is logically implied by A B and the other dependencies
Yes: using transitivity on A B and B C.
Can use attribute closure of A in more complex cases
Thus, the final canonical cover is: {A B, B C}
