CS145 Final Exam Solutions
Index
Problem 1: (d)
I threatened to put this on the exam, and here it is problem #1.
In general, ALL is a more stringent requirement than ANY, so we expect
that Q1 is contained in Q2.
However, if SELECT c FROM S
is empty, then it is impossible to satisfy ANY, while ALL
is trivially satisfied.
Then, Q2 is contained in Q1.
Since both containments could be proper, the queries are different.
Problem 2: (d)
Notice that the FROM and WHEREclauses of the queries are the same when
you swap r1 and r3.
Thus, they will produce the same answers but with the columns and
columnheaders swapped.
To see that the relations are different, we have only to find an example
where the result is not the same when columns are swapped.
For example, if we take R(a,b) = {(0,1), (2,1), (2,3)}, then the answer
to Q1 is {(0,2), (2,2), (2,2)} and the answer to Q2 is {(2,0), (2,2),
(2,2)}.
When computing the answer, don't forget to consider the possibility that
some of r1, r2, and r3 may refer to the same tuple.
Note: several people answered (a) but pointed out that the results
differed in the order of columns.
While this difference is significant (try substituting one of these
queries for the other in an INSERT statement, for example) I
accepted that answer, since it indicated that you had understood what
the queries were doing.
Problem 3: (b)
Q1 produces those (x,y) pairs from R such that x is not in S and y is not
in T.
Q2 produces those (x,y) pairs from R such that it is not true that both
x is in S and y is in T; i.e., either x is not in S or y is not in T.
Thus, everything produced by Q1 is also produced by Q2.
Problem 4: (c)
Q1 produces avalues that appear in some tuple of R and some tuple of S.
Q2 produces avalues that appear in the same tuple in R and S.
Thus, everything in Q2 is surely in Q1.
Problem 5: (a)
These both produce the set of C's that are related to a B that is
related to an A named Sue.
Problem 6: (d)
This one is so tricky that I actually had the wrong answer, and didn't
discover my error until I surveyed a random sample of answers and saw
that people were preferring another answer.
Q1 produces the set of C's that are related to a B that is related to an
A named Sue.
However, because of the way it is stated, a C that is related two
n B's that are each related to an A named Sue will appear in the
output bag n times.
Notice that aName is not a key for A, so there is nothing wrong
with there being many A's named Sue.
Q2 is more liberal than Q1 in that it will produce a C in the answer as
long as there is any B related to an A named Sue.
Thus, as sets, Q1 is contained in Q2.
However, OQL produces bags, and Q2 can never produce the same C object
more than once.
Q1, however, can produce it many times.
To see that Q1 and Q2 are different, consider the following objects:

There are A objects a1 and a2.

a1 is named Sue; a2 is not.

There are B objects b1, b2, and b3, and C objects c1 and c2.

b1 is related to a1 and c1; so is b2.
b3 is related to a2 and c2.
Then Q1 produces c2 not at all, but produces c1 twice  once for the
combination cc = c1 and bb = b1, the second time for the combination cc
= c1, bb = b2.
On the other hand, Q2 produces c1 once and c2 once.
Problem 7: (c)
Another subtle one.
Roughly, each query produces the bag of integers that are the counts of
the sets of B's that are related to a single A.
The difference is that Q1 also may produce some 0's if there are A's
that are related to empty sets of B's.
However, Q2 never looks at those A's and only produces the counts of the
nonempty groups of B's.
Problem 8: (a)
These queries each produce the set of pairs of nodes between which a
path exist.
It is more traditional to write the recursive rules with the order of
subgoals reversed, e.g.,
Path(x,y) < Arc(x,z) & Path(z,y)
in Q1.
Problem 9: (a)
Each of these modifications has the effect of replacing every tuple of
the form (a,3) for some a by the tuple (a,2).
If such a tuple appears more than once in R, the count is preserved as
well.
Problem 10: (c)
Q1 finds tuples where the acomponent has the substring
NULL.
However, Q2 only finds tuples where that substring appears at either the
beginning or the end.
Problem 11: (c)
Q1 produces the largest element of R as many times as it appears in R.
Q2 produces the same element, but only once.
Problem 12: (a)
These are the same.
Each groups by a and produces the set of all sizes of these
groups.
A count is produced only once, even if it is the size of several groups.
Notice that it doesn't matter whether we count tuples, as in Q1, or
count the values of a component of those tuples, as in Q2.
Even if a group has duplicate values of b, each such value is
counted.
If we wanted duplicate b's counted only once, we would have to
say
SELECT DISTINCT COUNT(DISTINCT b)
Problem 13: (d)
In the E/R approach, the relation for B has only the attributes
associated with B itself plus the key attribute(s) for the
isahierarchy, which must be found at the root.
Problem 14: (b)
Answer (a) is the schema for objects of type B; (c) is the schema for objects
that are both B's and C's, and (d) is the schema for objects of type A
that are neither B's nor C's.
Problem 15: (b)
The relation for B has only the attributes of B, that is, B(c,d).
The relation for A has the key for A, including the attribute it
``borrows'' from B, plus the other attributes for A, yielding
A(a,b,c).
There is no relation constructed for the supporting relationship R.
Problem 16: (d)
It is entirely possible that (0,1) pops up in the middle of T2's
execution, because although the world has to look serializable from T1's
point of view, the same is not true of T2.
In fact, since T2 does not modify the database, the world will look
serializable to T1 no matter when the two transactions execute.
However, REPEATABLE READ guarantees that if T2 has seen a tuple
once, then it will always see it.
In particular, having seen (2,3) in answer to the first query of T2,
that tuple must be there in response to the second query (which it also
satisfies), even if T1 has deleted it and committed.
Answer (d) is the only one where the second response is not a superset
of the first.
Problem 17: (a)
An easy one: when the privilege is revoked from B, the CASCADE
requires that it be revoked from C as well, because the only way C got
that privilege was through B.
Problem 18: (c)
Answer (a) is wrong because an attributebased check cannot prevent deletions.
Answer (b) is wrong because the foreignkey constraint is in the wrong
direction.
However, (c) is exactly what is needed, since the required constraint is
a statement of what this foreignkey constraint means.
Problem 19: (d)
Answer (a) doesn't make sense; you cannot apply SUM in the
WHEREclause (except in subqueries).
Answer (b) doesn't even address the limit of $1,000,000.
Answer (c) is not quite right.
If an employee is the manager of two departments, then in the group for
the department of that employee in Emps, that employee's salary
counts twice.
Answer (d) is exactly what is needed.
It groups employees by department, sums their salary by departments, and
checks for groups with a sum over $1,000,000.
Problem 20: (a)
Nothing much to this question.
UNKNOWN is the truthvalue of any comparison involving
NULL.
Problem 21: (c)
Notice that the INSERT statement is executed 11 times, for i =
1,2,...,11.
The exit occurs after the insertion on the 11th round.
Thus, (a) is wrong and (c) is a correct statement.
Clearly (b) is wrong, since only teams with scores at most 11 are ever
extracted from Teams or put into NewTeams.
Answer (d) is wrong because the effects of committed modifications on the
database are permanent.
Note that any successful PL/SQL statement is committed at the end, even
if you don't say COMMIT anywhere.
Problem 22: (c)
While it is helpful if score is a key for teams, all that is
really needed is that there be exactly one team for each of the first 11
scores (1 through 11).
We could, for example, have several teams with a score of 12 and yet the
PL/SQL would execute successfully.
Problem 23: (a)
The five (a,b,c,d) tuples in the natural join are
(0,1,2,3), (4,5,2,3), (4,5,6,7), (4,5,10,11), and (4,5,10,3).
Problem 24: (b)
First, let us compute the outer join of R and S.
The natural join has tuples (0,1,2), (4,5,2), (4,5,6), and (4,5,10).
Now, (8,9) is dangling in R, and (13,10) is dangling in S, so we add
(8,9,NULL) and (NULL,13,10).
Then, we must take the outer join of this relation of six tuples with
relation T.
We get the five tuples in the answer to Question 23, of course.
However, tuple (NULL,13,10) joins with (10,11) and (10,3) of T to give
us tuples (NULL,13,10,11) and (NULL,13,10,3).
In addition, (8,9,NULL) is dangling, since the NULL cannot match any
value in T, even another NULL.
Thus, we add (8,9,NULL,NULL), a total of eight tuples.
Problem 25: (d)
Answers (a) and (b) are wrong, since REF cannot be applied to an attribute name
by itself.
Rather, it must be applied to a value, which is a component of a
specific tuple.
Answer (c) is wrong because THE only applies to values of table type.
Answer (d) works; I tried it.
Problem 26: (c)
Think about the five attributes arranged in a circle, with A following
E.
Then the five FD's say that any two adjacent attributes functionally
determine the next around the circle (clockwise, say).
That tells us that any three attributes must have two adjacent ones on
the circle, those determine the attribute clockwise, which (together
with one of the original three) determines the next, and so on.
That is, any three or more attributes is surely a superkey.
However, the five pairs of attributes that are not adjacent on the
circle (the five pairs that are not left sides of given FD's)
are not keys; in fact they don't determine any attributes except
themselves.
Surely the empty set and the five singletons are not superkeys either.
Thus, there are 11 subsets of {A,B,C,D,E} that are not
superkeys, and the remaining 32  11 = 21 are superkeys.
Problem 27: (b)
Here's the trick.
No FD derived from the given FD's can have a singleton left side.
Thus, any projected FD will have to have at least two attributes on the
left, and in order to be nontrivial it will have to have a third
attribute on the right.
Thus, in any threeattribute schema, the left side of a nontrivial FD is
surely a superkey, since it determines three attributes.
Problem 28: (d)
Answer (a) isn't even true for sets.
In fact, the left side is the complement of the right side.
Answer (b) is true for both sets and bags.
For bags, both sides contain an element x as many times as it is
in S plus twice the number of times it is in R.
Answer (c) likewise holds for both sets and bags.
For bags, each side contains x the minimum of the number of times
it appears in R and S.
That count is true for the left side by definition of bag intersection.
To see it holds for the right side, let x appear r times in R and
s times in S.
If r <= s, then x appears r  0 = r times on the right.
If r > s, then x appears r  (r  s) = s times on the
right.
In either case, the number of appearances of x is the smaller of r
and s.
However, (d) is true for sets but not bags.
It is easy to check for sets using Venn diagrams or similar reasoning.
However, for bags, let x appear once in R and once in S.
Then x appears twice on the left and only once on the right.
Problem 29: (b)
If two tuples that agree on A and disagree on B remain in the relation,
then there is sure to be a violation of the MVD.
To see why, not that if we swap different B's, we change by one the
number of 1's in each tuple.
Thus, since all tuples of R
have an even number of 1's, the tuples with B's swapped cannot be in R.
Therefore, there can be only two of the four tuples with A = 0 remaining
and only two of the four tuples with A = 1.
Should there be three from either group, then two would have to differ
in B.
We conclude that 4 tuples is the maximum we can leave.
Problem 30: (b)
If we put one attribute on the left side of a FD, say A > B, then we
can surely find two tuples in R that agree on A and disagree on B.
All we need to know is that after fixing A, we can choose C to be either
0 or 1 so that the sum of the number of 1's among the A, B, and C
components is even.
Then choosing D = 0, we can guarantee that the resulting tuple is in R.
Note that this argument applies equally well to any three attributes, so
we see that given any attribute on the left and any other on the right,
we can find in R two tuples that agree on the left and disagree on the
right.
That is, this FD is not satisfied.
Similarly, if we pick any two attributes on the left and a third on the
right, we can fix the two on the left and find two tuples that disagree
on the right.
For each tuple, pick the fourth attribute to be 0 or 1, whichever makes
the number of 1's in the tuple even.
However, if there are three attributes on the left, then R has only one
tuple with any given combination of values for those attributes, and
therefore the FD must be satisfied.
Thus, only the four FD's with three attributes on the left are
satisfied.
Problem 31: (d)
You don't use the colon in the WHEN clause, but you must in the body of
the trigger.
Problem 32: (d)
This turned out to be surprisingly hard.
Answer (a) is incorrect, because it is not a model.
If you set x = 3 in the second rule, you violate that rule.
That is, the subgoals of the body, B(3) and NOT
P(3), are both true, yet the head, Q(3), is false.
Similarly, (b) is incorrect.
If you set x = 2, you violate the first rule.
Answer (c) is the stratified model, so that is not correct.
However, (d) is a model other than the stratified model.
Even though Q(2) makes no ``sense,'' it doesn't violate anything.
The second rule, with x = 2, has a true head, and thus cannot be
false.
The third rule with x = 2 has a false body, and thus also cannot
be false.
You may check that all the rules are rendered true by each possible
value of x.
Problem 33: (a)
The last problem also fooled a lot of people.
I suspect you were calculating averages so fiercely that you forgot to
check for a primarykey violation.
The sequence of events is as follows:

The insert of Fred succeeds, because his salary is less than the current
average of 20,000.
The new average salary is 18,000, and the total is 72,000.

The update of Sue's salary is rejected because it is higher than the
average.

The insertion of a tuple for Sally is rejected because there is already
a tuple with the key value 'Sally'.

The deletion of Joe's tuple succeeds; neither of the constraints on
Foo affects a deletion.
The total salary is decreased by Joe's 20,000 salary, to 52,000.