CS145 Midterm Solutions

Index

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15

Problem 1: (d)

The schemas aren't even the same. Q1 produces tuples with three components and Q2 produces tuples with four components, so their results are different whenever the join is nonempty.

Problem 2: (a)

Whether you throw out the tuples with A other than 1 before or after the join doesn't matter. The result is still the join of all tuples in R and S that match in B and have A = 1.

Problem 3: (c)

The difference is seen if a tuple of R joins with several tuples of S, say (a,b) in R and (b,c1) and (b,c2) in S. Q1 will produce two copies of a from these two tuples. However, Q2 will look at the tuple (a,b) of R once, decide that it meets the condition of the where-clause, and produce one copy of a.

Problem 4: (a)

In each case, one copy of every tuple in R is produced.

Problem 5: (d)

Normally, the number of distinct values of B will not be the same as the number of tuples (unless B is a key). Thus, the tuples produced by the same query are normally different.

Problem 6: (a)

Q1 obviously produces delta(R) (in relational-algebra terms). However, since duplicate-elimination is the default for intersection, so does Q2.

Problem 7: (d)

Many people thought that T was redundant. I assume they imagined that T was necessarily the composition of R and S. However, there is nothing in the E/R model that requires it, nor should there be. T can in general map an A-entity to a completely different C entity from what you would get by following R then S. Put another way, if we didn't tell you what pairs were in relationship T, but let you see all the other entity sets and relationships, you couldn't figure out anything about what T was.

Others thought R was redundant. I assume that was because you remembered that when converting to relations, R goes away. However, the reason it goes away is because we introduce a relational structure, namely the relation for A, that includes the information of R.

Problem 8: (b)

The database schema is A(a,b,d), B(b,e), C(c,f), S(b,c), and T(a,b,c).

Problem 9: (c)

(0,1,4) has to be there, because we get it by flipping the middle components of (0,1,2) and (0,3,4).

(0,3,4) has to be there, because we said it was.

However, there is no reason (0,5,2) has to be there. For instance, we can add to the three given tuples the tuples (0,1,4) and (0,3,2), and the resulting five tuples satisfy the MVD but do not include (0,5,2).

Problem 10: (a)

Because they don't appear on the right of any FD, A and E must be in any key. However, it is easy to check that AE^+ = ABCDE, so AE is the only key. A number of people during the exam appeared to forget that in the relational model, keys are minimal, and we use ``superkey'' if we mean ``superset of some key.''

Problem 11: (d)

Here are the closures of the left sides of the four choices: AC^+ = ABCD, AE^+ = ABCDE, BC^+ = BCD, CE^+ = CE. Thus, only in case (d) is the right side not in the closure of the left side.

Problem 12: (b)

First, we should figure out the key(s) for BCDE. Surely E is in any key, because it is not on the right of any FD. Once E is known to be in any key, there is no reason to consider C as a member of a key, because we can always ``get'' C by using the FD E->C. Thus, we need consider only E plus B or D or both. It is then easy to check that BE is a key, but DE is not, so BE is the only key.

Thus, (a), (c), and (d) are eliminated, because they each violate BCNF. Choice (b), BE->D, does not violate BNCF, and is easily seen to follow from the given FD's.

Problem 13: (a or b)

This turned out to be a flawed problem. I intended the answer to be (b), a clearly correct fragment. I also intended line (1) to have an error: missing mode. However, because IN is the default, there is nothing syntactically wrong with this statement, so (a) is also a correct answer.

The assignment statement of line (9) is wrong, because PSM uses the diction SET ... = .... Of course PL/SQL uses the :=, and both lines (4) and (9) are good PL/SQL.

Line (10) is incorrect, because in PSM, the while-statement has to end with END WHILE.

Problem 14: (c)

(a) violates the primary-key constraint for S and will be rejected.

(b) violates the foreign-key constraint. That is, (b) results in deletion of (5,3) from T, but that tuple is necessary because of (3,5) in S.

However, (c) causes no violation to be detected. That is, deletion of (3,6) from T does not affect the foreign-key situation, because there is no tuple in S with d = 3. It does cause (3,5) in S to violate the check-constraint, but this constraint is never checked on a deletion (let alone on any modification at all that takes place in another relation), so the constraint checker will not complain.

Problem 15: (b)

Let's call the three tuples of T by u, v, and w, in that order, and call the tuples of S by x, y, and z, in order. Let aqqb mean that the deletion of tuple a must precede the deletion of tuple b. Then we have the following precedences:

x<u and y<u because of the foreign-key constraint and value 1.
t<w because of the foreign-key constraint and value 5.
t<v because of the check-constraint (6 in v is the only b-value bigger than 5 in t). Note that the check-constraint is not checked during deletions, but the question clearly asks that there be no violation, whether or not the violation is caught.
x and y must each precede at least one of v and w (because of the check constraint).

If we look at only the first three conditions, then we can think of three places in the order chosen for x, y, and u, while the other three places go for t, w, and v. There are {6 choose 3} = 20 ways to divide the six places. Among those devoted to x, y, and u, the latter has to be last, but x and y can be ordered 2 ways. Similarly, among the positions for t, w, and v, tuple t must be first, and the other two can appear in 2 different ways. That makes a total of 20 * 2 * 2 = 80 orders that satisfy conditions (1)-(3).

Now, what about condition (4)? We claim the only way that condition can be violated when the other conditions are satisfied is if the two last positions are assigned to x, y, and u. For then, even though u will be last, one of x and y has to be in 5th position and therefore follow both v and w. However, as long as t, w, and v get either the 5th or 6th position, one of v and w will occupy one of the last two positions. Since u has to follow x and y, it is not possible that either x or y is as late as position 5, and therefore, one of v and w will follow each of them. We conclude that among the 20 ways to divide the six positions between xyu and tvw, only the 4 in which xyu gets positions 5, 6, and one other, will result in violating condition (4). The number of these orders is 4 * 2 * 2; the factors of 2 are because we can still choose a relative order for x and y within the three positions for xyu, and we can choose a relative order for v and w within tvw.

The final answer is thus 80 - 16 = 64.