Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: 3NF but not BCNF
Phil Cook wrote:
> I am presented with the following question:
>
> Argue that if a relation schema R is in Third Normal Form but not
> in Boyce-Codd Normal Form with respect to a set of functional
> dependencies F, then it must have at least two distinct keys for
> R with respect to F which overlap, i.e. such that their
> intersection is nonempty.
>
> Unfortunately, my textbook only mentions this point in passing,
> referring to some paper by Vincent and Srinivasan. This paper does
> not appear to be available online, however.
>
> Any explanation would be greatly appreciated.
The proof rests upon the following two Lemmas:
Lemma 1:
If you have a candidate key K and a functional dependency X -> A (with X a set of attributes and A a single attribute) that is left-irreducible (i.e. there is not a FD X' -> A with X' a strict subset of X) then (K - {A}) + X (with '-' the set minus and '+' the set union) is also a candidate key.
For example, if you know that ABC is a candidate key and FD DE->B holds, then ADEC is also a candidate key. (Note that we simply replaced in ABC the B with DE.)
[Note: Proof of this is easy but not trivial.]
Lemma 2:
If a relation is in 3NF but not in BCNF then there will be a left-irreducible FD X -> A such that it is
1. non-trivial, 2. A is in a candidate key and 3. X is not a superkey.
[Note: This is also easy to prove but not trivial. ]
With these lemmas we can prove for a relation in 3NF but not in BCNF there are at least two different candidate keys such that these have an overlap. The general idea of the proof is that we can use the FD of Lemma 1 to derive another candidate key with Lemma 2 that has an overlap with the one that A is in:
Assume that there are only the candidate keys K_1, ..., K_n. Then by Lemma 1 there is a left-irreducible non-trivial FD X -> A such that A is in some candidate key K_i and X is not a superset of any of K_1, ..., K_n.
By Lemma 2 it follows that then (K_i - {A}) + X is also a candidate key. For this candidate key we can show two things:
This can be shown as follows.
It follows from a. and b. that ther are at least two candidate keys such that these have an overlap.
QED
-- Jan HiddersReceived on Tue May 15 2001 - 08:41:29 CDT