CSc 8710, Deductive Databases and Logic Programming
Fall 1999
Exam III (Take Home)
Due: 5 PM, 13 December 1999 (graduating students); 
     5 PM, 15 December 1999 (others)
---------------------------------------------------

1. Consider the following Datalog program:

   all_subparts(P,S) :- assembly(P,S,_).
   all_subparts(P,S) :- all_subparts(P,Q), assembly(Q,S,_).
   basic_subparts(P,P) :- part_cost(P,_,_,_).
   basic_subparts(P,Q) :- assembly(P,S,_), basic_subparts(S,Q).
   fastest(P,T) :- part_cost(P,S,C,T), not faster(P,T).
   faster(P,T) :- part_cost(P,S,C,T), part_cost(P,S1,C1,T1), T1 < T.
   time_for_basic(A,B,T) :- basic_subparts(A,B), fastest(B,T).
   how_soon(A,T) :- time_for_basic(A,_,T), not larger(A,T).
   larger(P,T) :- time_for_basic(P,_,T), time_for_basic(P,_,T1), T1 > T.

   and the EDB

   part_cost(top_tube,cinelli,20.00,14).
   part_cost(top_tube,columbus,15.00,6).
   part_cost(down_tube,columbus,10.00,6).
   part_cost(head_tube,cinelli,20.00,14).
   part_cost(head_tube,columbus,15.00,6).
   part_cost(seat_mast,cinelli,20.00,6).
   part_cost(seat_mast,cinelli,15.00,14).
   part_cost(seat_stay,cinelli,15.00,14).
   part_cost(seat_stay,columbus,10.00,6).
   part_cost(chain_stay,columbus,10.00,6).
   part_cost(fork,cinelli,40.00,14).
   part_cost(fork,columbus,30.00,6).
   part_cost(spoke,campagnolo,0.60,15).
   part_cost(nipple,mavic,0.10,3).
   part_cost(hub,campagnolo,31.00,5).
   part_cost(hub,suntour,18.00,14).
   part_cost(rim,mavic,50.00,3).
   part_cost(rim,araya,70.00,1).
   part_cost(tire,mavic,30.00,3).
   part_cost(tire,araya,10.00,1).

   assembly(bike,frame,1).
   assembly(bike,wheel,2).
   assembly(frame,top_tube,1).
   assembly(frame,down_tube,1).
   assembly(frame,head_tube,1).
   assembly(frame,seat_mast,1).
   assembly(frame,seat_stay,2).
   assembly(frame,chain_stay,2).
   assembly(frame,fork,1).
   assembly(wheel,spoke,2).
   assembly(wheel,nipple,2).
   assembly(wheel,rim,2).
   assembly(wheel,hub,2).
   assembly(wheel,tire,2).

  (a) Compute the stratification for the program.
  (b) Write Datalog Equations for the Naive evaluation of the IDB
      predicates.
  (c) Compute the stratified model; show the values after each iteration.


2. Consider the following Datalog program:

      insuree(kathy).
      insuree(tom).
      caused_accident(tom).

      low_premium(X) :- cautious_driver(X).

      cautious_driver(X) :- insuree(X), not caused_accident(X).
      cautious_driver(X) :- low_premium(X).

      high_premium(X) :- insuree(X), not cautious_driver(X).

   (a) List all the minimal models for this program.
   (b) Is the program stratified? If yes, give the stratification.
   (c) Write Datalog Equations for the IDB predicates (assuming Naive
       Evaluation).
   (d) Compute the stratified model for the program. Show the values after
       each iteration of the algorithm.

3. Compute the weak-well-founded model (Fitting's model) for
   the following Datalog program. Apply the TpF operator 
   and show the values after each iteration.

      r(a,b).
      r(b,c).
      r(c,d).
      p(X) :- r(X,Y), not q(Y).
      q(X) :- r(Y,X), not p(Y).

4. The Generalized Closed World Assumption (GCWA) states that if a ground
   atomic formula is not present in any of the minimal models of a
   deductive database then it may be assumed to be false. Compute all
   the minimal models for the database of problem 3 and all the ground
   atomic formulas which may be assumed to be false based on the GCWA.