DBMS Canonical cover

DBMS

1. Closure of an Attribute Set

2. Closure of an attribute set
Given a set of attributes A and a set of FDs F, closure of A under F is
the set of all attributes implied by A
In other words, the largest B such that:
 A  B
Redefining super keys:
 The closure of a super key is the entire relation schema
Redefining candidate keys:
1. It is a super key
2. No subset of it is a super key

3. Computing the closure for A
Simple algorithm
1. Start with B = A.
2. Go over all functional dependencies, b ® g , in F
+
3. If b Í B, then
 Add g to B
4. Repeat till B changes

4. 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 = ABCG(A ® C and A ® B)
3.result = ABCGH(CG ® H and CG Í AGBC)
4.result = ABCGHI(CG ® I and CG Í AGBCH
Is (AG) a candidate key ?
 1. It is a super key.
 2. (A+) = BC, (G+) = G.
 YES.

5. Uses of attribute set closures
Determining superkeys and candidate keys
Determining if A  B is a valid FD
Check if A+ contains B
Can be used to compute F+

6. Computing Canonical Cover

7. Canonical Cover
A canonical cover for F is a set of dependencies F
c
such that
F logically implies all dependencies in F
c,
and
F
c
logically implies all dependencies in F, and
No functional dependency in F
c
contains an extraneous
attribute, and
Each left side of functional dependency in F
c
is unique
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

8. Extraneous Attributes
Consider F, and a functional dependency, A  B.
“Extraneous”: Are there any attributes in A or B that can be
safely removed ?
Without changing the constraints implied by F

9. Testing if an Attribute is Extraneous
Consider a set F of functional dependencies and the
functional dependency a ® b in F.
To test if attribute A Î a is extraneous in a
1.compute ({a} – A)
+
using the dependencies in F
2. check that ({a} – A)
+
contains A; if it does, A is extraneous
To test if attribute A Î b is extraneous in b
1.compute a
+
using only the dependencies in
F’ = (F – {a ® b}) È {a ®(b – A)},
2. check that a
+
contains A; if it does, A is extraneous

10. Example1: 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
The canonical cover is: A ® B
B ® C

11. Example2: Computing a Canonical Cover
Given F = {A ® C, AB ® C }
B is extraneous in AB ® C because {A ® C, AB ® C} is
equivalent to {A ® C, A ® C } = {A ® C}
Given F = {A ® C, AB ® CD}
C is extraneous in AB ® CD because {A ® C, AB ® CD} is
equivalent to {A ® C, AB ® D}