CSc 8710, DDLP, Fall 2003
Solutions, Exam2 Practice Problems
----------------------------------

(1) (a) Stratum 1: s, t, q
        Stratum 2: r
        Stratum 3: p

    (b) Here the Herbrand Universe is U = {a,b,c,d,e}
        DATALOG EQUATIONS for R and P are:

        R = (S(X,Y) join (U(Y) - T(Y))) union
            (S(X,Y) join R(Y))

        P(X,Y) = Q(X,Y) join (U(X) - R(X))

        Computing R first we get:
          Iteration 0: R = empty set
          Iteration 1: R = empty set

        Computing P next we get:
          P = { (a,b), (b,c), (c,d), (d,e) }

        Therefore the Stratified Minimal model is:
          { s(a,b), s(b,c), s(c,a),
            t(a), t(b), t(c),
            q(a,b), q(b,c), q(c,d), q(d,e),
            p(a,b), p(b,c), p(c,d), p(d,e) }

    (c) Another Minimal Model is:

          { s(a,b), s(b,c), s(c,a),
            t(a), t(b), t(c),
            q(a,b), q(b,c), q(c,d), q(d,e),
            p(a,b), p(b,c), p(c,d), r(d) }

(2)
(a) RSG(X,Y) = FLAT(X,Y) union
               PROJECT[X,Y](UP(X,X1) join RSG(Y1,X1) join DOWN(Y1,Y))

    Iteration 0: RSG = gf, mn, mo, pm
    Iteration 1: RSG = gf, mn, mo, pm, ab, hf, if, jf, fk
    Iteration 2: RSG = gf, mn, mo, pm, ab, hf, if, jf, fk, ac, ad
    Iteration 3: RSG = gf, mn, mo, pm, ab, hf, if, jf, fk, ac, ad

(b) DELTA-RSG(X,Y) = 
          PROJECT[X,Y](UP(X,X1) join DELTA-RSG(Y1,X1) join DOWN(Y1,Y))

    Iteration 0: RSG = gf, mn, mo, pm
                 Delta-RSG = gf, mn, mo, pm
    Iteration 1: Delta-RSG = ab, hf, if, jf, fk
                 RSG = gf, mn, mo, pm, ab, hf, if, jf, fk
    Iteration 2: Delta-RSG = ac, ad
                 RSG = gf, mn, mo, pm, ab, hf, if, jf, fk, ac, ad
    Iteration 3: Delta-RSG = empty
                 RSG = gf, mn, mo, pm, ab, hf, if, jf, fk, ac, ad

(c) Magic Set Transformed Program:

      query_f(X) :- rsg_bf(a,X).
      rsg_bf(X,Y) :- flat(X,Y), magic_rsg_bf(X).
      rsg_bf(X,Y) :- up(X,X1), rsg_fb(Y1,X1), down(Y1,Y), magic_rsg_bf(X).
      rsg_fb(X,Y) :- flat(X,Y), magic_rsg_fb(Y).
      rsg_fb(X,Y) :- up(X,X1), rsg_bf(Y1,X1), down(Y1,Y), magic_rsg_fb(Y).
      magic_rsg_bf(a).
      magic_rsg_fb(X1) :- up(X,X1), magic_rsg_bf(X).
      magic_rsg_bf(Y1) :- down(Y1,Y), magic_rsg_fb(Y).

                     MAGIC_RSG_BF      MAGIC_RSG_FB
      Iteration 0:     a
      Iteration 1:     a                 e, f
      Iteration 2:     a, l, m           e, f
      Iteration 3:     a, l, m           e, f

                     RSG_BF               RSG_FB
      Iteration 0:    mn, mo               gf 
      Iteration 1:    mn, mo, ab           gf, hf, if, jf 
      Iteration 2:    mn, mo, ab, ac, ad   gf, hf, if, jf 
      Iteration 3:    mn, mo, ab, ac, ad   gf, hf, if, jf 

                     QUERY_F
                       b, c, d

(3) 
(a) Fitting model:
                           I+                    I-
      Iteration 1:  r(a,c), r(b,b)         r(a,a), r(a,b), r(b,a), r(b,c), 
                    s(a,a)                 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(b,b), p(b,c), p(c,b), p(c,c)
   
      Iteration 2:  p(a,a), p(b,a)         p(a,b), p(a,c), p(c,a)

(b) Coming Soon

(c) Coming Soon

(d) well founded model is the same as Fitting model.