Search code examples
databaseprimary-keyfunctional-dependencies3nfbcnf

R in 3NF if and only if R in BCNF?

Consider a relation R, and a functional dependencies set F ,including only one functional dependency: {X->A}. prove that if R in 3NF iff R in BCNF.

So far, for the <- direction is trivial by definition. But i struggle to the -> direction. What we know about F-closure? from the definition, i need to check for every functional dependency Y->B that in F-closure, that its trivial or Y is superkey. Is there some conclusions on the superkey of R that i'm missing?

Solution

  • Here is a sketch of the proof.

    The fact that a relation schema in BCNF implies that the schema is also in 3NF is due to the definition of 3NF (each determinant is a superkey or implies only prime attributes, and we know that each determinant is a superkeys since the schema is in BCNF).

    So we must show that if the relation is in 3NF, then it is also in BCNF.

    Now consider the only dependency, {X->A}. For the definition of 3NF, either X is a superkey, or A is prime.

    In the first case, if X is a superkey, we know that the schema is also in BCNF.

    So, we need to check only the case in which X is not a (super)key, and A is prime. We can prove that this case is impossible, with the following steps.

    We have only two possibilities, either X contains A, or not.

    1. If X contains A then this dependency is trivial, and, since there are no other dependencies, X is a key, and this violates our hypothesis, so we have a contradiction.

    2. If, on the other hand, X is not contained in A, then X is again a key, and this again contradicts our hypothesis.

    Finally, note that in this proof I have assumed that there are no other attributes in R a part from XU{A}, otherwise those other attributes should be present in any key of the relation, and there should be at least another dependency with them.