Deductive Database = Datalog Program/Rules + relational database Datalog rules define deductive data (views); views may be recursive. Intensional Database (IDB) : Datalog rules Extensional Database (EDB) : relational database Assumption: predicates used in EDB are not defined in IDB. SQL-DATALOG EQUATION ALGORITHM ------------------------------ INPUT: Datalog rules defining predicates p1, ..., pk EDB relations R1, ..., Rn OUTPUT: Pi = evalSQL(pi,P1, ..., Pk, R1, ..., Rn) where evalSQL(...) is an SQL expression that mimics the one-step deduction of the Tp operator discussed in the fixpoint semantics. METHOD: (1) Partition the Datalog rules based on head predicate. (2) Convert Datalog rules to an equivalent set of rules in which all the heads of rules defining the same predicate are the same. Example: P(a,Y) :- r(X,Y). P(X,Y) :- s(X,Z), r(Z,Y). q(X,X) :- p(X,b). q(X,Y) :- p(X,Z), s(Z,Y). is converted to P(X,Y) :- r(Z,Y), X = a. P(X,Y) :- s(X,Z), r(Z,Y). q(X,Y) :- p(X,b), X=Y. q(X,Y) :- p(X,Z), s(Z,Y). (3) for each partition do for each rule P :- Q1, ..., Qn within the partition do Construct SQL select statement Si Union of Si ..... Assume P, Q, R, and S all have same schemas (A,B) P = (select 'a',R.B from R) union (select S.A, R.B from S, R where S.B = R.A) Q = (select P.A, P.A from P where P.B = 'b') union (select P.A, S.B from P, S where P.B = S.A) Example: schema(EDGE) = (F,T) schema(REACH) = (F,T) edge(a,b). edge(a,c). edge(c,b). edge(b,d). reach(X,Y) :- edge(X,Y). reach(X,Y) :- edge(X,Z), reach(Z,Y). SQL-DATALOG Equation: REACH = (select F,T from EDGE) union (select EDGE.F, REACH.T from EDGE, REACH where EDGE.T=REACH.F) REACH = {(a,b),(a,c),(c,b),(b,d),(a,d),(c,d)} is a fixed point for the equaltion (it is also a least fixed point) Try producing another fixed point. NAIVE EVALUATION Algorithm -------------------------- 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 miminal model of the deductive database. METHOD: Step 1: Using the algorithm to construct SQL-DATALOG EQUATIONs for the Datalog program. Let Pi = evalSQL(pi,P1, ..., Pk, R1, ..., Rn) be the SQL-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 := evalSQL(pi,Q1, ..., Qk, R1, ..., Rn); until (Pi = Qi) for all i between 1 and k; output P1, ..., Pk; NOTE: If we use Pi := evalSQL(pi,P1, ..., Pk, R1, ..., Rn); instead of Pi := evalSQL(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. Consider the edge/reach example: Iter oldREACH REACH --------------------------------------------------------------------------------- 0 {} 1 {} {(a,b),(a,c),(c,b),(b,d)} 2 {(a,b),(a,c),(c,b),(b,d)} {(a,b),(a,c),(c,b),(b,d),(a,d),(c,d)} 3 {(a,b),(a,c),(c,b),(b,d),(a,d),(c,d)} {(a,b),(a,c),(c,b),(b,d),(a,d),(c,d)} --------------------------------------------------------------------------------- Another Example: 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). parent(c,a). parent(d,a). parent(d,b). parent(e,b). parent(f,c). parent(g,c). parent(h,d). parent(i,d). parent(f,e). parent(i,e). parent(j,f). parent(j,h). parent(k,g). parent(k,i). Assume following schemas: SIBLING(PERSON1,PERSON2) COUSIN(PERSON1,PERSON2) RELATED(PERSON1,PERSON2) SQL-DATALOG Equations: SIBLING = (select p1.PERSON1, p2.PERSON1 from PARENT p1, PARENT p2 where p1.PERSON2=p2.PERSON2 and p1.PERSON1 <> p2.PERSON1); COUSIN = (select p1.PERSON1, p2.PERSON1 from PARENT p1, PARENT p2, SIBLING s where p1.PERSON2=s.PERSON1 and p2.PERSON2=s.PERSON2) union (select p1.PERSON1, p2.PERSON1 from PARENT p1, PARENT p2, COUSIN c where p1.PERSON2=c.PERSON1 and p2.PERSON2=c.PERSON2); RELATED = (select s.PERSON1, s.PERSON2 from SIBLING s) union (select r.PERSON1, p.PERSON1 from RELATED r, PARENT p where r.PERSON2=p.PERSON2) union (select p.PERSON1, r.PERSON2 from RELATED r, PARENT p where r.PERSON1=p.PERSON2); Iteration SIBLING COUSIN RELATED ---------------------------------------------------------- 1 cd de fg hi fi 2 fh fi ii cd de gh gi fg hi hi jk fi 3 jj kk df dg ch di ci eh ei gj fk hk ij 4 fh dj gh jk gi dk cj ii ck ej ek 5 fj hj gk ik 6 jj kk ------------------------------------------------------------- SEMI-NAIVE EVALUATION Algorithm ------------------------------- 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 mimimal model of the deductive database. METHOD: Step 1: Using the algorithm to construct SQL-DATALOG equations for the Datalog program. Let Pi = evalSQL(pi,P1, ..., Pk, R1, ..., Rn) be the SQL-DATALOG EQUATION for pi. Step 2: Using the algorithm to construct INCREMENTAL SQL-DATALOG EQUATIONS for the Datalog program. Let DPi = evalincrSQL(pi,P1, ..., Pk, DP1, ..., DPk, R1, ..., Rn) be the INCREMENTAL SQL-DATALOG EQUATION for pi. Step 3: for i := 1 to k do begin Pi := evalSQL(pi,{}, ...,{},R1, ..., Rn); DPi := Pi; end; repeat for i := 1 to k do DQi := DPi; for i := 1 to k do begin DPi := evalincrSQL(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 := evalincrSQL(pi,P1, ..., Pk, DP1, ..., DPk, R1, ..., Rn); instead of DPi := evalincrSQL(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 SQL-DATALOG EQUATIONS. These are obtained by taking the union of expressions obtained from evalSQL(pi,...) by substituting one Pi by DPi at a time, i.e. evalincrSQL(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. INCREMENTAL SQL-DATALOG Equation for REACH example DELTA-REACH = (select e.F, d.T from EDGE e, DELTA-REACH d where e.T=d.F) INCREMENTAL SQL-DATALOG Equation for sibling-cousing-related example DELTA-SIBLING = {} DELTA-COUSIN = (select p1.PERSON1, p2.PERSON1 from PARENT p1, PARENT p2, DELTA-SIBLING s where p1.PERSON2=s.PERSON1 and p2.PERSON2=s.PERSON2) union (select p1.PERSON1, p2.PERSON1 from PARENT p1, PARENT p2, DELTA-COUSIN c where p1.PERSON2=c.PERSON1 and p2.PERSON2=c.PERSON2); RELATED = (select s.PERSON1, s.PERSON2 from DELTA-SIBLING s) union (select r.PERSON1, p.PERSON1 from DELTA-RELATED r, PARENT p where r.PERSON2=p.PERSON2) union (select p.PERSON1, r.PERSON2 from DELTA-RELATED r, PARENT p where r.PERSON1=p.PERSON2); 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).