CSc 8710, Deductive Databases and Logic Programming
Fall 1998
Take Home Exam III
Due: 11 December 1998 (graduating students); 
     14 December 1998 (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,c).
      r(b,b).
      s(a,a).
      p(X) :- r(X,Y), not p(Y).
      p(Y) :- s(Y,a).