1

"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?

1
  • Where did you get these 1 and 2? They don't seem to be the definition of 3NF. Consider relation R with 3 attributes ABC and the only key being A. Then BC->B is an FD that holds but 1 or 2 are not. Commented Jan 9, 2017 at 13:10

1 Answer 1

2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.