CSc 8710, Fall 2005
Take Home Exam 1, Due 15 October Midnight (Saturday)
----------------------------------------------------

Please use handin and submit under assignment 9.

(1) Write Prolog programs to implement the following predicates that will be
useful in the implementation of the join operator for HW3:

(a) formSelectionCondition(Rname1,Attributes1,Rname2,Attributes2,Condition)

?- formSelectionCondition(t1,[a,b,c],t2,[b,c,d],C).
C = [[t1.b,=,t2.b],[t1.c,=,t2.c]]

?- formSelectionCondition(t1,[a,b,c],t2,[d,e,f],C).
C = []

This predicate takes as input two sets of relation names and attribute lists and
produces a selection condition based on common attribute names. 

(b) formProjectList(Rname1,Attributes1,Rname2,Attributes2,ProjectList)

?- formProjectList(t1,[a,b,c],t2,[b,c,d],L).
L= [a,t1.b,t1.c,d]

?- formProjectList(t1,[a,b,c],t2,[d,e,f],L).
L = [a,b,c,d,e,f]

This predicate takes as input two sets of relation names and attribute lists and
produces a project list of attributes that will be needed for the join operator. 

(c) joinSchema(Attributes1,Attributes2,JAttributes)

?- joinSchema([a,b,c],[b,c,d],A).
A =  [a,b,c,d]

?- joinSchema([a,b,c],[d,e,f],A).
A =  [a,b,c,d,e,f]

This predicate takes as input two sets of attributes and produces an output set of
attributes that correspond to the join operator's output schema.

(2) Consider the following familiar relational database:

suppliers(SNO,sname,city)
parts(PNO,pname,color,city)
supply(SNO,PNO,qty)

Write DRC, Datalog, and RA expressions for each of the following queries:

(a) Find names of parts that are found in "Duluth" or are supplied by a supplier
    from "Duluth".
(b) Find names of suppliers who supply at least two red parts.
(c) Find name(s) of supplier(s) who supply the most quantity of part "P1".
(d) Find pairs of part numbers such that the two parts are each supplied by
    all suppliers from "Duluth".
(e) Find names of suppliers who supply exactly two red parts.

(3) Consider the following logic program P:

t(a).
u(b).
s(b,c).
v(d,f).
q(a,d).
q(a,c).
p(X,Y) :- q(X,Y), r(X,Y).
r(X,Y) :- s(X,Z), r(Z,Y).
s(X,Y) :- t(X), u(Y).

(a) What is the Herbrand Universe (U_P) for P?
(b) What is the Herbrand Base (B_P) for P?
(c) Compute minimal model using T_P operator starting with the empty interpretation.
    Show work after each iteration.
(d) Show the entire SLD refutation tree for the goal:
    ?- p(X,Y), v(Y,Z).

(4) Is the following DRC formula domain-independent? Justify your answer.

    (Forall X,Q)(supply(U,X,Q) --> (Exists P,N,C)(parts(P,N,red,C)))