CSc 8710 - Fall 2002
Homework 2
Due: 26 September, 2002
-----------------------

(1) Write Prolog code to complete the definitions of the following 
    three predicates in the dbd.pro package that follows:

    (a) cancover(R,F,FC)
         Given R and F, compute the canonical cover FC for F.

    (b) threenf(R,F,R3NF)
         Given R and F, produce a 3NF decomposition R3NF.
     
    (c) ljd(R,F,R1,R2)
         Given R and F and a decomposition (R1,R2) of R, ljd
         returns true iff (R1,R2) is a lossless join decomposition

dbd.pro follows:


% Input data: The relation scheme R and the set of FDs F
% is represented as follows:
%
% R = (A,B,C,D,E)
% F = { A --> B, A --> C, CG --> H, CG --> I, B --> H }
%
% is represented as:
%
% scheme([a,b,c,g,h,i]).
% fds([[[a],[b]],[[a],[c]],[[c,g],[h]],[[c,g],[i]],[[b],[h]]]).
% 
% Note that all attributes are in lower case
%
%scheme([a,b,c,d,e]).
%fds([[[a],[b,c]],[[c,d],[e]],[[b],[d]],[[e],[a]]]).
scheme([a,b,c,d,e]).
fds([[[a,b],[c]],[[c,d],[e]],[[d,e],[b]]]).
%fds1([[[a],[c]]]).

%***************************************************************************
% xplus computes the closure of a set of attributes with respect to R and F
%
% xplus(R,F,X,XPLUS) is true iff XPLUS is the closure of X wrt R and F.
%
% input:  R,F, and X
% output: XPLUS
%***************************************************************************

xplus(R,F,X,XPLUS) :- xph(R,F,X,X,[],XP),
                      mergesort(XP,XPLUS).

xph(_,_,_,T,T,T) :- !.
xph(R,F,X,Tnew,_,XPLUS) :- onepass(R,F,X,Tnew,S),
                              xph(R,F,X,S,Tnew,XPLUS).

onepass(_,[],_,S,S) :- !.
onepass(R,[[U,V]|L],X,T,F) :- subset(T,U), !, 
                              union(T,V,T1),
                              onepass(R,L,X,T1,F).
onepass(R,[[_,_]|L],X,T,F) :- onepass(R,L,X,T,F).

%***************************************************************************
% finfplus checks to see if a FD is in the closure of a set of FDs
%
% finfplus(R,F,[X,Y]) is true if FD, X --> Y belongs to the closure of
% F with respect to R. X and Y are lists of attributes.
%
% input:  R, F, and [X,Y]
% output: Yes/No
%
%***************************************************************************

finfplus(R,F,[X,Y]) :- xplus(R,F,X,Z),
                       subset(Z,Y).

%***************************************************************************
%
% fplus(R,F,FPLUS) is true if FPLUS is the closure of F wrt R.
% 
% input:  R, F
% output: FPLUS
%
%**************************************************************************

fplus(R,F,FPLUS) :- setof(FD,onefinfplus(R,F,FD),FPLUS).

onefinfplus(R,F,[X,Y]) :- subset(R,X),
                          subset(R,Y),
                          not (subset(X,Y)),
                          finfplus(R,F,[X,Y]).

%***************************************************************************
% 
% implies(R,F1,F2) is true if the set of FDs F1 logically implies
% the set of FDs F2.
%
% equiv(R,F1,F2) is true if the sets of FDs F1 and F2 are logically
% equivalent.
%
% input:  R, F1, F2
% output: Yes/No
% 
%***************************************************************************

implies(_,_,[]).
implies(R,F,[[X,Y]|L]) :- xplus(R,F,X,Z),
                          subset(Z,Y),
                          implies(R,F,L).

equiv(R,F1,F2) :- implies(R,F1,F2),
                  implies(R,F2,F1).

%***************************************************************************
%
% superkey(R,F,K) is true if K is a super key of R given FDS F.
% candkey(R,F,K) is true if K is a candidate key of R given FDs F
% 
% could be used to generate super keys/candidate keys as well as 
% test if K is a super key or a candidate key.
%
%***************************************************************************

superkey(R,F,K) :- subset(R,K),
                   xplus(R,F,K,R1),
                   mergesort(R,R1).


candkey(R,F,K) :- superkey(R,F,K),
                  setof(K1,(subset(K,K1),not(subset(K1,K))),S),
                  ckey_check(R,F,S).

ckey_check(_,_,[]).
ckey_check(R,F,[K1|L]) :- not(superkey(R,F,K1)),
                          ckey_check(R,F,L).

%***************************************************************************

%cancover(R,F,FC) :- .

%threenf(R,F,R3NF) :- .

%ljd(R,F,R1,R2) :- .

%***************************************************************************


dfd(_,F,X) :- member(X,F).
dfd(R,_,[X,Y]) :- subset(R,X), 
                  subset(X,Y).
dfd(R,F,[U,V]) :- subset(R,W),
                  dfd(R,F,[X,Y]),
                  union(X,W,U),
                  union(Y,W,V).
dfd(R,F,[X,Z]) :- subset(R,Y),
                  dfd(R,F,[X,Y]),
                  dfd(R,F,[Y,Z]).

%***************************************************************************

%***************************************************************************
% Utility relations
%***************************************************************************

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

union([],A,A) :- !.
union([X|L],A,B) :- member(X,A), union(L,A,B).
union([X|L],A,[X|B]) :- not (member(X,A)), union(L,A,B). 

%reverse([],[]) :- !.
%reverse([X|L],N) :- reverse(L,M), append(M,[X],N).

%append([],X,X) :- !.
%append([X|Y],Z,[X|W]) :- append(Y,Z,W).

subset(S,SS) :- var(SS), !, subset_gen(S,SS).
subset(S,SS) :- subset_test(SS,S).

subset_gen(L,L).
subset_gen(L,M) :- remove(L,M).

remove([_|L],L).
remove([_|L],M) :- remove(L,M).
remove([A|L],[A|M]) :- remove(L,M).


subset_test([],_).
subset_test([A|L],B) :- member(A,B), subset_test(L,B).



mergesort([],[]) :- !.
mergesort([X],[X]) :- !.
mergesort(X,Z) :- split(X,L1,L2),
                  mergesort(L1,M1),
                  mergesort(L2,M2),
                  merge(M1,M2,Z).

split([],[],[]) :- !.
split([X],[X],[]) :- !.
split([X,Y|Z],[X|L1],[Y|L2]) :- split(Z,L1,L2).

merge([],X,X) :- !.
merge(X,[],X) :- !.
merge([X|L],[Y|M],[X|N]) :- X @=< Y, !, merge(L,[Y|M],N).
merge([X|L],[Y|M],[Y|N]) :- Y @=< X, merge([X|L],M,N).




% ***********************************************************************