Closure of Attribute Sets

1. To test whether a set of attributes is a superkey, we need to find the set of attributes functionally determined by .
2. Let be a set of attributes. We call the set of attributes determined by under a set F of functional dependencies the closure of under F, denoted .
3. The following algorithm computes :

    result :=   
   
   		 while (changes to result) do 
   
   		 		 for each functional dependency   
   
   		 		 		 		 		 in  F do 
   
   		 		 		 begin 
   
   		 		 		 		 if     result 
   
   		 		 		 		 then  result := result   ;
   
   		 		 		 end 
   
   

4. If we use this algorithm on our example to calculate then we find:
   • We start with result = AG.
   • A B causes us to include B in result.

   • A C causes result to become ABCG.
   • CG H causes result to become ABCGH.

   • CG I causes result to become ABCGHI.
   • The next time we execute the while loop, no new attributes are added, and the algorithm terminates.
5. This algorithm has worst case behavior quadratic in the size of F. There is a linear algorithm that is more complicated.