The following are some Prolog programs that are useful for Chapter 12 and 13 problems. To invoke cprolog on tinman, type

$cprolog

| ?- ['dbd.pro'].

| ?- halt.

The Prolog program follows:

% Input data: The relation scheme R and the set of FDs F
% are represented as follows:
% Suppose
% R = (A,B,C,G,H,I)
% F = { A --> B, A --> C, CG --> H, CG --> I, B --> H }
%
% Then, R and F are represented as Prolog lists as follows:
%
% R = [a,b,c,g,h,i]
% F = [ [[a],[b]], [[a],[c]], [[c,g],[h]], [[c,g],[i]], [[b],[h]] ]
% 
% Note that all attributes are in lower case
%
%***************************************************************************
% 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(R,F,X,T,T,T) :- !.
xph(R,F,X,Tnew,Told,XPLUS) :- onepass(R,F,X,Tnew,S),
                              xph(R,F,X,S,Tnew,XPLUS).

onepass(R,[],X,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,[[U,V]|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(R,F,[]).
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.
%
% input: R, F
% output: K
%***************************************************************************

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(R,F,[]).
ckey_check(R,F,[K1|L]) :- not(superkey(R,F,K1)),
                          ckey_check(R,F,L).

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

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




%***************************************************************************
% dfd(R,F,[X,Y]) is true if X-->Y is derivable from F.
% can also be used to derive all FDs in closure of F
% Input: R, F, [X,Y]
% Output: yes if X-->Y is derivable from F; no otherwise
%***************************************************************************

dfd(R,F,X) :- member(X,F).
dfd(R,F,[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([A|L],L).
remove([A|L],M) :- remove(L,M).
remove([A|L],[A|M]) :- remove(L,M).


subset_test([],L).
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).
% ***********************************************************************