
Solutions for Section 10.1
Solutions for Section 10.2
Solutions for Section 10.3
Solutions for Section 10.4
Answer(model) < PC(model,speed,_,_,_,_) AND speed >= 1000
Answer(hd) < PC(m1,_,_,hd,_,_) AND PC(m2,_,_,hd,_,_) AND m1 <> m2Notice how Datalog allows us to express equality conditions by using the same variable, e.g., hd, twice.
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
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)
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)
Answer(x,y,z) < R(x,y,z) AND x < y AND y < z
(NOT(xy)) OR (NOT(y The second NOT flips < to >=. The first NOT is pushed through the first OR, flipping it to AND:
((NOT(xFinally, push the remaining NOT's into the literals:y))) OR y>=z
(x>=y AND y>=x) OR y>=zIn 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>=zThis 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 >= zNotice that the first rule is a more succinct way of writing
Answer(x,y,z) < R(x,y,z) AND x = yExercise 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 < szExercise 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 >= szNotice 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)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."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).