CSc 8710 Deductive Databases and Logic Programming
Spring 2007
Assignment #4
April 13, 2007 (Friday)

Consider the following Deductive Database and 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).
  

1. Write a program in Java (using JDBC) 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.

2. Implement the Semi-Naive algorithm.
3. Implement the Semi-Naive algorithm on the magic sets transformed program.

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));

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');