Practice Exam 2

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

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.
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.

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.