CSc 8710
Practice Problems for Exam 2
----------------------------

(1) Transform the following IDB using magic sets algorithm:

  sflat(X,Y) :- flat(X,Y).
  sflat(X,Y) :- flat(Y,X).

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

  query(X) :- rsg(a,X).

(2) Consider the following database:

  g(a,b). 
  g(b,c). 
  g(c,d). 
  g(b,e). 
  g(f,g).
  bi(X,Y) :- g(X,Y). 
  bi(Y,X) :- g(X,Y). 
  even(X,Y) :- bi(X,Z), bi(Z,Y). 
  even(X,Y) :- bi(X,U), bi(U,V), even(V,Y). 

 (a) Using T_P operator, find the minimal model of the database. Show
     values after each iteration.

 (b) Write SQL queries for the IDB relations.
     Show the values of the relations after each iteration of the Naive algorithm.

 (c) Write SQL queries for IDB relations and the delta-relations.
     Show the values of the relations after each iteration of the Semi-Naive algorithm.

(3) Consider the following database:

  a(1).
  a(3).
  b(1,2).
  b(2,3).
  c(3).
  p(X) :- a(X), not q(X).
  q(X) :- b(X,Y), p(Y).
  q(X) :- c(X).

 (a) Is the database stratified? Show the dependency graph and justify
     your answer. If the database is stratified, construct the perfect model.

 (b) Construct the weak well-founded model using the T_P^F operator.
     Show values at each iteration.

(4) Compute ALL the stable models for the following programs:

  (a) 
    a(1,2).
    a(2,3).
    a(3,1).
    p(X) :- a(X,Y), not q(Y).
    q(X) :- a(X,Y), not p(Y).

  (b) 
    p :- not q, not r.
    q :- not p, s.
    r :- not v.
    s :- s, not v.
    v :- not s.