CSc 8710 Deductive Databases and Logic Programming
Fall 2008
Assignment #5 (Part of Exam 3 Grade)
December 9, 2008 (Tuesday) - STRICT DEADLINE

Consider the following Deductive Database and Query:

  sflat(X,Y) :- flat(X,Y).
  sflat(X,Y) :- flat(Y,X).

  rsg(X,Y) :- sflat(X,Y).
  rsg(X,Y) :- up(X,X1), rsg(Y1,X1), down(Y1,Y).

  query(X) :- rsg(a,X).

1. Write a program in Java (using JDBC) to answer the query. The program should implement the Naive Evaluation algorithm.
2. Implement the Semi-Naive algorithm (you may assume that sflat is as good as an EDB predicate, i.e. you do not have to track the Delta tuples for this IDB predicate).
3. Implement the Semi-Naive algorithm on the magic sets transformed program. Note that the sflat predicate is not adorned in the transformed program as we are going to treat it as EDB!

Notes

• All the three programs will be executed on three data sets: small, medium, and large. The small data set is shown below.
• For the small data set, you should prompt the user for the query constant. This way we can verify that the program works correctly. For the medium and large data sets, you will disable the prompts and execute the query for constant 'a'.
• To track performance of the three algorithms, you will keep count of the number of "joins" and the average size of the smallest table being joined. Run times may also be recorded. Another parameter for comparison is the number of "inserts" into tables.
• A final report comparing the three algorithms should be submitted.

The base tables in Oracle have the following schema:

create table up (
  per1 varchar2(10),
  per2 varchar2(10));
create table flat (
  per1 varchar2(10),
  per2 varchar2(10));
create table down (
  per1 varchar2(10),
  per2 varchar2(10));

insert into up values ('a','e').
insert into up values ('a','f').
insert into up values ('f','m').
insert into up values ('g','n').
insert into up values ('h','n').
insert into up values ('i','o').
insert into up values ('j','o').

insert into flat values ('g','f').
insert into flat values ('m','n').
insert into flat values ('m','o').
insert into flat values ('p','m').

insert into down values ('l','f').
insert into down values ('m','f').
insert into down values ('g','b').
insert into down values ('h','c').
insert into down values ('i','d').
insert into down values ('p','k').

JDBC Connect String:

Connection conn = DriverManager.getConnection("jdbc:oracle:thin:@tinman.cs.gsu.e
du:1521:tinman",user,pass);