1. Create several (at least two) large EDBs for the databases. This should include narrow but deep tree/graph like data and wide and not so deep data. The data should also contain several trees/graphs. 100 depth and 100 width would be considered deep and wide enough.
2. Write programs to answer queries in the following databases using
   • Naive Evaluation of original rules
   • Semi-Naive Evaluation of original rules
   • Semi-Naive Evaluation of transformed rules (magic-set transformation). The magic-set transformation of the rules will be done manually.

Bill of Materials Database

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(<Q>)) :- look_for(P,B,Q).

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

Anti-Trust Database

controls(Comp1,Comp2) :- has_shares(Comp1,Comp2,N), N > 50.

market(Comp1,Mrkt,Qty) :- company(Comp1,Mrkt,Qty).
market(Comp1,Mrkt,Qty) :- controls(Comp1,Comp2), market(Comp2,Mrkt,Qty).

inquire(Comp,Mrkt,sum(<Quota>)) :- market(Comp,Mrkt,Quota).

find_trust(Mrkt,Comp,Total) :- trust_limit(Mrkt,Threshold),
                               inquire(Comp,Mrkt,Total),
                               Total > Threshold.

Flights Database

reaches(X,Y) :- flights(_,X,Y,_,_).
reaches(X,Y) :- flights(_,X,Z,_,_), reaches(Z,Y).

connects(X,Y,D,A) :- flights(_,X,Y,FD,FA), FD >= D, FA <= A.
connects(X,Y,D,A) :- flights(_,X,Z,FD,FA), FD >= D, connects (Z,Y,FD2,A),
                     FD2 >= FA+100.

Siblings-Cousins-Related Database

sibling(X,Y) :- parent(X,Z), parent(Y,Z), X <> Y.
cousin(X,Y) :- parent(X,Xp), parent(Y,Yp), sibling(Xp,Yp).
cousin(X,Y) :- parent(X,Xp), parent(Y,Yp), cousin(Xp,Yp).
related (X,Y) :- sibling(X,Y).
related(X,Y) :- related(X,Z), parent(Y,Z).
related(X,Y) :- related(Z,Y), parent(X,Z).

Trip Database

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

• For each of the algorithms, you must track the amount of database activity (such as number of insert statements executed) and report them in the results; If you can time the queries, it will be more interesting. We expect to see an improvement in the semi-naive over the naive and of the magic-sets over non-magic sets.
• The project will be done in groups of 3 or 4. Exceptions will be made for smaller groups. The number of databases for which the programs will be developed will be equal to the number of members in the group.
• A professional report must be submitted and will count for 30% of the project grade. The report must contain comparative experimental results.