【正文】
their columns are identical. Exercise (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 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 . R [R PI_R(R JOIN S)] Here, the strategy is to find the dangling tuples of R and remove them. Solutions for Section Exercise 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. H3Exercise (a) As sets, an element x is in the leftside 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 rightside 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 leftside 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 (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 moment39。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 (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 (ST) 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, ST = {x}, so the right side is {x} INTERSECT {x}, which is {x}. Solutions for Section Exercise (a){(1,0,1), (5,4,9), (1,0,1), (6,4,16), (7,9,16)}. Exercise (c)The result is the list [(0,1), (0,1), (2,3), (2,4), (3,4)]. Exercise (e){(0,1), (2,3), (2,4), (3,4)}. Exercise (g){(0,2), (2,7), (3,4)}. Exercise (k)A B C 0 1 NULL 2 3 4 2 3 4 0 1 NULL 2 4 NULL 3 4 NULL Exercise (a)When a relation has no duplicate tuples, DELTA has no effect on it. Thus, DELTA is idempotent. Exercise (b)The result of PI_L is a relation over the list of attributes L. Projecting this relation onto L has no effect, so PI_L is idempotent. Exercise If we use set semantics, it is not hard to get the effect of PI_{A,A} using only the operators of Section . The idea is to project R onto A, take the product of that relation with itself, and select for equality. As a sequence of steps: R1(A) := PI_A(R) R2(A,A1) := R1 * RHO_{S(A1)}(R1) ANS(A,A1) := SIGMA_{A=A1}(R2)Under bag semantics, it is not possible. The intuitive idea behind the proof is that: Focus on the case when R consists only of two tuples, each of which is (0,1). e neec to produce the result {(0,0), (0,0)}. Since joins can be expressed as products, selections, and projections, let us assume that the only operations used are selection, projection, product, union, intersection, and difference. We can never get a relation with tuples that have two 039。s in different ponents without using a product. However, then we get at least four identical tuples (or none, if we have eliminated the 039。s) with two 039。s. No operation can distinguish among them, so they all survive any operation, or none do. Thus, we can never produce a result with exactly two tuples with two 0 ponents. Solutions for Section Exercise (a)SIGMA_{speed1000 AND price1500} (PC) = EMPTYSETExercise (d)This plex 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,mod