Consider two sets of FD’s F1 and F2 over a relation scheme R. The two sets F1 and F2 are equivalent if the closure of F1 is equal to the closure of F2 i.e. F1 + = F2 +. The set F1 covers F2 and F2 covers F1 iff F1 and F2 are equivalent.
Importance of Cover: Sometimes closure of a set of FD’s F+ can be very large and difficult to compute. In that case the cover is used. It acts as a representative of the closure of F.
Example. Consider two sets of FDs, F and G,
F = {A –> B, B –> C, AC –> D} and
G = {A –> B, B –> C, A –> D}
Are F and G equivalent?
Sol. To determine their equivalence, we need to prove that F+ = G+. However, since computing F+ or G+ is computationally expensive, there is another method. Two sets of FDs, F and G are equivalent, if all FDs in F can be inferred from the set of FDs in G and vice versa.
To see if all FDs in F are inferred by G, compute attribute closure for attributes on the LHS of FDs in F using FDs in G:
A+ using G = ABCD; A –> A; A –> B; A –> C; A –> D;
B+ using G = BC; B –> B; B –> C;
AC+ using G = ABCD; AC –> A; AC –> B; AC –> C; AC –> D;
Thus, all FDs in F can be inferred using FDs in G.
To see if all FDs in G are inferred by F, compute attribute closure for attributes on the LHS of FDs in G using FDs in F:
A+ using F = ABCD; A –> A; A –> B; A –> C; A –> D;
B+ using F = BC; B –> B; B –> C;
Since all FDs in F can be obtained from G and vice versa, hence F and G are equivalent.
Example. Consider two sets of FDs, F and G,
F = {A –> B, A –>C}
G = {A –> B, B –> C}
Are F and G equivalent?
Sol. To check we, have
A+ using G = ABC;
Whereas, A+ using F = ABC; but B+ using F = B, indicating B –> C in G is not inferred using the FDs from F.
Hence, F and G are not equivalent, as B –> C in G is not inferred from the FDs in F.
1. Types of Cover:
The different types of cover are as follows:
- Redundant Cover: Consider a set of FD’s F1 over a relation schema R. Now if a proper subset F1‘ of F1 covers F1 , then we can say F1 is redundant cover.
- Non-redundant Cover: Consider two sets of FD’s F1 and F2 over a relation schema R. Suppose F1 covers F2 and no proper subset F1¢ of F1 covers F2. This set F1 is called the non-redundant cover.
To obtain a non-redundant cover, we have to remove some FD’s say X®Y from F1. The non-redundant cover so obtained is not unique and it is possible to obtain more than one non-redundant cover. A non-redundant cover with minimum number of FD’s is known as Minimal Cover.
- Canonical Cover: Before discussing the canonical cover Fc for the set of FD’s F, let us discuss some of the terms that are associated with canonical
Simple FD: A functional dependency X→A1A2A3………..An can be replaced by an equivalent set of FD’s X→A1, X→A2, X→A3…. X→An by using the axioms additivity and projectivity. An FD of the form X®Ai, where the right hand side has only one attribute is called a simple Fd. It is possible to replace every set of FD’s by an equivalent set of simple FD’s.
Example. Write an equivalent simple set of FD’s corresponding a set of FD’s F. F = { L→MN,L→O}
Sol. By additivity, L→MNO
By projectivity, L→M,L→N,L→O.
This is the required set of simple FD’s.
Extraneous Attributes: An attribute A of a FD α→β in F is said to be extraneous if it can be removed from F(set of FD’s) without changing its closure F+. An attribute A is extraneous if it satisfies the following conditions:
- A is extraneous in a if A ε α, and F logically implies (F–{α→β}) ∪ {(α–A) →β} i.e. first compute γ = α – {A} and check if γ→β can be derived from F. To do so, compute γ+ under F and if γ+ includes all attributes in β, then A is extraneous in α.
- A is extraneous in b if A e β and the set of functional dependencies (F – {α→β}) ∪ {α→(β–A} logically implies F.
i.e. first compute F’ where F’ = (F – {α→β}) ∪ {α→(β–A} and check if α→A can be derived from F+. To do so, compute a+ under F’ and if a+ includes A, then A is extraneous.
Example. Consider the set of FD’s F= { LM→N,L→N}. Determine the extraneous attributes.
Sol. Consider attribute M in FD LM→N
Now apply rule(i) to determine extraneous attributes.
Consider α→β, here α = LM and β = N
Compute γ = α – {M} so γ= LM – M = L
Compute γ+ over F, closure of L in LN
γ+ = LN, which includes all elements of β, then we can say that M is an extraneous attribute.
Example. Consider the set of FD’s F = {LM→NO,L→N}. Determine the extraneous attributes.
Sol. Consider attribute M in FD LM→NO
Now apply rule (ii) to determine extraneous attributes.
Consider α→β, here α = LM and β = NO
Now Compute F’ = (F – {α→β}) ∪ {α→(β–N)}
({LM→NO, L→N}– {LM → NO}) ∪ {LM → (NO–N)}
(L→N) ∪ {LM→O}
{L→N, LM→O}
Now compute a+ under F’, closure of LM under F’ is LMNO which includes N, so N is extraneous in right side of FD, LM→NO.
2. Identifying Redundant Functional Dependencies
Given a set of functional dependencies F. An FD in F is redundant if it can be derived from the other FD’s in the set F i.e. FD X→A is redundant if {F – (X→A)} logically implies F. The obtained set of FD’s F’ is smaller but equivalent set of FDs F. Following are the steps to remove redundant FD’s.
Algorithm: To determine the redundant FD in a set of FD’s
Input: Given a relation with a set of FD’s F.
Output: Non-redundant set of FDs equivalent to the original set
Step 1. For every FD X→A in F do
Step 2. Remove X→A from F, and call the resultant FD’s, (i.e. F′= {– (X→A)})
Step 3. Compute X+ under F’.
Step 4. If A ε X+, then X®A is redundant. Rename F as F’.
We could remove the FD X®A from the set, since it can be derived from the other FDs. By testing every FD in the set in turn and removing any that can be derived from the others, then repeating this process with the remaining FDs we can find a non-redundant set of FDs equivalent to the original set.
Example. Remove any redundant FD’s from the following set of FD’s F:
- D → C
- D → B
- BC → A
- DC → B
Sol. Try for FD (1), D → C. Remove it to obtain F’. Now F′= {D → B, BC → A, DC → B}. Further, compute the closure of D i.e. D+ under F’. The closure of D is DB. Since C does not belong to D+, hence D → C is not redundant FD.
Try for FD (2), D → B. Remove it to obtain F’. Now F′= {D → C, BC → A, DC →B}. Again, compute the closure of D i.e. D+ under F’. The closure of D is ABCD. Since B belongs to D+, hence D → B is redundant FD.
Try for FD (3), BC → A. Remove it to obtain F’. Now F′ = {D → C, DC → B}.. Compute the closure of BC i.e. BC+ under F’. The closure of BC is BC. Since A does not belong to BC+, hence BC → A is not redundant FD.
Finally, try for FD (4), DC → B. Remove it to obtain F’. Now F′ = {D → C, BC → A}. Compute the closure of DC i.e. DC+ under F’ The closure of DC is DC. Since B does not belong to DC+, hence DC → B is not redundant FD.
The final set of FDs is
F = {D → C, BC→ A, DC → B}
Example. Remove any redundant FD’s from the following set of FD’s F: F = {A→B, B→C, AD→C}
Sol. Simplifying the FD’s of F as using axioms, we get F = {A→B, B→C, A→C, D→C}
Now apply the algorithm, we have the final set of FDs F = {A→B, B→C, D→C}
Definition of Canonical Cover: A cover Fc for a set of FD’s F is known as canonical cover for F if F logically implies all dependencies in Fc, and Fc logically implies all dependencies in F. The canonical cover Fc must also satisfy the following properties:
- No FD in Fc contains an extraneous attributes.
- Each left side of a FD in Fc is unique, it means no FD, X→A is redundant e. there are no two dependencies α1→β1 and α2→β2 in Fc with α1→β2.
Algorithm: To find the canonical cover Fc for F
Input: Given a relation with a set of FD’s F.
Output: Canonical cover Fc for F
Step 1. Fc = F
Step 2. Repeat
Step 3. Decompose all FD’s in simple form i.e. replace each FD X→A1A2A3……………. An in F with X→A1, X→A2, X→A3…. X→An.
Step 4. Eliminate extraneous attributes from LHS
Step 5. Remove all redundant FD’s.
Step 6. Make LHS of FD’s unique i.e. Replace X→A1, X→A2, X→A3…. X→An with X→A1, X→A2, X→A3…. X→An..
Step 7. Until Fc does not change.
Example. Consider a set of functional dependencies F = {A→C, CD→B, C→E, A→E}.
Compute the canonical cover Fc for F.
Sol. Following the steps of algorithm to compute canonical cover Fc = F. We have Fc = {A→C, CD→B, C→E, A→E}
Since all the FD’s are in simple form so skip step 3.
Now eliminate all extraneous attributes from the LHS of FD’s : Consider the FD, CD®B
Take attribute C in FD, CD→B
Comparing with (α→β), we have α = CD and β = B
Now compute, γ = α – {C} so γ = CD – C = D. Further, compute γ+ over Fc, closure of D is DB. Since γ+ = DB, which includes all elements of β , then we can sat that C is an extraneous attribute in FD, C→DB.
Eliminate C from C→DB
Thus we have, Fc = {A→C, D→B, C→E, A→E}
Now eliminate all redundant FD’s from Fc.
Consider FD, A→E in Fc, remove it. Fc’ = {A→C, D→B, C→E}. Now compute closure of A i.e. A+ under Fc’. The closure of A is ACE. Since E belongs to A+, hence A→E is a redundant FD.
Similarly, you can check for other FD’s after renaming Fc¢ to Fc and repeating the above process. Since there are no more changes in Fc. We reached at the solution. Hence the final solution is Fc = {A→C, D→B, C→E}..
3. Covers and Equivalent Sets of FDs
If F and G are two sets of FDs for some relation R, then F is a cover for G if every FD in G is also in F+. This means that every FD in G can be derived from the FDs in F, or that G+ is a subset of F+. To prove that F is a cover for G, we examine each FD X→Y in G. We then calculate X+ in F and demonstrate that X+ contains the attributes of Y. If this holds true for all the FDs in G, then F is a cover for G. For a relation R, two sets of FDs, F and G, are said to be equivalent if and only if F is a cover for G and G is also a cover for F, (i.e. F+ = G+). To prove equivalence, we prove F and G are covers for each other.
If G is a set of FDs in R, and G is large, we would like to be able to find a smaller set of FDs such that all the FDs in G are also implied by that smaller set, i.e. that the smaller set is a cover for G.
4. Minimal Set of Functional Dependencies
A set of FDs, F, is said to be minimal if it satisfies these conditions
- the right side of every FD in F has a single This form is called standard or canonical form for FDs.
- no attribute on the left side of any FD in F is extraneous. This means that if X → Y is an FD in F then there is no proper subset S of X such that S → Y can be used in place of X →Y and the resulting set is equivalent to F.
- F has no redundant
5. Finding a Minimal Cover for a Set of FDs
A cover, F, for G, is said to be a minimal cover (also called a nonredundant cover) if F is a cover for G but no proper subset of F is a cover for G. A set of FDs may have several minimal covers, but we can always find one of them. To do so, we begin with the set of FDs, G. We express each FD in G in canonical form, i.e. with one attribute on the right side. Then we examine the left side of each FD, checking each attribute on the left side to see if deleting it does not effect G+. If the deletion of A has no effect, we delete it from the left side. This eliminates extraneous attributes from all the FDs. Next we examine each remaining FD and check to see if it is redundant, i.e. if deleting it has no effect on G+. If it is redundant, we eliminate it. The final set of FDs, which we will call F, is irreducible and equivalent to the original set. The algorithm follows.
Algorithm: To find a minimal cover, F, for a given set of FDs, G.
Input: Given a relation R and a set of functional dependencies, G, on R,
Output: A minimal cover, F, for a given set of FDs G of R
- Set F ← G;
- For each FD in F that is not in canonical form, e. not of the form X→{Y1, Y2, …Yn}, replace it by the n FDs X→Y1, X→Y2,…X→Yn;
- For each FD X→Y in F
for each attribute A that is an element of X
if ((F–{X→Y}) ∪ {(X – {A})→ Y} is equivalent to F
then replace X → Y with {X – {B}) → Y in F;
- For each remaining FD X®Y in F
If (F–{X→Y}) is equivalent to F
Then remove X→Y from F
Example. Let R = ABCDFE, and F = {ABD → AC, C → BE, AD → BF, B → E}. Find a minimal cover of F.
Sol.
Step 1. H = F=F={ABD → A, ABD → C, C → B, C → E, AD → B,AD → F, B → E}
Step 2. ABD → A is not essential.
- How about ABD → C? It cannot be derived from other FDs using set closure rule.
- How about C → B? Can it be implied by other FDs? Compute C+={CE}. Since, C* does not contain B, C ®B is
- C →E is inessential
- Compute (AD)+=(ADF), so AD → B is How about AD →F? No FD has F on left hand side. So this is essential.
- Also, B →E is essential.
H = {ABD → C, C → B, C →E, AD → B, AD →F, B →E}
Step 3. Can we drop A in ABD →C?
The new set J={BD → C, C → B, C →E, AD →B, AD →F, B → E}
Is J=H? Yes iff (BD)+ under H = BD+ under J.
BDE is not equal BDC. So we cannot drop A.
Proceed on this line and repeat step 2.
H={AD →C, C →B, AD →F, B → E}
Step 4. The minimal cover of F is H={AD →CF, C → B, B →E}
Example. Let R = R(ABCDEGH) and F = {CD → AB, C → D, D → EH, AE → C, A → C, B → D}. Find a minimal cover of F.
Sol. The process of computing a minimal cover of F is as follows:
Step 1. Break down the right hand side of each FD’s. After performing step (1) in the algorithm, we get F′ ={CD → A, CD→ B, C → D, D → E, D → H, AE → C, A → C, B → D}.
Step 2. Eliminate redundancy in the left hand side. The fd CD→ A is replaced by C → A. This is because C→ D ∈ (F’)+, hence C → CD ∈ (F’)+;from C → CD (F′)+, hence C → CD ∈ (F′)+;from C → CD ∈ (F′)+ and CD →A ∈ F′, by transitivity, we have C → A ∈ (F′)+ and hence CD → A should be replaced by C → A. Similarly, CD → B is replaced by C → B, AE → C is replaced by A → C. F′ ={C → A, C → B, C → D, D → E, D →H, A → C, B → D} after step (2).
Step 3. Remove redundant FD’s. The FD C → D is eliminated because it can be derived from C → B and B → D and hence it is redundant. The F′ now becomes {C →A, C → B, D →E, D → H, A → C, B → D}, which is the only minimal cover of F.
Example. Let R = R(ABCDEG) and F ={AB → C, C → A, BC → D, ACD → B, D →G, BE→ C, CG→BD, CE→ AG }.. Find the minimal covers of F.
Sol. Try yourself.
The two minimal covers are H = {AB → C, C → A, BC → D, CD → B, D → E, D → G, BE → C, CG → D, CE → G} and H = {AB → C, C → A, BC → D, D → E, D → G, BE → C, CG → B, CE → G}
Example. Find a minimal cover of F = {AB→D, B→C, AE→B, A→D, D→EF}
Step 1. Make right hand sides atomic
G = {AB→D, B→C, AE→B, A→D, D→E, D→F}
Step 2. Remove any redundant FDs
For AB→D compute AB+ under (G – (AB→D))
AB+ = ABCDEF
D in AB+ so remove AB→D from G
G = {B→C, AE→B, A→D, D→E, D→F}
For B→C compute B+ under (G – (B→C))
B+ = B, C not in B+ so G = {B→C, AE→B, A→D, D→E, D→F}
For AE→B compute AE+ under (G – (AE→B))
AE+ = AEDF , B not in AE+ so G = {B→C, AE→B, A→D, D→E, D→F}
For A→D compute A+ under (G – (A→D))
A+ = A, D not in A+ so G = {B→C, AE→B, A→D, D→E, D→F}
For D→E compute D+ under (G – (D→E))
D+ = DF, E not in D+ so G = {B→C, AE→B, A→D, D→E, D→F}
For D→F compute D+ under (G – (D→F))
D+ = DE, F not in D+ so G = {B→C, AE→B, A→D, D→E, D→F}
Step 3. Remove any redundant left hand side attributes
G = {B→C, AE→B, A→D, D→E, D→F}
For AE→B
For A: compute E+ with respect to (G–(AE→B) ∪ (E→B))
E+ w.r.t. {B→C, E→B, A→D, D→E, D→F} = EBC
E+ doesn’t contain A, so A is not redundant in AE→B
For E: compute A+ with respect to (G–(AE→B) ∪ (A→B))
A+ w.r.t. {B→C, A→B, A→D, D→E, D→F} = ABDEFC
A+ contains E, so E is redundant in AE→B.
Minimal Cover of F = {B→C, A→B, A→D, D→E, D→F}
Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)