NAIVE EVALUATION OF Datalog Programs ------------------------------------ INPUT: Datalog Program with EDB containing relations R1, ..., Rn and IDB containing rules defining intensional predicates p1, ..., pk. OUTPUT: Relations P1, ..., Pk for predicates p1, ..., pk which correspond to the Intensional part of the least model of the Datalog Program. METHOD: Step 1: Using the algorithm to construct DATALOG EQUATIONs for the Datalog program. Let Pi = eval(pi,P1, ..., Pk, R1, ..., Rn) be the DATALOG EQUATION for pi. Step 2: for i := 1 to k do Pi := {}; repeat for i := 1 to k do Qi := Pi; for i := 1 to k do Pi := eval(pi,Q1, ..., Qk, R1, ..., Rn); until (Pi = Qi) for all i between 1 and k; output P1, ..., Pk; NOTE: If we use Pi := eval(pi,P1, ..., Pk, R1, ..., Rn); instead of Pi := eval(pi,Q1, ..., Qk, R1, ..., Rn); and delete for i := 1 to k do Qi := Pi; we get a variant of the NAIVE ALGORITHM in which we use the values of relations being generated in the current iteration of the repeat-until loop to calculate other relations in the same iteration.

SEMI-NAIVE EVALUATION OF Datalog Programs ----------------------------------------- INPUT: Datalog Program with EDB containing relations R1, ..., Rn and IDB containing rules defining intensional predicates p1, ..., pk. OUTPUT: Relations P1, ..., Pk for predicates p1, ..., pk which correspond to the Intensional part of the least model of the Datalog Program. METHOD: Step 1: Using the algorithm to construct DATALOG equations for the Datalog program. Let Pi = eval(pi,P1, ..., Pk, R1, ..., Rn) be the DATALOG EQUATION for pi. Step 2: Using the algorithm to construct INCREMENTAL DATALOG EQUATIONS for the Datalog program. Let DPi = eval-incr(pi,P1, ..., Pk, DP1, ..., DPk, R1, ..., Rn) be the INCREMENTAL DATALOG EQUATION for pi. Step 3: for i := 1 to k do begin Pi := eval(pi,{}, ...,{},R1, ..., Rn); DPi := Pi; end; repeat for i := 1 to k do DQi := DPi; for i := 1 to k do begin DPi := eval-incr(pi,P1, ..., Pk, DQ1, ..., DQk, R1, ..., Rn); DPi := DPi - Pi; end; for i := 1 to k do Pi := Pi U DPi; until (DPi = {}) for all i between 1 and k; output P1, ..., Pk; NOTE: If we use DPi := eval-incr(pi,P1, ..., Pk, DP1, ..., DPk, R1, ..., Rn); instead of DPi := eval-incr(pi,P1, ..., Pk, DQ1, ..., DQk, R1, ..., Rn); and delete for i := 1 to k do DQi := DPi; we get a variant of the SEMI-NAIVE ALGORITHM in which we use the values of relations being generated in the current iteration of the repeat-until loop to calculate other relations in the same iteration.

OBTAINING INCREMENTAL DATALOG EQUATIONS. These are obtained by taking the union of expressions obtained from eval(pi,...) by substituting one Pi by DPi at a time, i.e. eval-incr(pi,P1, ..., Pk, DP1, ..., DPk, R1, ..., Rn) = Union of eval(pi,P1,...,Pi-1,DPi,Pi+1,...,Pk,R1,...,Rn) for each i, 1 <= i, <= k.

ALGORITHM QSQI: --------------- Q := { query(X) }; R := { }; State := < Q, R >; While State changes do for all generalized queries q in Q do for all rules r whose head matches with q do begin 1. Unify head of rule r with q and GENERATE NEW GENERALIZED QUERIES for each IDB predicate in body of rule (by propogating bindings and consulting EDB and current IDB relations). 2. GENERATE NEW TUPLES FOR IDB RELATIONS defined in the rule by using EDB and current IDB relations. 3. Update Q and R by adding new GENERALIZED QUERIES and new TUPLES obtained in steps 1. and 2. end;

MAGIC SETS TRANSFORMATION ALGORITHM ----------------------------------- INPUT: A set of IDB rules including a query rule. OUTPUT: A new set of rules, query-equivalent to the original set of rules, which will when evaluated using a bottom-up strategy will perform as well as top-down strategies. METHOD: Step 1: Generate an ADORNED SET OF query-reachable rules from the input rules. Step 2: Generate Magic Rules. FOR each adorned rule r: q_a1 :- ..., p_a2, ... and each IDB predicate p_a2 in the body of the rule DO begin Generate a magic rule as follows: (a) Delete all other occurrences of IDB predicates in the body of r. (b) Replace the name of the predicate p_a2 by magic_p_a2. (c) Delete all non-distinguished arguments of magic_p_a2 thereby obtaining a predicate with possibly fewer arguments. (d) Delete all non-distinguished EDB predicates in the body of r. (e) Replace the name of the head predicate q_a1 by magic_q_a1. (f) Delete all non-distinguished arguments of magic_q_a1 thereby obtaining a predicate with possibly fewer arguments. (g) Exchange the two magic predicates. end Step 3: Modify each ADORNED rule by adding to the body of the rule the magic predicate magic_q_a1 obtained by deleting all non-distinguished arguments, where q_a1 is the head predicate of the rule. Step 4: Output: Modified Adorned Rules + Magic Rules. ---------------------------------------------------------------------------- EXAMPLE: Input set of rules: ------------------- query(X) :- cousin('tom',X). 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). Adorned set of rules: --------------------- query_f(X) :- cousin_bf('tom',X). cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), sibling_bf(Xp,Yp). cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), cousin_bf(Xp,Yp). sibling_bf(X,Y) :- parent(X,Z), parent(Y,Z), X <> Y. Magic rules: ------------ magic_cousin_bf('tom'). magic_cousin_bf(Xp) :- parent(X,Xp), magic_cousin_bf(X). magic_sibling_bf(Xp) :- parent(X,Xp), magic_cousin_bf(X). Modified Adorned Rules: ----------------------- query(X) :- cousin_bf(h,X). cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), sibling_bf(Xp,Yp), magic_cousin_bf(X). cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), cousin_bf(Xp,Yp), magic_cousin_bf(X). sibling_bf(X,Y) :- parent(X,Z), parent(Y,Z), X <> Y, magic_sibling_bf(X). Final Output: ------------- magic_cousin_bf(h). magic_cousin_bf(Xp) :- parent(X,Xp), magic_cousin_bf(X). magic_sibling_bf(Xp) :- parent(X,Xp), magic_cousin_bf(X). query(X) :- cousin_bf(h,X). cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), sibling_bf(Xp,Yp), magic_cousin_bf(X). cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), cousin_bf(Xp,Yp), magic_cousin_bf(X). sibling_bf(X,Y) :- parent(X,Z), parent(Y,Z), X <> Y, magic_sibling_bf(X). DETAILED STEPS TO GENERATE A MAGIC RULE: --------------------------------------- Let us consider the following adorned rule and see how a magic rule is generated from it. cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), cousin_bf(Xp,Yp). (a) Delete all other occurrences of IDB predicates in the body of r. Since there is only one IDB predicate in the body of the rule, no action needs to be taken. cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), cousin_bf(Xp,Yp). (b) Replace the name of the predicate p_a2 by magic_p_a2. cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), magic_cousin_bf(Xp,Yp). (c) Delete all non-distinguished arguments of magic_p_a2 thereby obtaining a predicate with possibly fewer arguments. cousin_bf(X,Y) :- parent(X,Xp), parent(Y,Yp), magic_cousin_bf(Xp). (d) Delete all non-distinguished EDB predicates in the body of r. cousin_bf(X,Y) :- parent(X,Xp), magic_cousin_bf(Xp). (e) Replace the name of the head predicate q_a1 by magic_q_a1. magic_cousin_bf(X,Y) :- parent(X,Xp), magic_cousin_bf(Xp). (f) Delete all non-distinguished arguments of magic_q_a1 thereby obtaining a predicate with possibly fewer arguments. magic_cousin_bf(X) :- parent(X,Xp), magic_cousin_bf(Xp). (g) Exchange the two magic predicates. magic_cousin_bf(Xp) :- parent(X,Xp), magic_cousin_bf(X).