CSc 8710 Deductive Databases and Logic Programming
Fall 1998
Exam #1
Monday, October 12, 1998

1. Assume that a binary tree is represented in Prolog using the function term

     tree(X,LeftSubTree,RightSubTree)

   where X is the element at any node and LeftSubTree and RightSubTree are the left sub-tree and the right sub-tree for the node respectively. The term nil is used when there is no left sub-tree or right-tree. For example, the following function term:

   tree(20,tree(10,nil,nil),tree(40,tree(30,nil,nil),nil))

   would represent the following binary (search) tree:

   Recall that a binary search tree is a binary tree in which all the elements in the left sub-tree of a node are less than the element at the node and all the elements in the right sub-tree of a node are greater than the element at the node. Assume that the binary search tree is being used to represent a set of elements (i.e. no duplicates).

   Write Prolog programs for the following predicates:

   1. member(X,T) is true if X is an element in the binary search tree T.

   2. insert(X,T1,T2) is true if T2 is the tree obtained by inserting X in the binary search tree T1.
      
   3. height(T,H) is true if H is the height of the binary search tree T, where height is defined as the length of the longest path from root to leaf node.
      

2. Consider the following Prolog program:

   mystery1([]).
   mystery1([X|L]) :- mystery2(L).
   mystery2([X|L]) :- mystery1(L).

   How will Prolog respond to the following queries?

   ?- mystery1([a,b,c,d,e]).
   
   
   ?- mystery1([a,b,c,d]).
   
   
   ?- mystery2([a,b,c]).
   
   
   ?- mystery2([a,b]).

   What do the relations mystery1 and mystery2 do?

3. Do the following pairs of terms unify? If they do, provide the most general unifier and if they do not, explain why.

   (a) [[the,Y]|Z] and [[X,hare],[is,here]]
   
   
   
   
   
   (b) [golden|T] and [golden,norfolk]
   
   
   
   
   
   (c) [X,Y|Z] and [mary,likes,wine]
   
   
   
   
   
   (d) A(X,3) and A(Y,Y)
   
   
   
   
   
   (e) [] and [X|Y]
   
   
   
   
   
   (f) [X|[Y|Z]] and [a,b,c,d,e]
   
   
   
   
   
   (g) append([b],[c,d],L) and append([X|Xs],Ys,[X|Zs])

4. Consider the following relational database schema:

   MOVIES(TITLE,Director)
   ACTORS(TITLE,ACTOR)
   THEATERS(TNAME,Address,Phone)
   PLAYS(TNAME,TITLE,STARTTIME)

   The key attributes are shown in all capital letters. The MOVIES table records information about current movies, the ACTORS table records information about the different actors acting in each movie, the THEATERS table records information about the various theaters in a city and the PLAYS table records information about which movie is being played in which theater and at what time.

   Write Datalog programs to answer the following queries. Note: You should use only Datalog constructs, i.e., you should not use any Prolog features that are not available in Datalog such as lists, setof predicate, function terms etc.

   1. Find the directors who have acted in a movie they directed.
      
   2. Find the movies that are directed by Kurosawa or are being played in theater Odeon.
      
   3. Find the directors such that EVERY actor has acted in at least one of his or her movies.
      
   4. Find actors who act ONLY for director Kurosawa.
      
   5. Find all pairs of actors who act in EXACTLY the same movies.

5. Precisely define the following for a Datalog program :
   1. Herbrand Universe of .
      
   2. Herbrand Base of .
      
   3. Herbrand Interpretation for .
      
   4. Herbrand Model for .
      
   5. Minimal Herbrand Model for .
      
   6. Least Herbrand Model for .

6. Consider the following Datalog program.

     P(X,Y) :- Q(X,Y).
     P(X,Y) :- Q(X,Z), P(Z,Y).
     Q(a,b).
     Q(b,c).
     Q(c,d).
     Q(d,e).

   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; If it is a Herbrand model, is it a minimal or least Herbrand model? Explain your answer.

      I1 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e) }
      
      
      
      
      
      I2 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e), P(a,c), P(b,d), P(c,e) }
      
      
      
      
      
      I3 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e), P(a,c), P(b,d), P(c,e),
                   P(a,d), P(b,e) }
      
      
      
      
      
      I4 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e), P(a,c), P(b,d), P(c,e),
                   P(a,d), P(b,e), P(a,e) }

• About this document ...