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+.
- 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.
- 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.
- 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+.
Contact Us