1. Create a large EDB for the databases. The number of iterations each of the algorithms will take should be at least 20. Also, there should be at least 100 rows in each of the base tables.
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).

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