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 |

The computation of the number of superkeys is exactly the same as a
problem on HW2; it uses the principle of inclusion/exclusion.
That is, there are 4 superkeys containing *ABC*, 8 superkeys
containing *CD*, and 2 superkeys containing all of *ABCD*.
Thus the number of superkeys is 4+8-2 = 10.

A | B | C |
---|---|---|

a | b | c |

a | b | d |

On the other hand, ``E/R-style'' wins when we have a query about attributes that can belong to two or more classes, for ODL-style will then require us to look in several relations, while E/R-style lets us look only in the superclass. Choice (b) is the only one that meets this description, so it is the answer to Problem 6.

Note that choice (c) is easy in either database schema.

Equation (b) gets the naming of attributes right, but the left side computes R-S, while the right side computes S-R.

However, (c) is a true statement; it expresses the relationship between the natural join and a similar equijoin.

Abstractly, I is saying that x and y are cousins if they have
*some* parents that are not the same.
More concretely, here's a family history that is bizarre but legal in
most states.
Sally and Sue are sisters; let Gus be their common father.
Joe marries Sally and has child Alice.
Joe later divorces Sally and marries Sue (and opens a bar --- but that's
another story).
Joe and Sue have child Bob.
Now Alice and Bob are siblings; they have common parent, Joe.
Thus, they are *not* cousins according to the problem statement (or
in real life).
However, rule I lets us deduce `Cousin(Alice,Bob)` if we let x =
Alice, y = Bob, xp = Sally, yp = Sue, and z = Gus.

The problem with II is more subtle; it is a confusion of ``there
exists'' with ``for all'' akin to the trouble with the Datalog rule in
Problem 10(I).
Suppose Sue manages Sally and Joe.
We do not want to produce Sue's ID among the answers, because she
*does* manage a Sally.
However, when the `Emps` tuple in the outer query, say t, is the
tuple for Joe, then the where-condition of the outer query is true.
That is, `EmpID`, being the employee ID of Joe, will not be equal
to any Id of an employee named Sally.
Thus, Sue's ID, the one in the `mgrID` field of tuple t, gets
printed.

I fails because it makes the dual of the mistake from Problem 18(I):
here there is an attempt to use a noncollection in a place (the
from-clause) where a collection is required.
That is, `p.playsFor` is not a collection and thus cannot be used
where it appears in query I.

The easiest way to verify that (d) has a lossless join is first to consider the join of AB and ACE. Since A->CE, our theorem about a lossless join if the common attributes functionally determines one side or the other, tells us that the decomposition of ABCE into AB and ACE is lossless. Now, consider the join of ABCE with BCD. The intersection, BC, functionally determines D, so this join is also lossless. Now, we know that the join of AB, BCD, and ACE is lossless, so if you have faith in your reasoning you just mark (d) and go on to the next question.

However, if you want the sanity check of making sure that none of the
other choices could be right, there is a trick that generalizes the argument
we used to prove that theorem about when the join of two relations is
lossless.
Start with a tuple that appears in the result of the join, say
*abcde*.
Argue that there must be tuples in each of the decomposed relations that
agree with it in appropriate attributes and have some other values
elsewhere.
Then use the FD's to try to infer that certain unknown symbols must be
equal and eventually to infer that one of these tuples is really
*abcde*.
If you cannot prove that, after applying all FD's in all possible ways,
**then you have a counterexample**.
That is, you have a set of tuples that could be the original relation,
and when you project it onto the decomposed relations, and rejoin, you
get a tuple *abcde* that you did not have before.

Let's see how this applies to choice (c); you can try it with (a) and
(b) yourself.
The three tuples in relation ABCDE whose projections onto AC, CE, and
BCD yields *abcde* in the join must look like:

A | B | C | D | E |
---|---|---|---|---|

a | b' | c | d' | e' |

a' | b'' | c | d'' | e |

a'' | b | c | d | e'' |

A | B | C | D | E |
---|---|---|---|---|

a | b' | c | d' | e |

a' | b'' | c | d'' | e |

a'' | b | c | d | e |