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 of functional dependencies the closure of under , denoted .

3. The following algorithm computes :

   

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 behaviour quadratic in the size of . There is a linear algorithm that is more complicated.