Database Systems: The Complete Book
Solutions for Chapter 10

Solutions for Section 10.1
Solutions for Section 10.2
Solutions for Section 10.3
Solutions for Section 10.4

Solutions for Section 10.1

Exercise 10.1.1(a)

     Answer(model) <- PC(model,speed,_,_,_,_) AND speed >= 1000

Exercise 10.1.1(f)

     Answer(hd) <- PC(m1,_,_,hd,_,_) AND PC(m2,_,_,hd,_,_) AND m1 <> m2
Notice how Datalog allows us to express equality conditions by using the same variable, e.g., hd, twice.

Exercise 10.1.1(h)

     FastComputers(M) <- PC(M,S,_,_,_,_) AND S >= 700
     FastComputers(M) <- Laptop(M,S,_,_,_,_) AND S >= 700

     Answer(maker) <- Product(maker,m1,_) AND Product(maker,m2,_) AND
                      FastComputers(m1) AND FastComputers(m2) AND m1 <> m2

Return to Top

Solutions for Section 10.2

Exercise 10.2.1(d)

The following uses X as a temporary predicate to represent R UNION S.

     X(a,b,c) <- R(a,b,c)
     X(a,b,c) <- S(a,b,c)

     Answer(a,b,c) <- X(a,b,c) AND NOT T(a,b,c)

Exercise 10.2.1(g)

This expression asks for those (a,b) pairs that are both the first two components of a tuple from R and the last two components of a tuple from S. Thus, the following rule works.

     Answer(a,b) <- R(a,b,_) AND S(_,a,b)
A more mechanical solution would be something like:

     X(a,b) <- R(a,b,_)
     Y(a,b) <- S(_,a,b)
     Answer(a,b) <- X(a,b) AND Y(a,b)

Exercise 10.2.2(b)

     Answer(x,y,z) <- R(x,y,z) AND x < y AND y < z

Exercise 10.2.2(e)

We need to work on this using DeMorgan's laws to put the expression into conjunctive normal form. First, we push the NOT through the AND, which ``flips'' the AND to an OR, giving us:

     (NOT(xy)) OR (NOT(y

The second NOT flips < to >=.
The first NOT is pushed through the first OR, flipping it to AND:



     ((NOT(xy))) OR y>=z



Finally, push the remaining NOT's into the literals:



     (x>=y AND y>=x) OR y>=z



In this case, we can observ esomething special about the left side of
the OR.  The only way for x>=y and y>=x both to hold is if x=y.
Thus, our final form is:



     x=y OR y>=z



This condition can be expressed by two rules:



     Answer(x,x,z) <- R(x,x,z)
     Answer(x,y,z) <- R(x,y,z) AND y >= z



Notice that the first rule is a more succinct way of writing



     Answer(x,y,z) <- R(x,y,z) AND x = y




Exercise 10.2.4(b)



     Answer(rx,ry,rz,sx,sy,sz) <- R(rx,ry,rz) AND S(sx,sy,sz) AND
                                  rx < sy AND ry < sz




Exercise 10.2.4(e)


Taking advantage of the expression simplification we did for Exercise
4.3.2(e):



     Product(rx,ry,rz,sx,sy,sz) <- R(rx,ry,rz) AND S(sx,sy,sz)

     Answer(rx,ry,rz,sx,rx,sz) <- Product(rx,ry,rz,sx,rx,sz)
     Answer(rx,ry,rz,sx,sy,sz) <- Product(rx,ry,rz,sx,sy,sz) AND ry >= sz



Notice that rx appears four times in the first rule above, thus
enforcing rx = sy.


Exercise 10.2.5(a)


That looks to us like the natural join of Q and R, followed by
projecting out the middle (z) component.



     PI_{x,y} (Q JOIN R)





Return to Top





Solutions for Section 10.3



Exercise 10.3.1(a)


The following pairs are added to Reaches: (CHI,SF), (CHI,DEN),
(CHI,DAL), (CHI,CHI), (DEN,DEN), (DEN,SF),
(DAL,DEN), (DAL,SF), (DAL,DAL), and (SF,SF).


The following tuples are added to Connects:
(DAL,SF,1530,2100),
(DEN,SF,1500,2100),
(SF,SF,900,2100), and
(SF,SF,930,2100).


Nothing is added to UAreaches.


To AAreaches we add:
(CHI,SF), (CHI,DAL), (CHI,CHI),
(DAL,SF), (DAL,DAL), and (SF,SF).



Exercise 10.3.2(a)


We could define FollowOn as in Example 4.36 and then simply say:



     P(x,y) <- FollowOn(x,y) AND NOT SequelOf(x,y)



Another approach is to define P(x,y) recursively, starting with two
levels of sequel as a basis.
This recursion is:



     P(x,y) <- SequelOf(x,z) AND SequelOf(z,y)
     P(x,y) <- SequelOf(x,z) AND P(z,y)




Exercise 10.3.3(b)



     1) S(class,eclass) <- Rel(class,eclass,"single")
     2) M(class,eclass) <- Rel(class,eclass,"multi")

     3) S(x,y) <- S(x,z) AND S(z,y)
     4) M(x,y) <- M(x,z) AND M(z,y)
     5) M(x,y) <- S(x,z) AND M(z,y)
     6) M(x,y) <- M(x,z) AND S(z,y)



In explanation, rules (1) and (2) are basis rules, that handle ``paths''
of length 1.
Rule (3) is the recursion for S: 
paths that are all single must be composed of two paths that are all
single.
Rules (4), (5), and (6) are the recursion for M:
a path with a "multi" may be composed of two paths, at least one of
which has a "multi."



Return to Top





Solutions for Section 10.4



Exercise 10.4.2(b)



WITH RECURSIVE Single(class, eclass) AS
        (SELECT class, eclass
         FROM Rel
         WHERE mult = 'single')
    UNION
        (SELECT Single.class, Rel.eclass
         FROM Single, Rel
         WHERE Single.eclass = Rel.class AND
               mult = 'single')

SELECT * FROM Single;




Exercise 10.4.2(c)



WITH RECURSIVE Multi(class, eclass) AS
        (SELECT class, eclass
         FROM Rel
         WHERE mult = 'multi')
    UNION
        (SELECT Multi.class, Rel.eclass
         FROM Multi, Rel
         WHERE Multi.eclass = Rel.class)
    UNION
        (SELECT Rel.class, Multi.eclass
         FROM Multi, Rel
         WHERE Rel.eclass = Multi.class)

SELECT * FROM Multi;



In the above, we start with a connection known to be ``multi'' as the
basis.
We then allow an arbitrary connection to be attached to the end (the
middle term of the union) or the beginning (the last term of the union)
of a connection known to have at least one ``multi'' connection.
The reader may wish to compare this approach with the approach taken in
Exercise 10.3.3(b).
Either approach is appropriate for both Datalog and SQL, except that
SQL does not support nonlinear recursion as was used in Exercise
10.3.3(b).



Return to Top