Canonical Cover

(Eng ver.)
Suppose that we have a set of functinoal dependencies F on a relation schema. Whenever a user performs an update(insert, delete, ...) on the relation, the database system must ensure that the update does not violate any functional dependencies; that is, all the functional dependencies in F are satisfied in the new database state.

(필기 ver.)
F로부터 derived된 것들을 모두 모아둔 F closure를 구하는 것이 아니라
F를 minimal한 set으로 만들어 보자. F의 원소들 중에서, 다른 것으로부터 derive되는 게 있으면 제거시켜라.
가장 simple한 핵심적인 dependency들만 남긴다
매번 업데이트를 할 때마다 functional dependency를 만족하는지 체크한다
근데 이걸 체크해야 하는 게 많아지면, 시간적으로 오래걸린다.
결국, 핵심은 남겨두고 불필요한 dependency를 제거하는 것이 유리하다

• 이 simplified set을 canonical cover라고 부른다

• canonical cover를 정의하기 위해서는 우선 extraneous attribute을 먼저 정의해야 한다

• An attribute of a functional dependency in F is extraneous if we can remove it without changing F+

---

Extraneous Attribute

Removing left side

• functional dependency에서 left side의 속성을 제거하는 것은
  이것을 stronger constraint로 만든다

  • AB -> C

  • A -> C

  • 이 두 dependency를 비교해보면,
    전자는 A B 2개로 C를 determine하지만 후자는 A 하나로 C를 determine한다.
    후자가 true라면 전자는 true이지만, 전자가 true라고 해서 후자가 true일 필요는 없다.

  • 이 때 두 dependency가 모두 true라면,
    B가 extraneous하다고 할 수 있고, A->C가 더 strong하다고 할 수 있다.

  • A -> C logically implies AB -> C

Removing right side

• functional dependency에서 right side의 속성을 제거하는 것은
  이것을 weaker constraint로 만든다

  • AB -> CD

  • AB -> D

  • 전자의 dependency는 C, D를 결정하지만,
    후자의 dependency는 D만 결정한다

• Example)
  F = {AB -> CD, A -> C}

  • AB -> CD에서 AB -> D를 끄집어내고 이를 A -> C와 결합하면
    AB -> CD를 만들 수 있다.
    -> 즉, C is extraneous

  • 같은 방식으로 AB -> C를 끄집어낸다 해도,
    여기서 AB -> CD를 만들 수가 없기 때문에
    -> D is NOT extraneous

Summary

• F에 있는 functional dependency의 속성들 중 F+로 바꾸지 않고도 제거할 수 있는 속성들을 extraneous하다고 한다

• Consider a functional dependency å -> ß

  Remove from the left side

  Attribute A is extraneous in å if

  • A ∈ å
  • F logically implies (F - {å->ß}) ∪ {(å - A) -> ß}

  여기서 F가 weak, 뒤에 있는게 strong하다고 할 수 있다.
  뒤에 있는 건 속성 관점에서 weak한 걸(å–>ß) 빼고 strong한 걸(å–>ß의 simplified 버전) 추가한 것이다.

  Remove from the right side

  Attribute A is extraneous in ß if

  • A ∈ ß
  • (F - {å->ß}) ∪ (å->(ß-A)} logically implies F

• 논리적으로, strong한 게 weak한 걸 imply하는 건 당연하다
  위의 조건들처럼 weak한 게 strong한 걸 imply하는 경우는 extraneous가 있는 case라고 이해하면 된다.

---

Testing Extraneous

Consider å->ß

• Test if attribute A ∈ ß is extraneous in ß (right side)

  • Consider the set
    $F^{'}$ = (F - {å–>ß}) ∪ (å-> (ß - A)}

  • 계산한 F'에서, a+가 A를 포함하는지 확인한다.
    만약 포함하고 있으면, A is extraneous in ß

• Test if attribute A ∈ å is extraneous in å (left side)
  • Let 𝛄 = å - {A}.
    Check if 𝛄 -> ß can be inferred from F
  • F에서 𝛄+를 구한다
  • 구한 𝛄+가 ß의 모든 속성을 포함하고 있으면,
    A가 없어도 ß를 다 derive할 수 있다는 의미이므로
    A is extraneous in å

Example

F = {AB -> CD, A -> E, E -> C}일 때,

C가 AB -> CD에서 extraneous한 지 확인해보자

• 일단 right side case이므로 F'을 만든다
  F' = {AB->D, A->E, E->C}
• F'에서, (AB)+를 구한다
  (AB)+ = ABDEC
• (AB)+가 C를 포함하고 있는 것을 확인할 수 있다
  C is extraneous in AB -> CD

D가 AB -> CD에서 extraneous한 지 확인해보자

• 마찬가지로 F'을 구한다
  F' = {AB->C, A->E, E->C}
• F'에서, (AB)+를 구한다
  (AB)+ = ABCE
• (AB)+가 D를 포함하지 않고 있다는 것을 확인할 수 있다
  D is NOT extraneous in AB -> CD

A가 AB -> CD에서 extraneous한 지 확인해보자

• left side case이므로 𝛄를 만든다
  𝛄 = B
• F에서 𝛄+를 구한다
  𝛄+ = (B)+ = B
• CD를 포함하고 있지 않다는 것을 확인할 수 있다
  A is NOT extraneous in AB -> CD

---

Canonical Cover

canonical cover for F is a set of dependencies Fc such that

• F logically implies all dependencies in Fc

• Fc logically implies all dependencies in F

• No functional dependency in Fc contains an extraneous attribute

• Each left side of functional dependency in F is unique

  • å1 -> ß1 과 å2 -> ß2가 있으면, å1 ≠ å2 이어야 한다
  • (a->c, a->b 이렇게 있으면 a->cb로 합쳐라)

Fc = F		// 초기값
repeat
	Use the union rule to replace any dependencies in Fc of the form
    	å1 -> ß1 and å1 -> ß2 with å1 -> ß1ß2
    
    Find a functional dependency å -> ß in Fc with an extraneous attribute either in å or in ß
    (test for Fc, not F)
    If an extraneous attribute is found, delete it from å -> ß

until (Fc not change)

• union rule은 extraneous attribute가 제거된 후에 다시 applicable될 수 있다.

Example 1

R = (A, B, C)
F = { A->BC, B->C, A->B, AB->C }

1. Combine A->BC and A->B
=> A->BC
=> Fc = { A->BC, B->C, AB->C }

2. A is extraneous in AB->C
- left side case이다
- 𝛄 = B, 𝛄+ = (B)+ = BC
- C를 포함하고 있으므로 A is extraneous
=> Fc = { A->BC, B->C, B->C} = { A->BC, B->C }

3. C is extraneous in A->BC
- right side case이다
- F' = { A->B, B->C}
- A+ = ABC
- C를 포함하고 있으므로 C is extraneous
=> Fc = { A->B, B->C }

[3. 다른 방법]
F' = { A->B, B->C}에서, A->C is logically implied by transivity
So C는 없어도 된다

The canonical cover is {A -> B, B -> C}

Example 2

R = (A, B, C, D)
F = {A->BC, B->C, A->B, AB->C, AC->D}

1. Combine A->BC and A->B
=> A->BC
=> Fc = { A->BC, B->C, AB->C, AC->D }

2. C is extraneous in A->BC
- right side case
- F' = { A->B, B->C, AB->C, AC->D }
- A+ = ABCD
- C 포함하고 있으므로 C is extraneous
=> Fc = { A->B, B->C, AB->C, AC->D }

3. C is extraneous in AB->C
- right side case
- F' = { A->B, B->C, AC->D }
/////////////(주의)////////////
- (AB)+ = ABCD
/////////////(주의)////////////
- C 포함하고 있으므로 C is extraneous
=> Fc = { A->B, B->C, AC->D }

4. C is extraneous in AC->D
- left side case
- 𝛄 = A. (A)+ = ABCD
- D 포함하고 있으므로 C is extraneous
=> Fc = { A->B, B->C, A->D }

5. Combine A->B and A->D
=> A->BC
=> Fc = { A->BD, B->C }

The canonical cover = { A->BD, B->C }

---

Dependency Preservation

• Let $F_i$ be the set of dependencies that include only attributes in $R_i$.
  ($R_i$의 속성으로만 구성된 functional dependency들을 의미한다)

• A decomposition is dependency preserving if
  (F1 ∪ F2 ∪ ... ∪ Fn)+ = F+

• 위의 정의를 이용하면, testing for dependency preservation은 exponential time이 필요하다

• 만약 decomposition이 NOT dependency preserving하다면,
  functional dependency의 violation을 check하는 데
  join이 필요하고, 이건 되게 비싸다.

  ---

• The restriction of F to $R_i$ is the set $F_i$
  of all functional dependencies in F+
  that include only attribute of $R_i$

• restriction에 있는 모든 functional dependency는 one relation schema에 있는 속성들만 포함하고 있으므로,
  하나의 relation으로만 그 dependency를 check하는게 가능하다

• 주의해야 할 점은, restriction의 정의는 F+를 사용하는 것이다.
  F를 사용한다고 착각하지 말자

  ---

Testing dependency preservation

To check if a dependency å->ß is preserved in a decomposition of R into R1, ... Rn

result = å		// 초기값 (å는 속성의 집합이다)
repeat
	for each Ri in the decomposition
    	t = (result ∩ Ri)+ ∩ Ri
        result = result ∪ t

until (result does not change)

결과적으로 result가 ß의 모든 속성을 포함하고 있으면, å–>ß is preserved

이 과정은 polynomial time이 걸린다.
만약 F+와 (F1 ∪ F2 ∪ ... ∪ Fn)+를 계산하려면 exponential time이 걸릴 것이다

Example

R = (A, B, C)
F = { A->B, B->C }
Key = {A}

일단, R은 BCNF가 아니다 (B가 superkey가 아니기 때문이다)

그래서 R1 = (A, B), R2 = (B, C)로 decompose 하였다

1. R1과 R2는 BCNF이다

2. Lossless-join decomposition이다

3. dependency preserving하다


F = {A->B, B->C, A->C } 일 때, A->C가 preserved 되는지 check하여라

	1. result = {A}
    	R1 : t = (A)+ ∩ (A, B)
        	   = AB
             result = AB
        R2 : t = (AB)+ ∩ (B, C)
        	   = BC
             result = ABC
    
    2. result = {A, B, C}
    	R1 : NOT change
    
    result include C
    => A->C is preserved