Closure of a Set (X+) and Applications of Closure

Closure of a Set (X⁺) and Applications of Closure – Closure of a set (X⁺) is the set of attributes functionally determined by X. Let S be the set of functional dependencies on relation R. Let X is set of attributes that appear on left hand side of some FD in S and we want to determine the set of all attributes that are dependent on X. Thus for each such set of attribute X, we determine the set  X⁺ of attributes that are functionally determined by X based on S, X⁺ is called closure of X under S.

Algorithm to find the X⁺ is :

X+ = X;
repeat
oldX+ := X+
for each FD Y→Z in S do
if Y is subset of X+ then
X+ : = X+ ∪ Z;
until (X+ =old X+)            /* If X+ did not change then leave loop*/

Example:

Suppose we are given relation R with attributes A,B,C,D and FDs 
 A→BC
 B→CD

Attribute Closure :

 (A+)    = {ABCD}
 (B+)    = {BCD}
 (C+)    = {C}
 (D+)    = {D}
 (AB+)   = {ABCD}
 (AC+)   = {ABCD}
 (AD+)   = {ABCD}
 (BC+)   = {BCD}
 (BD+)   = {BCD}
 (CD+)   = {CD}
 (ABC+)  = {ABCD}
 (ABD+)  = {ABCD}
 (ACD+)  = {ABCD}
 (BCD+)  = {BCD}
 (ABCD+) = {ABCDEF}

Question :
Compute the closure of following set F of functional dependencies for
relation schema R = {A, B, C, D, E}.
 A  → BC
 CD → E
 B  → D
 E  → A

Solution :
 Attribute closure:
 (A)+    = {ABCDE}
 (B)+    = {BD}
 (C)+    = {C}
 (D)+    = {D}
 (E)+    = {ABCDE}
 (AB)+   = {ABCDE}
 (AC)+   = {ABCDE}
 (AD)+   = {ABCDE}
 (AE)+   = {ABCDE}
 (BC)+   = {ABCDE}
 (BD)+   = {BD}
 (BE)+   = {ABCDE}
 (CD)+   = {ABCDE}
 (CE)+   = {ABCDE}
 (DE)+   = {ABCDE}
 (ABC)+  = {ABCDE}
 (ABD)+  = {ABCDE}
 (ABE)+  = {ABCDE}
 (ACD)+  = {ABCDE}
 (ACE)+  = {ABCDE}
 (ADE)+  = {ABCDE}
 (BCD)+  = {ABCDE}
 (BDE)+  = {ABCDE}
 (CDE)+  = {ABCDE}
 (ABCD)+ = {ABCDE}
 (ABCE)+ = {ABCDE}
 (ABDE)+ = {ABCDE}
 (ACDE)+ = {ABCDE}
 (BCDE)+ = {ABCDE}

Applications of Closure set of attributes –

• It is used to identify the additional Functional Dependencies.
• It is used to identify keys (Candidate Keys and Super Keys).
• It is used to identify the Prime and Non Prime Attributes.
• It is used to identify equivalence of Functional Dependency.
• It is used to identify the irreducible set of Functional Dependencies or Canonical Cover of Functional Dependency.

]]>