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,\ 2) M(class,eclass) <- Rel(class,eclass,\

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 \which has a \

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