For a given application, we can define many different sets of fds with the same closure (e.g. F and G where F+ = G+)
Minimal cover Fc for a set F of fds:
- Fc is equivalent to F
- all fds have the form X →A (where A is a single attribute)
- it is not possible to make Fc smaller
- either by deleting an fd
- or by deleting an attribute from an fd
An fd d is redundant if (F-{d})+ = F+
An attribute A is redundant if
(F−{d}∪{d'})+=F+(F−{d}∪{d'})+=F+ size 12{ \( F - lbrace d rbrace union lbrace d' rbrace \) rSup { size 8{+{}} } =F rSup { size 8{+{}} } } {} (where d' is the same as d but with attribute A removed)
Algorithm for computing minimal cover:
Inputs: set F of fds
Output: minimal cover Fc of F
Fc = F
Step 1: put fds into canonical form
for each f
in
Fc like X
->
{A1,..,An}
Fc = Fc - {f}
for each a in {A1,..,An}
Fc = Fc
union
{X
->
a}
end
end
Step 2: eliminate redundant attributes
for each f
in
Fc like X → A
for each b in X
f' = (X-{b})
->
A;
G = Fc - {f}
Union
{f'}
if (G+ == Fc+) Fc = G
end
end
Step 3: eliminate redundant functional dependencies
for each f
in
Fc
G = Fc - {f}
if (G+ == Fc+) Fc = G
end
Example : R = ABC, F = { A →BC, B →C, A →B, AB →C }
Compute the minimal cover:
- canonical fds: A →B, A →C, B →C, AB →C
- redundant attrs: A →B, A →C, B →C, AB →C
- redundant fds: A →B, A →C, B →C
This gives the minimal cover
FC={A→B,B→C}FC={A→B,B→C} size 12{F rSub { size 8{C} } = lbrace A rightarrow B,B rightarrow C rbrace } {}.
Example: Let consider the relation schema R(ABCDEG) and a set of functional dependencies F = {AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG }. Find the minimal cover of F
Canonical fds: F1 = {AB → C, C → A, BC → D, ACD → B, D → E, D → G, BE → C, CG → B, CG → D, CE → A, CE → G }
Find redundant attributes:
Consider fd: ACD → B, we have (CD)+ = ABCDEG it means CD → B . A is a redundant attribute in that functional dependency.
No other redundant attributes found. So we have
F2 = {AB → C, C → A, BC → D, CD → B, D → E, D → G, BE → C, CG → B, CG → D, CE → A, CE → G }
Find redundant functional dependency.
- Initially F0 = F2
- Consider first fd in F : AB → C . With respect to the set F0 \ {AB →C}, we have (AB)+ = AB. So the fd AB → C cannot be inferred from others fds in the set F0 or F0 is not equivalent to F0 \ {AB → C}. Therefore, we can have F1 = F0or the functional dependency AB → C is not redundant.
- C → A is not redundant or F2 = F1 because (C)+ = C with respect to the set F1 \ {C → A}
- BC → D is not redundant or F3 = F2 because (BC)+ = ABC with respect to the set F2 \ {BC → D}.
- CD → B is a redundant functional dependency because (CD)+ = ABCDEG with respect to the set F3 \ {CD → B}. The closure of CD contains attribute B so that CD → B can be inferred from remaining dependencies in the set . Therefore, F4 = F3 \ {CD → B}.
- Similarly, the following functional dependencies are redundant: CG → D, CE → A
Finally, the result of this step is F3 = {AB → C, C → A, BC → D, D → E, D → G, BE → C, CG → B, CE → G }
This is the minimal cover of F.
