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