;;;
;;;    by K. Yue
;;;       Dept. of Comp. Sc., UHCL.
;;;       July 10, 1990.
;;;
;;;    representation of
;;;       a set of attributes -- a list of attributes.
;;;       a functional dependencies (fd)
;;;          -- a list of 2 elements, the first element
;;;             is a list of attributes in the left hand
;;;             side of the fd and the second element is
;;;             a list of attributes in the right hand
;;;             side of the fd.
;;;       a set of fd's -- a list of fd's.

;;   
;;   closure-of: find the closure of a set of attributes
;;               with respect to a set of fd's
;;   input: x -- a set of attributes.
;;          fds -- a set of fd's.  Each fd is a list of
;;                 2 elements.
;;   output: the closure of x with respect to fds.
;;
(defun closure-of (x fds)
   (let ((x-new x)
         (x-old) )
      (loop
         (setf x-old x-new)
         (setf x-new (update-closure x-new fds))
         (if (equal x-old x-new) (return x-new)) ) ) )
;;
;;   update-closure: an iteration of finding the clsoure
;;                   a set of attributes.
;;
(defun update-closure (x fds)
   (dolist (fd fds x)
      (if (and (subsetp (first fd) x)
               (not (subsetp (second fd) x)) )
          (return (union x (second fd))) ) ) )
;;
;;   implies-p: to test whether a set of fd's implies a
;;              fd.
;;   input:  s - a set of fd's.
;;           fd - a fd.
;;   output: t if s logically implies fd; nil otherwise.
;;
(defun implies-p (s fd)
   (subsetp (second fd) (closure-of (first fd) s)) )
;;
;;   equi-fdset-p: to test whether two sets of fd's are
;;                 equivalent.
;;   input: fds1 - a set of fd's.
;;          fds2 - a set of fd's.
;;   output: t if fds1 and fds2 are equivalent; nil otherwise.
;;
(defun equi-fdset-p (fds1 fds2)
   (dolist (fd fds1)
      (if (not (implies-p fds2 fd)) (return nil)) )
   (dolist (fd fds2 t)
      (if (not (implies-p fds1 fd)) (return nil)) ) )
;;
;;    preserving-decomposition-p:
;;       to test whether a decomposition preserve a set
;;       of fd's.
;;    input: d -- a decomposition.
;;           fds -- a set of fd.
;;    output: t if d preserve fds; nil otherwise.
;;
(defun preserving-decomposition-p (d fds)
   (dolist (fd fds t)
      (if (not
             (subsetp
               (second fd)
               (decompostion-closure (first fd) d fds) ) )
          (return nil) ) ) )
;;
;;    decomposition-closure:
;;        to find the closure of a set of attributes
;;        x with respect to a decomposition d and
;;        a set of fd's fds.
;;
(defun decompostion-closure (x d fds)
  (let ((old-z)
        (new-z x) )
    (loop
      (setq old-z new-z)
      (setq new-z (R-operations new-z d fds))
      (if (equal old-z new-z) (return new-z)) ) ) )
;;
;;    R-operations: to perform a sequence of R-operations
;;                  on a set of attributes, z, with
;;                  respect to each set of attribute in
;;                  the decomposition d on the set of
;;                  fd's fds.
;;                  An iteration in the algorithm in p400
;;                  of J. Ullman, "Principle of database
;;                  and knowledge-based system," vol 1,
;;                  Computer Science Press.
;;
(defun R-operations (z d fds)
   (dolist (r-i d z)
      (setq z (union z
                 (intersection r-i
                   (closure-of (intersection r-i z) fds) ) )) ) )