To test whether a set of attributes tex2html_wrap_inline958 is a superkey, we need to
find the set of attributes functionally determined by tex2html_wrap_inline958 .
Let tex2html_wrap_inline958 be a set of attributes.
We call the set of attributes determined by tex2html_wrap_inline958 under a set F of
functional dependencies the closure of tex2html_wrap_inline958 under F,
denoted tex2html_wrap_inline1292 .
The following algorithm computes tex2html_wrap_inline1292 :
result := tex2html_wrap_inline958
while (changes to result) do
for each functional dependency tex2html_wrap_inline1240
in Fdo
begin
if tex2html_wrap_inline1302 result
then result := result tex2html_wrap_inline1304 ;
end
If we use this algorithm on our example to calculate tex2html_wrap_inline1306 then we find:
We start with result = AG.
A tex2html_wrap_inline1090 B causes us to include B in result.
A tex2html_wrap_inline1090 C causes result to become ABCG.
CG tex2html_wrap_inline1090 H causes result to become ABCGH.
CG tex2html_wrap_inline1090 I causes result to become ABCGHI.
The next time we execute the while loop, no new attributes are added,
and the algorithm terminates.
This algorithm has worst case behavior quadratic in the size of F.
There is a linear algorithm that is more complicated.