Solutions, Exam 2, DDBLP, Fall 2012
------------------------------------------------------------------------

Note: bi: bidirectional edges, even: even length paths

(1) (a) The iterations are:

    Tp^0 = { }

    Tp^1 = { g(a,b), g(b,c), g(c,d), g(b,e), g(f,g) }

    Tp^2 = { g(a,b), g(b,c), g(c,d), g(b,e), g(f,g),
             bi(a,b), bi(b,c), bi(c,d), bi(b,e), bi(f,g),
             bi(b,a), bi(c,b), bi(d,c), bi(e,b), bi(g,f)
           }

    Tp^3 = { g(a,b), g(b,c), g(c,d), g(b,e), g(f,g),
             bi(a,b), bi(b,c), bi(c,d), bi(b,e), bi(f,g),
             bi(b,a), bi(c,b), bi(d,c), bi(e,b), bi(g,f),
             even(a,a), even(a,c), even(a,e), even(b,b), even(b,d),
             even(c,a), even(c,c), even(c,e), even(d,b), even(d,d),
             even(e,a), even(e,c), even(e,e), even(f,f), even(g,g)
           }

    Tp^4 = Tp^3 

    (b) 

     BI = (select A,B from G) 
          union 
          (select B,A from G);

     EVEN = (select b1.A, b2.B 
             from   BI b1, BI b2 
             where  b1.B = b2.A) 
             union
            (select b1.A, e1.B 
             from   BI b1, BI b2, EVEN e1 
             where  b1.B = b2.A and b2.B = e1.A);

    (c) 

     DELTAEVEN =
            (select b1.A, e1.B 
             from   BI b1, BI b2, DELTAEVEN e1 
             where  b1.B = b2.A and b2.B = e1.A);

------------------------------------------------------------------------
(2) (a) The magic set transformed program is:

    queryF(X) :- reachBF(a,X).
    nodeB(X) :- g(X,Y), magicNodeB(X). 
    nodeB(Y) :- g(X,Y), magicNodeB(Y). 
    reachBF(X,X) :- nodeB(X), magicReachBF(X). 
    reachBF(X,Y) :- g(X,Y), magicReachBF(X). 
    reachBF(X,Y) :- g(X,Z), reachBF(Z,Y), magicReachBF(X). 
    magicReachBF(a).
    magicReachBF(Z) :- g(X,Z), magicReachBF(X).
    magicNodeB(X) :- magicReachBF(X).

    (b) The order of calculation of the IDB predicates is:

        magicReachBF, magicNodeB, NodeB, reachBF, queryF

    magicReachBF:

    iteration 1: a
    iteration 2: a, b
    iteration 3: a, b, c, e, g
    iteration 4: a, b, c, e, g, d, h
    iteration 5: a, b, c, e, g, d, h, i

    magicNodeB:

    iteration 1: a, b, c, e, g, d, h, i

    nodeB:

    iteration 1: a, b, c, e, g, d, h, i
    
    reachBF:

    iteration 1: aa, bb, cc, dd, ee, gg, hh, ii,
                 ab, bc, cd, be, bg, gh, hi

    iteration 2: aa, bb, cc, dd, ee, gg, hh, ii,
                 ab, bc, cd, be, bg, gh, hi,
                 ac, ae, ag, bd, gi, bh

    iteration 3: aa, bb, cc, dd, ee, gg, hh, ii,
                 ab, bc, cd, be, bg, gh, hi,
                 ac, ae, ag, bd, gi, bh,
                 ad, ah, bi

    iteration 4: aa, bb, cc, dd, ee, gg, hh, ii,
                 ab, bc, cd, be, bg, gh, hi,
                 ac, ae, ag, bd, gi, bh,
                 ad, ah, bi,
                 ai

    queryF:

    iteration 1: a, b, c, d, e, g, h, i


------------------------------------------------------------------------
(3) stratum(r) = 1, Stratum(s) = 2, stratum(p) = 3

Stratum 1 (r)
iteration   r
------------------------------
1	    ab, bc, cd, de, ef

2	    ab, bc, cd, de, ef,
            ac, bd, ce, df

3	    ab, bc, cd, de, ef,
            ac, bd, ce, df

4	    ab, bc, cd, de, ef,
            ac, bd, ce, df,
            ad, be, cf

5	    ab, bc, cd, de, ef,
            ac, bd, ce, df,
            ad, be, cf,
            ae, bf

6	    ab, bc, cd, de, ef,
            ac, bd, ce, df,
            ad, be, cf,
            ae, bf,
            af

Stratum 2 (s)
aba, abb

Stratum 3 (p)
iteration p
--------------
1         b
2         b, a
------------------------------------------------------------------------
(4) (a) Dependency graph:

            p -------> q
            ^ <not----^  ^
            |         |  |
            a         b  c

        The program is not stratified because there is a cycle with a
        "not" edge.

    (b) The TpF iterations are shown below:

        Iteration 1:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2) }

        Iteration 2:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3), q(3) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2), p(2) }

        Iteration 3:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3), q(3) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2), p(2), p(3), q(1) }

        Iteration 4:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3), q(3), p(1) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2), p(2), p(3), q(1), q(2) }

        Iteration 5: same as iteration 4.

    (c) Well founded model

        Iteration 1:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2), p(2), q(1) }

        Iteration 2:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3), p(1), q(3) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2), p(2), q(1) }

        Iteration 3:
          I+ = { a(1), a(3), b(1,2), b(2,3), c(3), q(3) }
          I- = { a(2), b(1,1), b(1,3), b(2,1), b(2,2), b(3,1), 
                 b(3,2), b(3,3), c(1), c(2), p(2), q(1), p(3), q(2) }

        Iteration 4: same as iteration 3.

------------------------------------------------------------------------
(5)

I+ = { s(c,a), }
I- = { s(b,a), p(b,b) }

one application of TPF gives

J+ = { r(a,c), r(b,b), s(a,a), p(a,c) }
J- = { r(a,a), r(a,b), r(b,a), r(b,c), r(c,a), r(c,b), r(c,c),
       s(a,b), s(a,c), s(b,a), s(b,b), s(b,c), s(c,a), s(c,b), s(c,c),
       p(a,b), p(b,b), p(b,c), p(c,b), p(c,c) }

another application of TPF gives

K+ = {r(a,c), r(b,b), s(a,a), p(a,a), p(b,a) }
K- = { r(a,a), r(a,b), r(b,a), r(b,c), r(c,a), r(c,b), r(c,c),
       s(a,b), s(a,c), s(b,a), s(b,b), s(b,c), s(c,a), s(c,b), s(c,c),
       p(c,a), p(a,b), p(a,c), p(b,b), p(b,c), p(c,b), p(c,c) }