CSc 8710, DDLP Practice Exam 2
------------------------------

1. Consider the rules:

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

and the EDB:

s(a,b). t(a). q(a,b).
s(b,c). t(b). q(b,c).
s(c,a). t(c). q(c,d).
              q(d,e).
(a) Determine a stratification for the database.
(b) Find the stratified minimal model (the intuitive one) for the database.
(c) Find another minimal model.

2. Consider the following IDB:

rsg(X,Y) :- flat(X,Y).
rsg(X,Y) :- up(X,X1), rsg(Y1,X1), down(Y1,Y).

and the EDB:

up(a,e). flat(g,f).  down(l,f).
up(a,f). flat(m,n).  down(m,f).
up(f,m). flat(m,o).  down(g,b).
up(g,n). flat(p,m).  down(h,c).
up(h,n).             down(i,d).
up(i,o).             down(p,k).
up(j,o).

(a) Write SQL-DATALOG Equations for the IDB predicate and show the Naive
    algorithm computation of the IDB table. Show table after each iteration.
(b) Write the incremental SQL-DATALOG Equations for the IDB predicate and
    show the Semi-Naive algorithm computation of the IDB table. Show delta values 
    after each iteration.
(c) Transform the IDB using magic set transformation method for the query
    rsg(a,X). Show the Naive algorithm computation algorithm computation.
    Again, show work after each iteration.

(3) Let DB be the following general deductive database:
   r(a,c).
   r(b,b).
   s(a,a).
   p(X,a) :- r(X,Y), not p(X,Y).
   p(a,Y) :- s(Y,a).

(a) Compute the Fitting model. Show work after each iteration.
(b) Using paraconsistent relational algebra, write DATALOG equations.
(c) Starting with the EDB as the partial interpretation, show the calculation of
    the fixpoint solution to the DATALOG equation. Show work after each iteration.
(d) Compute the well-founded model.