1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

31 | 32 | 33 | 34 | 35 |

Added later: A number of people argued with me that it is impossible for
T1 to see one tuple, because the deletion of (1,2) is not committed
until after (5,6) is inserted.
I sort of sympathize, but
the problem is that the standard talks about tuples, as if they were the
elementary units of information. Thus, when step 1a asks for committed
tuples, it does not *have* to see (1,2).
There is no notion of a ``committed absence of a tuple.''

In practice, DBMS's use disk blocks as the elementary unit of
information, e.g., for locking.
Here, the reasoning that ``the absence of (1,2) is uncommitted'' makes
perfectly good sense.
That is, after step 2a, the block containing tuple (1,2) has been
updated --- rather than deleted --- and its new value is uncommitted.
Therefore, at that time T1
could not see that block and *must* see tuple (1,2), probably on
another version of the same disk block (unless T1 gets deferred --- a
likely possibility). As a result, answer (b) was also accepted for
credit.

The deletion (II) will surely be rejected, since it must cause at
least one violation of the foreign-key constraint.
Thus, it will make no change to either *R* or *S*, assuring
that (2) remains in *R*.

However, the following reasoning was shown to me later by one of the
students.
Since *S.b* is referenced by a foreign key, it must be the primary
key of *S*.
Therefore, whenever *S* has more than one tuple, the update will
violate this unseen primary-key declaration and will be rejected.
Thus, in these cases, it will fail to rid *R* of (2).

Because A->->B is given, we know that (a,b2,c1,d1) is also in *R*.
Now, we can apply D->B to (a,b1,c1,d1) and (a,b2,c1,d1) to infer that
b1=b2. That says that if any two tuples agree in *A*, they must
also agree in *B*; i.e., A->B.

Now, C->A and A->B tell us C->B. Also, C->A and C->B tell us C->->AB, and the latter MVD tells us C->->D. Thus, all of (a), (b), and (c) are true, and the answer must be (d).

Shame on people who are still confusing ``key'' with ``superkey.''

Choice (a) is incorrect; it never forces the tuple from *P* to be
``doubled.''
Choice (b) equates the first component of *P* to the second
component of *Q*.
Choice (c) fails to equate the components of *P* to the first
component of *Q*.

In the first two cases, the third rule forces *d* to be in
*N*.
Other nodes could also be in *N*, but all these models are not
minimal; they contain *({a,c}, {d})*, which is the stratified
model.

The third case gives us the minimal model *({a,c,d}, {})*.
In the fourth case, we get *({a,b,c,d}, {})*, and models with some
nodes in *N*, but none of these are minimal; they all contain
*({a,c,d}, {})*.

To check that these queries are not equal, consider a graph with only the arcs 1->2 and 2->3. Q1 produces (1,3), while Q2 doesn't.

Q2 will produce an A-object that is connected to some B's that are connected to ``Joe'' and to at least one B that is not connected to ``Joe.'' However, Q1 will not produce such an A. Thus, Q2 is not contained in Q1.

On the other hand, Q1 will produce an A that is connected to no B's at
all, because the `FOR ALL` is always true when it is applied to
an empty collection.
However, Q2 will not produce such an A.
Thus, neither query is contained in the other.

On the other hand, Q2 produces all the B's that are related to the A named ``Joe,'' regardless of whether those B's are related to any C. Thus, Q2 is properly contained in Q1.

To check that the queries are not equal, let *R = {(1,2)}* and *S
= {(1,3)}*.
Then Q1 produces (1), but Q2 does not.

However, if we remember a similar question from last year's final, we
think ``what if the set is empty.''
Then a value can be bigger than all, but not different from any.
But in this case, when *R* is empty, both queries produce nothing.
Thus, here our first thought turns out to be correct, and Q1 really is
contained in Q2.