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

From: Jan Hidders <hidders_at_REMOVE.THIS.win.tue.nl>
Date: 4 Apr 2001 18:03:40 GMT
Message-ID: <9afnls$2h4$1_at_news.tue.nl>

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).

-- 
  Jan Hidders

Received on Wed Apr 04 2001 - 20:03:40 CEST