CSc 8710 DDLP, Fall 2012
Exam 3 (Take Home)
DUE: December 9th (Sunday), MIDNIGHT
Use handin to submit under assignment e3
----------------------------------------

(1) (40 Points) Homework 5. Use the handin command and submit 
    the following under assignment 5:

  (a) All source code.
  (b) A short report (1 to 2 pages) detailing the comparisons 
      between the three methods (Naïve, Semi-Naïve, and Semi-Naïve 
      on Magic Set Transformed Rules).

(2) (20 Points) 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)

    vc(X) :- edge(X,Y), not vc(Y).
    edge(1,2).
    edge(1,3).
    edge(2,3).
    edge(2,4).
    edge(3,4).

  (c)

    q :- p, not r.
    q :- r.
    p :- q, r.
    p :- not r.
    r :- s, not v.
    s :- v.
    v :- s.

  (d)

    p :- not q, not r.
    q :- not p, s.
    r :- not v.
    s :- s, not v.
    v :- not s.

(3) (20 Points) Consider the following deductive database:

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

    Using the paraconsistent relational model and algebra compute the 
    Fitting model. Write the algebraic expressions for paraconsistent 
    relation P and Q. Show the work after each iteration including the 
    intermediate steps (complement, join, project etc) of evaluating 
    the algebraic expression. 

(4) (20 Points) Consider the following database:

    m(1,2).
    m(2,3).
    m(3,4).
    m(3,1).
    p(X) :- m(X,Y), not q(Y).
    q(X) :- m(Y,X), not r(X).
    r(X) :- m(X,Y), not p(X).

   (a) Compute the weak well-founded model for the database.
   (b) Using the algorithm in the program transformation paper, 
       transform the database into a logic program which contains 
       "plus" and "minus" predicates for each predicate. 
   (c) Run the transformed program under SWI Prolog and query the
       plus and minus IDB predicates and verify that they match
       the answer in (a).