Functional-Dependency Theory RoadMap

We now consider the formal theory
that tells us which functional dependencies are implied logically
by a given set of functional dependencies.

뭔소리냐 이게..

We then develop algorithms to generate lossless decompositions into BCNF and 3NF

We then develop algorithms to test if a decomposition is dependency-preserving

Closure of a set of Functional Dependencies

• functional dependency set F가 있으면,
  그 안에 있는 애들로 imply할 수 있는 애들이 더 있다.
  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
• We denote $F^+$

그럼 F closure를 어떻게 구하냐 -> 3가지 rule이 있다.

Armstrong's Axioms

• Reflexive rule
  : if ß ⊂ å, then å -> ß
• Augmentation rule
  : if å -> ß, then 𝛄å -> 𝛄ß
• Transitivity rule
  : if å -> ß and ß -> 𝛄, then å -> 𝛄

• This rules are Sound and Complete
  • Sound
    : generate only functional dependencies that actually hold,
  • Complete
    : generate all functional dependencies that hold

Example

R = (A, B, C, G, H, I)
F = {A -> B
	 A -> C
     CG -> H
     CG -> I
     B -> H }

1). A -> H
 - by transitivity from A -> B and B -> H

2). AG -> I
 - by augmenting A -> C with G to get AG -> CG
 	then transitivity with CG -> I

3). CG -> HI
 - by augmenting CG -> I to infer CG -> CGI		// CG를 결합하기 때문에 좌변은 그대로 CG이다
 	and augmenting CG -> H to CGI -> HI
    and then transitivity, we get CG -> Hi

Additional Rules

• 핵심은 아닌데, 있으면 편하다. 더 빠르게 찾을 수 있다

• Union rule
  : If å->ß holds and å->𝛄 holds, then å->ß𝛄 holds.

• Decomposition rule
  : If å->ß𝛄 holds, then å–>ß holds and å–>𝛄 holds

• Pseudotransitivity rule
  : If å->ß holds and 𝛄ß->δ holds, then å𝛄->δ

Procedure for Computing 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

• 이론적으로 이 방식으로 F closure를 모두 구할 수 있지만, 시간적으로 매우 expensive하다.
  속성의 개수를 n개라고 하면, 속성의 집합의 개수는 $2^n$개가 되고,
  이들로 만들 수 있는 dependency의 개수는 $2^{2n}$이 된다.

• 결국, 이렇게 모든 걸 체크해야 하는 F+를 찾는 것은 별로 좋지 않다고 할 수 있다

---

Closure of Attribute Sets

• Given a set of attribute å, define the closure of å under F
  as the set of attributes that are functionally determined by å under F
• å에서 derive할 수 있는 모든 속성들.

• algorithm to compute å+

result = å;
while (changes to result) do
	for each ß -> 𝛄 in F do
    	begin
        	if ß in result
            then result = result ∪ 𝛄
        end

Example

R = (A, B, C, G, H, I)
F = {A -> B
	 A -> C
     CG -> H
     CG -> I
     B -> H }

(AG)+
1). result = AG
2). result = AGBC
3). result = AGBCHI

• Q. AG는 candidate key인가?

  1. AG가 super key인가?
     Yes. AG -> R. (== $(AG)^+$ ⊃ R)

  2. AG의 모든 subset이 superkey인가?
     No.

     • $A^+ = ABCH ( ≠ AGCGHI)$ -> A is Not superkey
     • $G^+ = G ( ≠ AGCGHI)$ -> G is Not superkey

• 이를 좀 더 일반화하면,
  Suppose that $(A1 A2 A3 ... An)^+$ = R.
  For all subset of size (n-1)에 대해 검사했을 때,
  모두 R을 줄 수 있어야 superkey라고 할 수 있다.
  만약 R을 주지 못하는 애가 있다면, 그걸 다시 쪼개서 검사한다.

Use of Attribute Closure

• There are several uses of the attribute closure algorithm :

1. superkey인지 확인하는 용도
   • å가 superkey인지 확인하기 위해 a+를 구해서,
     그게 R의 모든 attribute을 포함하고 있는지 본다

2. functional dependency를 테스트한다
   • å->ß가 hold하는지 확인하기 위해 (in other words, is in F+)
     ß ⊂ å+ 인지만 확인한다
   • 즉, a+를 계산하여 얘가 ß를 포함하고 있는지만 확인하면 된다
   • It is a simple and cheap test, and very useful

3. F의 closure를 구하는 다른 방법을 제공한다
   • For each 𝛄 ⊂ R, we find the closure 𝛄+,
     and for each S ⊂ 𝛄+, we output a functional dependency
     𝛄 -> S