Re: Searching for algorithm: equivalence of sets of functional dependencies

Thanks.

On 4 Apr 2001 18:03:40 GMT, hidders_at_REMOVE.THIS.win.tue.nl (Jan Hidders) wrote:

>
>Suppose you have two sets of FDs: S1 and S2. Then you check if all
>dependencies in S1 follow from those in S2 and vice versa. To check if
>X -> Y follows from a set S simply compute the closure of X under the
>dependencies in S. This can be done with the following algorithm:
>
>FUNCTION Closure(X,S)
>BEGIN
> old_clos := {};
> new_clos := X;
> WHILE old_clos <> new_clos DO
> old_clos := new_clos;
> FOR X->Y IN S DO
> IF X <= old_clos /* <= is 'subset or equal */
> THEN new_clos := new_clos + Y /* + is 'set union' */
> FI
> OD
> OD
> RETURN new_clos
>END
>
>The dependency X->Y follows from the set S iff Y is a subset of
>Closure(X,S).
  Received on Sun Apr 08 2001 - 23:10:53 CEST