Assume that F is a set of functional dependencies for a relation R. The closure of F, denoted by F+ , is the set of all functional dependencies obtained logically implied by F i.e., F+ is the set of FD’s that can be derived from F. Furthermore, the F+ is the smallest set of FD’s such that F+ is superset of F and no FD can be derived from F by using the axioms that are not contained in F+.
If we have identified all the functional dependencies in a relation then we can easily identify superkeys, candidate keys, and other determinants necessary for normalization.
Algorithm: To compute F+, the closure of FD’s
Input: Given a relation with a set of FD’s F.
Output: The closure of a set of FD’s F.
Step 1. Initialize F+ = F // F is the set of given FD’s
Step 2. While (changes to F+) do
Step 3. For each functional dependency f in F+
Apply Reflexivity and augmentation axioms on f and add the resulting functional dependencies to F+.
Step 4. For each pair of functional dependencies f 1 and f 2 in F+
Apply transitivity axiom on f 1 and f 2
If f 1 and f 2 can be combined add the resulting FD to F+.
Step 5. For each functional dependencies to F+
Apply Union and Decomposition axioms on f and add the resulting functional dependencies to F+.
Step 6. For each pair of functional dependencies f 1 and f 2 in F+
Apply Pseudotransitivity axiom on f 1 and f 2
If f1 and f2 can be combined add the resulting FD’s to F+.
The additional axioms make the process of computing F+ easier by simplifying the process used for step 3 and 4. If we want to compute F+ only by using Armstrong’s rule than eliminate step 5 and 6.
Example. Consider the relation schema R = {H, D, X, Y, Z} and the functional dependencies X→YZ, DX→W, Y→H
Find the closure F+ of FD’s.
Sol. Applying Decomposition on X→YZ gives X→Y and X→Z
Applying Transitivity on X→Y and Y→H gives X→H
Thus the closure F+ has the FD’s
X→YZ, DX→W, Y→H, X→Y, X→Z, X→H
Example. Consider the relation schema R= {A, B, C, D, E} and Functional dependencies A→BC, CD→E, B→D, E→A
Sol. Applying Decomposition on A→BC gives A→B and A→C.
Applying Transitivity on A→B and B→D gives A→D.
Applying Transitivity on CD→E and E→A gives CD→A
Thus the closure F+ has the FD’s
A→BC, CD→E, B→D, E→A, A→B, A→C, A→D, CD→A.
1. Closure of an Attribute w.r.t. the Set of FD’s F
Given a set of functional dependencies F of a relation R, we are often interested in finding all the attributes in R that are functionally dependent on a certain attribute or set of attributes, X, in R. The closure F+ of FD’s F is computed to determine whether the set of FD’s F ╠ A→B. This is possible by computing F+ and checking to see whether A→B belongs to F+.
However, we have an alternate method by which it is possible to test whether F ╠ A→B without computing F+. In this method, we generate X+, the closure of X using the functional dependencies F.
Definition: The X+(A, B, C, D,…) is the closure of X w.r.t. F, if for each FD A→B can be derived from F by using inference axioms. Further more, by additivity axiom for FD, F ╠ A→B if B ⊆ X+.
Importance of A+: It can be used to decide if any FZ A→B can be derived from F. Further, if A+ is all of R, then X is a superkey for R.
The closure algorithm also allows us to determine whether a particular functional dependency exists in R. For attribute sets A and B, if we wish to determine whether A→B, we can calculate A+, and see if it includes B.
Algorithm: To find the closure of a set of attributes X with respect to the set of functional dependencies F.
Input: Given a relation with a set of FD’s F and set of attributes X.
Output: The closure of a set of attributes X w.r.t. the set of FD’s F
Step 1. Initialize X+ = X
Step 2. While (changes to X+) do
Step 3. For each functional dependency A®B in F do
Step 4. If A ⊆ X+ then do
Step 5. X+ = X+ ∪ B
Step 6. End.
Example. Consider the relation schema R= {A, B, C, D, E} with set of functional dependencies F = { A→BC, CD→E, B→D, E→A} and set of attributes X = ABE. Compute the closure of X under F.
Sol. Initialize X+ = X so X+ = ABE. Now for FD A→BC, left side of FD i.e. A ⊆ X+ so X+ = X+ ∪ Y, where Y is the right side of FD i.e. BC so X+ = ABCE. Now for FD BD, left side of FD i.e. B ⊆ X+ so X+ = ABCDE. Since X+ cannot be augmented further hence X+ = ABCDE.
Example. Consider the relation schema R= {A, B, C, D, E, F} with set of functional dependencies F ={A→CE, B→D, C→ADE, BD→F} and set of attributes X=AB. Determine whether F ╠ AB→F.
Sol. To determine whether F ╠ AB®F, find the closure of X. Initialize X+ by X so X+= AB. Now for FD, A→CE left side of FD i.e. A ⊆ X+ so X+ = X+ ∪ {C, E} i.e. right side of FD. So X+ becomes ABCE.
Now for FD, B→D, left side of FD i.e. B subset ABCE so X+ = ABCDE. Now for FD, BD→F, left side of FD i.e. BD subset ABCDE so X+ = ABCDEF.
Now the closure X+ = ABCDEF which contains F so we can say that FD, AB®F is true since F is subset of X+.
Example. Consider the relation schema R = {W, X, Y, Z} with set of functional dependencies F = {W → Z, YZ → X, WZ → Y}. Determine whether WZ, W or YZ are superkeys.
Sol. Compute the closure WZ+. Initialize WZ+ by WZ so WZ+ = WZ. Now the FD WZ→ Y, left side of FD satisfies the requirement, so WZ+ = WZY. Again, the FD YZ→ X, left side of FD satisfies the requirement, so WZ+ = WZYX. Since we have found that every attribute of R is in WZ+, so WZ+ is a superkey.
Compute the closure W+. Initialize W+ by W so W+ = W. Now the FD W → Z, left side of FD satisfies the requirement, so W+ = WZ. Again, the FD WZ → Y, left side of FD satisfies the requirement, so W+ = WZY. Finally, the FD YZ → X , left side of FD satisfies the requirement, so W+ = WZYX. Since we have found that every attribute of R is in W+, W is a superkey for this relation. Because it has no proper subset which is also a superkey, W is a candidate key as well.
Now, we know that WZ is not a candidate key
Compute the closure YZ+. Initialize YZ+ by YZ so YZ+ = YZ. Now the FD YZ → X, left side of FD satisfies the requirement, so YZ+ = YZX. Now we look for an FD where some combination of Y, Z, X is the determinant. Since there is none, we cannot add any new attributes. This means that YZ+ is only YZX, so W is not functionally dependent on YZ, which means YZ is not a superkey.
Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)