Proof that if a relation R is in 3NF and if every key in R is simple, then R is in BCNF?

Question

"A key is simple if it consists of only one attribute". Prove that if a relation R is in 3NF and if every key in R is simple, then R is in BCNF. Your proof should be general, e.g., it should not assume that R has a fixed number of, say two or three, attributes.

Solution:

Consider an FD X -> Y that holds in R. Since R is in 3NF, either

1. X is a superkey or
2. Y is a member of a key.

In the second case, since every key in R is simple, Y is itself a key, which implies that X is a superkey. Therefore, X -> Y does not violate BCNF in either case, which implies that R is in BCNF.

I understand everything except the final part; Y being a key implies X being a superkey. Can somebody elaborate on that?

Answer 1

Interesting question (I happen to be reading the Ullman book right now). I think the answer is something like this:

Assume that X is not a superkey. Then, each attribute in Y is a member of a key (is prime). Since each key consists of one attribute, y -> {every other attribute}, where y is a member of Y. Then by transitivity, X -> {every other attribute}, which implies that X is a superkey. We contradicted our original assumption, that X is not a superkey, hence X must be a superkey.

The most important part of the proof is the transitivity part.