Closures of a set of functional dependencies

A Closure is a set of FDs is a set of all possible FDs that can be derived from a given set of FDs. It is also referred as a Complete set of FDs. If F is used to donate the set of FDs for relation R, then a closure of a set of FDs implied by F is denoted by F⁺. Let's consider the set F of  functional dependencies given below:
F = {A -> B, B -> C, C -> D}
from F, it is possible to derive following dependencies.
A -> A   ...By using Rule-4, Self-Determination.
A -> B   ...Already given in F.
A -> C   ...By using rule-3, Transitivity.
A -> D   ...By using rule-3, Transitivity.
Now, by applyiing  Rule-6 Union, it is possible to derive A⁺ -> ABCD and it can be denoted using A -> ABCD. All such type of FDs derived from each FD of F form a closure of F. Steps to determine F⁺example:

• Determine each set of attributes X that appears as a left hand side of some FD in F.
• Determine the set X⁺ of all attributes that are dependent on X, as given in above example.
• In other words, X⁺ represents a set of attributes that are functionally determined by X based on F. And, X⁺ is called the Closure of X under F.
• All such sets of X⁺, in combine, Form a closure of F.

Algorithm : Determining X⁺, the closure of X under F.

Input : Let F be a set of FDs for relation R.

Steps:
            1. X+ = X                             //initialize X+ to X
            2. For each FD : Y -> Z in F Do
               If Y ⊆ X+  Then                    //If Y is contained in X+ 
               X+  =   X+  ∪  Z                   //add Z to X+  
               End If
               End For
            3. Return  X+                              //Return closure of X

Output : Closure  X+ of X under F

---

• Prev
• Next

---

Questions

---

---