CSc 8710 Deductive Databases and Logic Programming
Fall 1998
Practice Problems for Exam #2
Due: Monday, November 23, 1998 (will count for 20% of the exam)

1. Consider the rule

       p(X) :- q(X,Y), q(Y,X), r(Y).

   Suppose the relation Q for q contains the (binary) tuples {(1,2), (2,1), (3,3), (1,3), (3,2)} and the relation R for r contains the (unary) tuples {(1), (3), (4)}. What is the value of the relation P for p? For each tuple of P, give a substitution of constants for variables that explains why that tuple is in P.
2. Consider the rules:

           p(X) :- r(X,Y), s(Y,X). 
           p(X) :- q(Y,X). 
           q(X,Y) :- p(X), s(Y,X).

   Suppose the EDB relation R for r contains the tuples {(a,b),(a,c),(b,c),(a,d),(d,d)} and the EDB relation S for s contains the tuples {(b,a),(a,c),(c,b),(d,d)}.
   1. Execute the NAIVE evaluation algorithm on these rules. What are the final values of IDB relations p and q? To demonstrate your understanding of the process, show the the IDB after each iteration of the algorithm.
   2. Execute the SEMI-NAIVE evaluation algorithm on these rules. What are the final values of IDB relations p and q? To demonstrate your understanding of the process, show the the IDB and DELTA-IDB after each iteration of the algorithm.
   3. Execute the QSQI algorithms on these rules assuming the query rule:

        query(X) :-  q(b,X).

      Show the STATE after each iteration.
3. Consider the rules

       p(X,Y,Z) :- q(X,Y,Z) 
       p(X,Y,Z) :- q(X,S,Y), p(Y,T,Z) 
       query(A,B) :- p(a,A,B).

   Transform the rules using the magic-sets algorithm.