Assignment 5

CSc 8710 Deductive Databases and Logic Programming
Fall 2010
Assignment #5
Due: Along with Take Home Final Exam (Dec 1st)

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

where the base predicates are defined as follows:

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 Oracle-JDBC) or your favorite language and database system 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). Note: If you use a language other than Java, I need to see a demo of the program on the small data set.
Java code to connect and execute a query in Oracle
ojdbc6.jar and ojdbc6_g.jar.
To track the database activity in the Naive algorithm you will report the number of database inserts that take place, the number of joins, as well as the average size of the smallest table in each join.
Implement the Semi-Naive algorithm.
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));

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

Tha above data set will be referred to as the "Small" data set; Run your programs on two additional data sets: Medium and Large. You should create new versions of your three programs (Naive, SemiNaive, MagicSemiNaive) for the medium and large data sets in which there is no prompting for the query parameters. You should run the query trip('b','b19',X) on the Medium data set and the query trip('l9','l9s25',X) on the Large data set.

Submission Instructions:

You must submit the following programs:

Naive.java, SemiNaive.java, and MagicSemiNaive.java (these three programs will prompt the user for the values).
A short report (1-2 pages) describing the performance results (comparison between the three methods on the three data sets). This report should be a pdf file.