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 *f*1 and *f*2 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)