Closures of a Set of Functional Dependencies(FD)

Closures of a Set of Functional Dependencies(FD)

  • A closure of 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 denote the set of FDs for relation R , then a closure of a set of FDs implied by F is denoted by F + .

Algorithams: 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. Repeat   # Traverse loop

a) oldX+ = X+  # Save X+ to oldX+

b) For each FD: Y -> Z in F Do

If Y ∈ X+ Then  # if Y is contained in X+

X+ = X+  U   Z  # add Z to X+

End if

End For

Until (X+ = oldX+ )  # Loop through step-2 until no new attributes are found.

3. Return X+   # Return closure of X.

Output: Closure X+ of X under F.

Example:

Consider a relation R ( A , B , C , D , E , F , G ) with the functional dependencies-

A -> BC

BC -> DE

D -> F

CF -> G

Now, Let us try to find out the closure of attributes

Closure of attribute A

A +    = { A }

= { A , B , C }                          ( Using A -> BC )

= { A , B , C , D , E }               ( Using BC -> DE )

= { A , B , C , D , E , F }          ( Using D -> F )

= { A , B , C , D , E , F , G }    ( Using CF -> G )

Thus,

A + = { A , B , C , D , E , F , G }

Closure of attribute D

D +    = { D }

= { D , F }   ( Using D -> F )

We cannot determine any other attribute using attributes D and F contained in the result set.

Thus,

D + = { D , F }

Closure of attribute set {B, C}-

{ B , C } + = { B , C }

= { B , C , D , E }               ( Using BC -> DE )

= { B , C , D , E , F }          ( Using D -> F )

= { B , C , D , E , F , G }    ( Using CF -> G )

Thus,

{ B , C } + = { B , C , D , E , F , G }

Leave a Reply

Your email address will not be published. Required fields are marked *