A First Course in Database Systems |

PI_model( SIGMA_{speed >= 150} ) (PC)

`hd`

.
However, these two PC's could in fact be the same, so we must also
require in the theta-join that the model numbers be unequal.
Finally, we want the hard disk sizes, so we project onto
`hd`

.The expression is easiest to see if we write it using some temporary values. We start by renaming PC twice so we can talk about two occurrences of the same attributes.

R1 = RHO_{PC1} (PC) R2 = RHO_{PC2} (PC) R3 = R1 JOIN_{PC1.hd = PC2.hd AND PC1.model <> PC2.model} R2 R4 = PI_{PC1.hd} (R3)

R1 = PI_{model,speed} (PC) UNION PI_{model,speed} (Laptop) R2 = PI_{maker,model} (SIGMA_{speed>=133} (R1) JOIN Product) R3 = RHO_{T(maker2, model2)} (R2) R4 = R2 JOIN_{maker = maker2 AND model <> model2} (R3) R5 = PI_{maker} (R4)

The minimum number of tuples that can appear in the result occurs if every tuple of one relation also appears in the other. Surely the union has at least as many tuples as the larger of R and that is, max(n,m) tuples. However, it is possible for every tuple of the smaller to appear in the other, so it is possible that there are as few as max(n,m) tuples in the union.

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

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 >= 133 FastComputers(M) <- Laptop(M,S,_,_,_,_) AND S >= 133 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 = y## Exercise 4.3.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 4.3.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 4.3.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 4.4

## Exercise 4.4.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 4.4.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 4.4.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 4.5

## Exercise 4.5.1(a)

SIGMA_{speed<150 AND price>1500} (PC) = EMPTYSET## Exercise 4.5.1(d)

This complex expression is best seen as a sequence of steps in which we define temporary relations R1 through R4 that stand for nodes of expression trees. Here is the sequence:R1(maker, model, speed) := PROJ_{maker,model,speed}(Product JOIN PC) R2(maker, speed) := PROJ_{maker,speed}(Product JOIN Laptop) R3(model) := PROJ_{model}(R1 JOIN_{R1.maker=R2.maker AND R1.speed<=R2.speed} R2) R4(model) := PROJ_{model}(PC)The constraint is that R4 is a subset of R3.In explanation, R1 is the set of maker-model-speed triples for PC's, and R2 is the set of maker-speed pairs for laptops. Note JOIN is the natural join. R3 is the set of models (of PC's) for which there is a laptop by the same manufacturer at least as fast. R4 is all the PC models. Note that R3 is surely a subset of R4, so the constraint that R4 be a subset of R3 is really asking that these sets be equal; i.e., every PC has a laptop by the same manufacturer that is at least as fast.

## Exercise 4.5.3(a)

Producers(c) <- Movie(_,_,_,_,_,c) Execs(c) <- MovieExec(_,_,c,_) Problem(c) <- Producers(c) AND NOT Execs(c)Here, Producers(c) is true if c is the certificate of a producer, and Execs(c) is true if c is the certificate of a movie executive. We have a problem if there is a value of c in the former set but not in the latter. Thus, we constrain Problem to be an empty relation.## Solutions for Section 4.6

## Exercise 4.6.1

As a bag, the value is {133, 120, 166, 166, 166, 200, 200, 180, 200, 160}. Order is unimportant, of course. The average is 169.1.As a set, the value is {133, 120, 166, 200, 180, 160}. The average is 159.8.

## Exercise 4.6.4(a)

As sets, an element x is in the left-side expression(R UNION S) UNION T if and only if it is in at least one of R, S, and T. Likewise, it is in the right-side expression

R UNION (S UNION T) under exactly the same conditions. Thus, the two expressions have exactly the same members, and the sets are equal.

As bags, an element x is in the left-side expression as many times as the sum of the number of times it is in R, S, and T. The same holds for the right side. Thus, as bags the expressions also have the same value.

## Exercise 4.6.4(h)

As sets, element x is in the left sideR UNION (S INTERSECT T) if and only if x is either in R or in both S and T. Element x is in the right side

(R UNION S) INTERSECT (R UNION T) if and only if it is in both R UNION S and R UNION T. If x is in R, then it is in both unions. If x is in both S and T, then it is in both union. However, if x is neither in R nor in both of S and T, then it cannot be in both unions. For example, suppose x is not in R and not in S. Then x is not in R UNION S. Thus, the statement of when x is in the right side is exactly the same as when it is in the left side: x is either in R or in both of S and T.

Now, consider the expression for bags. Element x is in the left side the sum of the number of times it is in R plus the smaller of the number of times x is in S and the number of times x is in T. Likewise, the number of times x is in the right side is the smaller of

A moment's reflection tells us that this minimum is the sum of the number of times x is in R plus the smaller of the number of times x is in S and in T, exactly as for the left side.

- The sum of the number of times x is in R and in S.
- The sum of the number of times x is in R and in T.
## Exercise 4.6.5(a)

For sets, we observe that element x is in the left side(R INTERSECT S) - T if and only if it is in both R and S and not in T. The same holds for the right side

R INTERSECT (S-T) so as sets, the equivalence holds.

Now suppose we have bags. Let R = {x}, S = {x,x}, and T = {x}. Then R INTERSECT S = {x}, and the left side is {x}-{x}, or EMPTYSET.

However, on the right, S-T = {x}, so the right side is {x} INTERSECT {x}, which is {x}.