Database Systems: The Complete Book Solutions for Chapter 10

## 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
```

## 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)
```

### 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,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,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)

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

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