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:

1. It is different from K_i.
2. Its intersection with K_i is non-empty.

   This can be shown as follows.    

1. Assume that (K_i - {A}) + X = K_i. Since A is in K_i it follows that X must be a superset of {A}. But this implies that X -> A is trivial which leads to a contradiction. The assumption that (K_i
   • {A}) + X = K_i must therefore be false.
2. Assume that the intersection of K_i and (K_i - {A}) + X is empty. It then follows that K_i = {A} and therefore that (K_i - {A}) + X
   • ({A} - {A}) + X = X is a candidate key. But this implies that X is a superkey which leads to a contradiction. The assumption that the intersection of K_i and (K_i - {A}) + X is empty must therefore be false.

   It follows from a. and b. that ther are at least two candidate keys    such that these have an overlap.

QED

-- 
  Jan Hidders