CSc 8710, Deductive Databases and Logic Programming
Fall 2008
Homework 3 (Due: 9 October, 2008)

Write a Prolog program to implement parts of the DRC Interpreter. The well-formed formulas of DRC will be represented as function terms in Prolog. Here are some examples.
Here is Prolog code for storing relations db.pl.

Basic function terms

The basic function terms are of the form atom(R,A) where R is a relation name or one of the six built-in names eq, ne, lt, le, gt, ge and A is a list of arguments consisting of DRC variable names or DRC constants. In the case of the six built-in names, the argument list is a 2-element list consisting of the left and the right argument of the comparison.

General function terms

The general function terms are recursively defined as one of the following: exists(V,F), and(F,G), or(F,G), not(F), where F and G are function terms and V is a list of DRC variable names. Note: All predicate names and DRC variable names are coded as lower-case atoms in Prolog to avoid mix up with Prolog variables that begin with upper-case letter.

Here are the predicates that you will code in SWI-Prolog: 

1. wff(F): returns true if F is a wff, false otherwise.
2. freeVariables(F,L): Given a wff F, returns all the free variables
   of F in L.
3. orSafetyCheck(or(F,G)): returns true if or(F,G) is safe, false
   otherwise.
4. limitedVariables(F,L): Given a wff F, returns all limited variables 
   amongst the free variables of F in L. You may assume that the wffs
   do not have the "chain" of eq predicates (e.g. eq(X,Y), eq(Y,Z),..)
5. maxSC(F,M): Given a wff F, returns a list of maximal sub-conjuncts
   in M. Each subconjunct is a sub-formula of F.
6. safe(F): returns true if wff F is safe.
7. schemaCheck(F) : returns true if predicate names are proper and predicate 
   arities are proper and type checks out properly for constants and repeated
   variables. we will assume that the database schema and instances are
   available in Prolog predicates as follows:
?-dynamic(relation/4).
relation(c1,[city],[string],[["Atlanta"],["Duluth"],["Wichita"],["Dodge City"]]).
relation(c2,[city],[string],[["Carson City"],["Duluth"],["Chennai"]]).
relation(
  suppliers,
  [sno,sname,city],
  [string,string,string],
  [["S1","Jones","Atlanta"],
   ["S2","Smith","Duluth"],
   ["S3","Blake","Marietta"]]
).
relation(
  parts,
  [pno,pname,color,city],
  [string,string,string,string],
  [["P1","Nut","Red","Duluth"],
   ["P2","Bolt","Blue","Marietta"],
   ["P3","Screw","Red","Dunwoody"],
   ["P4","Axle","Green","Marietta"]]
).
relation(
  projects,
  [jno,jname,city],
  [string,string,string],
  [["J1","Bicycles","Duluth"],
  ["J2","Motorcycles","Dunwoody"]]
).
relation(
  spj,
  [sno,pno,jno,qty],
  [string,string,string,number],
  [["S1","P1","J1",100],
   ["S1","P2","J2",100],
   ["S1","P1","J2",100],
   ["S2","P1","J1",100],
   ["S2","P3","J1",100],
   ["S2","P3","J2",100],
   ["S3","P1","J1",100],
   ["S3","P2","J2",100]]
).

Note: For string(X) built-in to work, you must include the following
in the beginning of your program:

?-set_prolog_flag(double_quotes,string).
Page Maintained by raj@cs.gsu.edu