DBMS Closures of a set of functional dependencies

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.

            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

Share This Page on:

Ask Question