Proof that if a relation R is in 3NF and if every key in R is simple, then R is in BCNF? "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 -&gt; Y that holds in R. Since R is in 3NF, either


X is a superkey or
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 -&gt; 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?
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 -&gt; {every other attribute}, where y is a member of Y. Then by transitivity, X -&gt; {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.