Attribute Closure Algorithm and its Utilization

Closure of a set F of FDs is the set F⁺ of all FDs that can be inferred from F. It is also known as complete set of Functional Dependency. It is denoted by F⁺.

Algorithm : Attribute Closure set

Algorithm to compute a+, the closure of a under F
Result:= a;
while (changes to Result) do  
    for each B → Y in F do
        Begin
            if B ⊆  Result  then  Result := Result ∪  Y  
        End

Utilization of Attribute Closure –

• To test given attribute(s) is superkey/candidate key or not.
• We can check if FD X → Y holds.
• An alternative way to find out F⁺.

1. Test whether attribute is superkey or not.

   Example :
   Let R = (A, B, C, G, H, I) and set of FD are F = { A → B, A → C, CG → H, CG → I, B → H}

   Find out (AG)⁺.

   Result = {A, G}

   First loop :

   A → B includes B in the Result as A⊆ Result (which is AG), so Result := Result ∪ B. 
   Hence Result = {A, G, B}
   A → C causes Result to become ABCG.
   CG → H causes the Result to become ABCGH.
   CG → I causes the Result to become ABCGHI.
   B → H causes Result to become ABCGHI.

   Second loop :

   A → B causes the Result to be unchanged i.e. ABCGHI (B is already part of the Result).
   A → C causes Result to be unchanged.
   CG → H causes the Result to be unchanged.
   CG → I causes the Result to be unchanged.
   B → H causes Result to be unchanged.

   At the end of the second loop, the Result does not change so exit from the loop.

   (AG)⁺ = {A, B, C, G, H, I}

   Conclusion: AG is a super key as all other attributes can be determined by it.
   
   

2. Check whether Fd exists :

   Example :
   Let R = (A, B, C, G, H, I) and set of FD are F = { A →B, A → C, CG → H, CG → I, B → H}

   Check HB → I holds or not

   Result = {H, B}

   First loop :

   In A → B as A ⊆ Result (which is HB) so nothing will be added.
   In A → C nothing added.
   CG → H (CG ⊆ Result (which is HB) so nothing added)
   CG → I nothing added.
   B → H nothing added.

   At the end of the first loop, the Result does not change so exit from the loop.

   Conclusion: HB → I does not hold.
   
   

3. An alternate way to find Closure of FDs (F⁺).

   Example :
   Given a relation R (A, B, C, D, E, F) and set of FDs F: {A → BC, E → CF, B → E, CD → EF}

   Find out closure of {A, B}⁺

   Step-1: Result = AB

   Step-2: First loop

   Result = ABC for A → BC, A ⊆ Result so Result = Result ∪ BC.
   Result = ABC for E→ CF, E ∉ Result so Result = Result.
   Result = ABCE for B → E, B ⊆Result so Result = Result ∪ E.
   Result = ABCE for CD → EF, CD ∉ Result so Result = Result.

   The Result before step2 is AB and after step 2 is ABCE which is different so repeat the same as step 2.

   Step-3: Second loop

   Result = ABCE for A → BC, A ⊆ Result so Result = Result ∪ BC.
   Result = ABCEF for E → CF, E ⊆ Result so Result = Result ∪ CF.
   Result = ABCEF for B → E, B ⊆ Result so Result = Result ∪ E.
   Result = ABCEF for CD → EF, CD ∉ Result so Result = Result.

   The Result before step 3 is ABCE and that after step 3 is ABCEF which is different, so repeat the same as step 3.

   Step-4: Third loop

   Result = ABCEF for A → BC, A ⊆ Result so Result = Result ∪ BC.
   Result = ABCEF for E → CF, E ⊆ Result so Result = Result ∪ CF.
   Result = ABCEF for B → E, B ⊆ Result so Result = Result ∪ E.
   Result = ABCEF for CD → EF, CD ∉ Result so Result = Result.

   The Result before step4 is ABCEF and after step 3 is ABCEF which is the same so stop.

   So Closure of {A, B}⁺ is {A, B, C, E, F}.

   Conclusion: For every attribute/set of attributes we can find closure. This Results in F⁺.