# Closure of a Set of Functional Dependencies in Database

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)