optimization. One of the benefits one gets from constructing ``trees'' for queries is the ability to combine nodes that represent common subexpressions.

Exercise 5.2.7

The relation that results from the natural join has only one attribute

from each pair of equated attributes. The theta-join has attributes for both, and their columns are identical.

Exercise 5.2.9(a)

If all the tuples of R and S are different, then the union has n+m tuples, and this number is the maximum possible.

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.

Exercise 5.2.10

In the following we use the name of a relation both as its instance (set of tuples) and as its schema (set of attributes). The context determines uniquely which is meant.

PI_R(R JOIN S) Note, however, that this expression works only for sets; it does not preserve the multipicity of tuples in R. The next two expressions work for bags.

R JOIN DELTA(PI_{R INTERSECT S}(S)) In this expression, each projection of a tuple from S onto the attributes that are also in R appears exactly once in the second argument of the join, so it preserves multiplicity of tuples in R, except for those that do not join with S,

which disappear. The DELTA operator removes duplicates, as described in Section 5.4.

R - [R - PI_R(R JOIN S)] Here, the strategy is to find the dangling tuples of R and remove them.

Solutions for Section 5.3

Exercise 5.3.1

As a bag, the value is {700, 1500, 866, 866, 1000, 1300, 1400, 700, 1200, 750, 1100, 350, 733}. The order is unimportant, of course. The average is 959.

As a set, the value is {700, 1500, 866, 1000, 1300, 1400, 1200, 750, 1100, 350, 733}, and the average is 967. H3>Exercise 5.3.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 5.3.4(h)

As sets, element x is in the left side R 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 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.

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.

Exercise 5.3.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}.

Solutions for Section 5.4

Exercise 5.4.1(a)

{(1,0,1), (5,4,9), (1,0,1), (6,4,16), (7,9,16)}.

Exercise 5.4.1(c)

The result is the list [(0,1), (0,1), (2,3), (2,4), (3,4)].

Exercise 5.4.1(e)

{(0,1), (2,3), (2,4), (3,4)}.

Exercise 5.4.1(g)

{(0,2), (2,7), (3,4)}.

Exercise 5.4.1(k)

A B C