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 0 1 NULL 2 3 4 2 3 4 0 1 NULL 2 4 NULL 3 4 NULL Exercise 5.4.2(a)
When a relation has no duplicate tuples, DELTA has no effect on it. Thus, DELTA is
idempotent.
Exercise 5.4.2(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 5.4.3
If we use set semantics, it is not hard to get the effect of PI_{A,A} using only the operators of Section 5.1. 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 0's in different components without using a product. However, then we get at least four identical tuples (or none, if we have eliminated the 0's) with two 0'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 components.
Solutions for Section 5.5
Exercise 5.5.1(a)
SIGMA_{speed<1000 AND price>1500} (PC) = EMPTYSET
Exercise 5.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.
Database Systems: The Complete Book
Solutions for Chapter 6
Revised 11/3/01.
Solutions for Section 6.1
Exercise 6.1.1
If they are two different attributes, there will be a comma between them. Remember, in SQL, two names with no punctuation between them usually indicates that the second is an alias for the first.
Exercise 6.1.2(a)
SELECT address FROM Studio
WHERE name = 'MGM';
Exercise 6.1.2(c)
If you interpret the question as asking only that Love appear as a substring, then the following is OK: SELECT starName FROM StarsIn
WHERE movieYear = 1980 OR movieTitle LIKE '%Love%';
However, another reasonable interpretation is that we want the word Love as a word by itself. The query above returns stars of a movie like The Cook, the Thief, His Wife, and Her Lover. To identify only titles that have Love as a word by itself, either at the beginning, the middle, the endor as the entire title, we need to use four patterns. The following query works; notice the judiciously placed blanks in the patterns. SELECT starName FROM StarsIn
WHERE movieYear = 1980 OR
movieTitle LIKE 'Love %' OR movieTitle LIKE '% Love %' OR movieTitle LIKE '% Love' OR movieTitle = 'Love';
Exercise 6.1.3(a)
SELECT model, speed, hd FROM PC
WHERE price < 1200; The result:
model speed hd 1001 700 1004 866 1008 700 1010 750 1012 350 10 10 30 30 7 Exercise 6.1.3(b)
SELECT model, speed AS megahertz, hd AS gigabytes FROM PC
WHERE price < 1200;
Exercise 6.1.3(e)
SELECT * FROM Printer WHERE color; The result:
model color type price 3001 true ink-jet 231 3002 true ink-jet 267 3004 true ink-jet 439 3005 true bubble 200 3006 true laser 1999 Exercise 6.1.5(a)
All tuples where either a is 10 or b is 20, or both. There is no restriction on where NULL may appear, except for the above condition.
Exercise 6.1.5(d)
All tuples where a and b have the same, nonnull value.
Solutions for Section 6.2
Exercise 6.2.1(a)
SELECT name
FROM MovieStar, StarsIn WHERE gender = 'M' AND name = starName AND
movieTitle = 'Terms of Endearment';
Exercise 6.2.1(d)
SELECT M1.title
FROM Movie AS M1, Movie AS M2
WHERE M2.title = 'Gone With the Wind' AND M1.length > M2.length;
Exercise 6.2.2(a)
SELECT maker, speed FROM Product, Laptop WHERE hd >= 30 AND
Product.model = Laptop.model;
Exercise 6.2.2(b)
We need to join Product with each of the other three relations and take the union. (SELECT Product.model, price FROM Product, PC
WHERE Product.model = PC.model AND maker = 'B') UNION
(SELECT Product.model, price FROM Product, Laptop
WHERE Product.model = Laptop.model AND maker = 'B') UNION
(SELECT Product.model, price FROM Product, Printer
WHERE Product.model = Printer.model AND maker = 'B');