CS145 Midterm Solutions
Index
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 whereclause, 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 relationalalgebra terms).
However, since duplicateelimination 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 Aentity 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 whilestatement has to end
with END WHILE.
Problem 14: (c)
(a) violates the primarykey constraint for S and will be
rejected.
(b) violates the foreignkey 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 foreignkey
situation, because there is no tuple in S with d = 3.
It does cause (3,5) in S to violate the checkconstraint, 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 foreignkey constraint and
value 1.

t<w because of the foreignkey constraint and value 5.

t<v because of the checkconstraint (6 in v is the only
bvalue bigger than 5 in t).
Note that the checkconstraint 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.