CSc 8710, Homeworks 5, 6, 7
Due: 18 November 2003
---------------------
Consider the following IDB:

sub_part(X,Y,Q,T) :- comp(X,Y,Q,T).
sub_part(X,Y,Q,T) :- comp(Z,Y,Q2,T), sub_part(X,Z,Q1,T1),
                     Q is Q1 * Q2.
look_for(P,Y,Q) :- sub_part(P,Y,Q,b).

basic_comp(P,B,sum()) :- look_for(P,B,Q).

temp_cost(P,X) :- basic_comp(P,B,Q), price(B,C), X is Q * C.
cost(P,sum()) :- temp_cost(P,C).

The project involves the following parts:

(1) Populate a relational database for the EDB with large amounts of data.
    Create at least two different instances (one in which the data is very
    deep but narrow and the second in which the data is wide and relatively
    shallow). 

(2) Write a Java program that implements the naive algorithm. This program
    should prompt the user for a part and calculate its cost as defined
    by the rules.

(3) Write a Java program that implements the semi-naive algorithm. This program
    should prompt the user for a part and calculate its cost as defined
    by the rules.

(4) Write a Java program that implements the semi-naive algorithm corresponding
    to the following magic set transformed rules. This program should prompt
    the user for a part and calculate its cost as defined by the rules.

query(X,Y) :- basic_comp_bff(engine,X,Y).
basic_comp_bff(P,B,sum()) :- look_for_bff(P,B,Q), magic_basic_comp_bff(P).
look_for_bff(P,B,Q) :- sub_part_bffb(P,B,Q,b), magic_look_for_bff(P).

sub_part_bffb(X,Y,Q,T) :- comp(X,Y,Q,T), magic_sub_part_bffb(X,T).
sub_part_bffb(X,Y,Q,T) :- comp(Z,Y,Q2,T), sub_part_bbff(X,Z,Q1,T1),
                          Q is Q1 * Q2, magic_sub_part_bffb(X,T).

sub_part_bbff(X,Y,Q,T) :- comp(X,Y,Q,T), magic_sub_part_bbff(X,Y).
sub_part_bbff(X,Y,Q,T) :- comp(Z,Y,Q2,T), sub_part_bbff(X,Z,Q1,T1),
                          Q is Q1 * Q2, magic_sub_part_bbff(X,Y).

magic_basic_comp_bff(engine).
magic_look_for_bff(P) :- magic_basic_comp_bff(P).
magic_sub_part_bffb(P,b) :- magic_look_for_bff(P).

magic_sub_part_bbff(X,Z) :- comp(Z,Y,Q2,T), magic_sub_part_bffb(X,T).
magic_sub_part_bbff(X,Z) :- comp(Z,Y,Q2,T), magic_sub_part_bbff(X,Y).

temp_cost_bf(P,X) :- basic_comp_bff(P,B,Q), price(B,C), X is Q * C.
cost_bf(P,sum()) :- temp_cost_bf(P,C).

(5) Track the database activity in each of the above 3 programs. You should
    keep count of the number of database inserts and other interesting parameters
    to compare the performance of the 3 methods. Finally, produce a comparative
    analysis on both the data sets (plots would be useful).