CSc 8710 Deductive Databases and Logic Programming
Fall 1998
Practice Problems for Exam #1
Due: Monday, October 12, 1998 (will count for 20% of the exam)

1. Write Prolog programs for the following:
   1. middle(L,X), where X is the middle element of list L. In case the list L has even number of elements, middle should be false.
   2. split(Numbers,Positives,Negatives), where Positives is a list of all positive numbers (greater than 0) in list Numbers and Negatives is a list of all negative numbers (less than 0) in list Numbers.

2. Consider the following Prolog program:

   r(X,[],0).
   r(X,[X|L],N) :- r(X,L,M), N is M + 1.
   r(X,[Y|L],N) :- r(X,L,N).

   How will Prolog answer the following queries?
   1. ?- r(a,[a,b,c,a,d,e],N).
   2. ?- r(a,[a,a,a,a,b],N).
   3. ?- r(a,[b,c,d,e],N).
   What does the program do in general?
3. Suppose we have the following relational database:

   

   The first relation indicates the bars a drinker visits; the second relation tells what beer each bar sells, and the last relation indicates which beer each drinker likes to drink. Write Prolog programs to answer the following queries:

   1. Get the bars that serve a beer that drinker Charles Chugamug likes.
   2. Get the drinkers that frequent at least one bar that serves a beer that they like.
   3. Get the drinkers that frequent only bars that serve some beer that they like (assume that each drinker frequents at least one bar).
   4. Get the drinkers that frequent no bar that serves a beer that they like (i.e. every bar a drinker frequents does not serve a single beer he/she likes).

4. Consider the following Datalog program.

   supplies(X,Z) :- supplies(X,Y), subpart(Z,Y).
   supplies(X,Y) :- d_supplies(X,Y).
   supplies(foobar,X) :- widget(X).
   d_supplies(acme,p1).
   d_supplies(aaa,w3).
   d_supplies(aaa,w4).
   subpart(X,Y) :- d_subpart(X,Y).
   subpart(X,Y) :- d_subpart(X,Z), subpart(Z,Y).
   d_subpart(p2,p1).
   d_subpart(p3,p2).
   d_subpart(w1,p1).
   d_subpart(w2,w1).
   widget(w1).
   widget(w2).
   widget(w3).
   widget(w4).

   1. List the Herbrand Universe for the database.
   2. How many elements does the EHB contain.
   3. How many elements does the IHB contain.
   4. For each of the following Herbrand Interpretations, determine if it is a Herbrand Model for the Datalog program; Explain your answer.

      I1 = EDB U
             { supplies(aaa, w3), supplies(aaa, w4), supplies(acme, p1), 
               supplies(acme, p2), supplies(acme, w1), supplies(acme, w2), 
               supplies(foobar, w1), supplies(foobar, w2), supplies(foobar, w3), 
               supplies(foobar, w4),
               subpart(p2, p1), subpart(p3, p2), subpart(w1, p1), subpart(w2, p1), 
               subpart(w2, w1) }
      
      I2 = EDB U 
             { supplies(aaa, w3), supplies(aaa, w4), supplies(acme, p1), 
               supplies(acme, p2), supplies(acme, p3), supplies(acme, w1), 
               supplies(acme, w2), supplies(foobar, w1), supplies(foobar, w2), 
               supplies(foobar, w3), supplies(foobar, w4),
               subpart(p2, p1), subpart(p3, p1), subpart(p3, p2), subpart(w1, p1), 
               subpart(w2, p1), subpart(w2, w1) }
      
      I3 = EDB U
             { supplies(aaa, w3), supplies(aaa, w4), supplies(acme, p1), 
               supplies(acme, p2), supplies(acme, p3), supplies(acme, w1), 
               supplies(acme, w2), supplies(foobar, w1), supplies(foobar, w2), 
               supplies(foobar, w3), supplies(foobar, w4), supplies(foobar,p1),
               subpart(p2, p1), subpart(p3, p1), subpart(p3, p2), subpart(w1, p1), 
               subpart(w2, p1), subpart(w2, w1), subpart(w1,p3) }