CSc 8710 Deductive Databases and Logic Programming
Fall 2002
Programming Assignment #4
October 17, 2002 (Thursday)

Consider the following Datalog query:

  trip(L,S,E) :- leg(L,S,E).
  trip(L,S,E) :- leg(L,S,I), trip(L,I,E). 
  trip(L,S,E) :- interchange(I,L,M), trip(L,S,I), trip(M,I,E).

  query(X) :- trip(blue,suwanee,X).

• leg(L,S,T) is true if it there is a train on line L which leaves station S and arrives at the next station T with no intermediate stops. For example, on MARTA, the following may be some of the instances:

    leg(ne,doraville,chamblee).
    leg(ne,chamblee,doraville).
    leg(ne,chamblee,brookhaven).
    leg(ne,brookhaven,chamblee).
    leg(ne,brookhaven,lenox).
    leg(ne,lenox,brookhaven).
    leg(n,medical-center,dunwoody).
    leg(n,dunwoody,medical-center).
  

• interchange(S,L,M) is true if it is possible to change from line L to line M in station S. Instances in MARTA would be:

    interchange(lindbergh,n,ne).
    interchange(lindbergh,ne,n).
    interchange(fivepoints,n,e).
    interchange(fivepoints,e,n).
    interchange(fivepoints,ne,e).
    interchange(fivepoints,e,ne).
  

  Write a program in Java (using JDBC or SQLJ database access) to answer the query. The program should implement the Naive Evaluation algorithm. You should prompt the user for the two constants in the query (line and station values).

  To track the database activity in the Naive algorithm you will report the number of database inserts that take place.

  The base tables in Oracle have the following schema:

  create table leg (
    line    char(10),
    departs char(20),
    arrives char(20));
  
  create table interchange (
    station char(20),
    line1   char(10),
    line2   char(10));
  

  and sample data is:

  insert into leg values ('blue','suwanee','norcross');
  insert into leg values ('blue','norcross','suwanee');
  insert into leg values ('blue','norcross','doraville');
  insert into leg values ('blue','doraville','norcross');
  insert into leg values ('blue','doraville','chamblee');
  insert into leg values ('blue','chamblee','doraville');
  insert into leg values ('blue','chamblee','brookhaven');
  insert into leg values ('blue','brookhaven','chamblee');
  insert into leg values ('blue','brookhaven','lenox');
  insert into leg values ('blue','lenox','brookhaven');
  insert into leg values ('blue','lenox','lindbergh');
  insert into leg values ('blue','lindbergh','lenox');
  insert into leg values ('blue','lindbergh','northavenue');
  insert into leg values ('blue','northavenue','lindbergh');
  insert into leg values ('blue','northavenue','fivepoints');
  insert into leg values ('blue','fivepoints','northavenue');
  insert into leg values ('blue','fivepoints','lakewood');
  insert into leg values ('blue','lakewood','fivepoints');
  insert into leg values ('blue','lakewood','collegepark');
  insert into leg values ('blue','collegepark','lakewood');
  insert into leg values ('blue','collegepark','airport');
  insert into leg values ('blue','airport','collegepark');
  
  insert into leg values ('black','northpoint','sandysprings');
  insert into leg values ('black','sandysprings','northpoint');
  insert into leg values ('black','sandysprings','dunwoody');
  insert into leg values ('black','dunwoody','sandysprings');
  insert into leg values ('black','dunwoody','medicalcenter');
  insert into leg values ('black','medicalcenter','dunwoody');
  insert into leg values ('black','medicalcenter','lindbergh');
  insert into leg values ('black','lindbergh','medicalcenter');
  insert into leg values ('black','lindbergh','northavenue');
  insert into leg values ('black','northavenue','lindbergh');
  insert into leg values ('black','northavenue','fivepoints');
  insert into leg values ('black','fivepoints','northavenue');
  insert into leg values ('black','fivepoints','lakewood');
  insert into leg values ('black','lakewood','fivepoints');
  insert into leg values ('black','lakewood','collegepark');
  insert into leg values ('black','collegepark','lakewood');
  insert into leg values ('black','collegepark','airport');
  insert into leg values ('black','airport','collegepark');
  
  insert into leg values ('gray','pacesferry','chastain');
  insert into leg values ('gray','chastain','pacesferry');
  insert into leg values ('gray','chastain','lindbergh');
  insert into leg values ('gray','lindbergh','chastain');
  insert into leg values ('gray','lindbergh','northlake');
  insert into leg values ('gray','northlake','lindbergh');
  insert into leg values ('gray','northlake','tucker');
  insert into leg values ('gray','tucker','northlake');
  insert into leg values ('gray','tucker','lawrenceville');
  insert into leg values ('gray','lawrenceville','tucker');
  
  insert into leg values ('red','douglas','bankhead');
  insert into leg values ('red','bankhead','douglas');
  insert into leg values ('red','bankhead','philips');
  insert into leg values ('red','philips','bankhead');
  insert into leg values ('red','philips','fivepoints');
  insert into leg values ('red','fivepoints','philips');
  insert into leg values ('red','fivepoints','gsu');
  insert into leg values ('red','gsu','fivepoints');
  insert into leg values ('red','gsu','avondale');
  insert into leg values ('red','avondale','gsu');
  insert into leg values ('red','avondale','stonemountain');
  insert into leg values ('red','stonemountain','avondale');
  
  insert into leg values ('green','easteast','easthaven');
  insert into leg values ('green','easthaven','easteast');
  insert into leg values ('green','easthaven','marietta');
  insert into leg values ('green','marietta','easthaven');
  insert into leg values ('green','marietta','eastcobb');
  insert into leg values ('green','eastcobb','marietta');
  
  insert into interchange values ('lindbergh','black','blue');
  insert into interchange values ('lindbergh','blue','black');
  insert into interchange values ('lindbergh','black','gray');
  insert into interchange values ('lindbergh','gray','black');
  insert into interchange values ('lindbergh','blue','gray');
  insert into interchange values ('lindbergh','gray','blue');
  insert into interchange values ('fivepoints','black','red');
  insert into interchange values ('fivepoints','red','black');
  insert into interchange values ('fivepoints','blue','red');
  insert into interchange values ('fivepoints','red','blue');
  insert into interchange values ('fivepoints','blue','black');
  insert into interchange values ('fivepoints','black','blue');