Prove that any relation schema with two attributes is in BCNF.
Answer:
Consider a relation schema R={A, B} with two attributes. The only possible (non-trivial) FDs are {A} ( {B} and {B} ( {A}. There are four possible cases:
No FD holds in R. In this case, the key is {A, B} and the relation satisfies BCNF.
Only {A} ( {B} holds. In this case, the key is {A} and the relation satisfies BCNF.
Only {B} ( {A} holds. In this case, the key is {B} and the relation satisfies BCNF.
Both {A} ( {B} and {B} ( {A} hold. In this case, there are two keys {A} and {B} and the relation satisfies BCNF.
Hence, any relation with two attributes is in BCNF.
R(A, B, C) is a relation in BCNF. A is one of the keys of R. R may have other keys.
Prove that R is in 4NF. (10 points) (Hint: Assume that R is not in 4NF. What could the MDs that violate 4NF be? For each such MD, use what you know about the relation to show that this MD cannot violate 4NF.)
Answer:
R = (A, B, C)F = {A ( B, B ( C)
Can be decomposed in two different ways
R1 = (A, B), R2 = (B, C)
Lossless-join decomposition:
R1 ( R2 = {B} and B ( BC
Dependency preserving
R1 = (A, B), R2 = (A, C)
Lossless-join decomposition:
R1 ( R2 = {A} and A ( AB
Not dependency preserving (cannot check B ( C without computing R1
R = (A, B, C )F = {A ( B B ( C}Key = {A}
R is not in BCNF
Decomposition R1 = (A, B), R2 = (B, C)
R1 and R2 in BCNF
Lossless-join decomposition
Dependency preserving
R = (A, B, C )F = {A ( B B ( C}Key = {A}
R is not in BCNF (B ( C but B is not superkey)
Decomposition
R1 = (B, C)
R2 = (A,B)
Consider the universal relation R = {A, B, C, D, E, F, G, H, I} and the set of functional dependencies F = { {A, B} -> {C}, {A} -> {D, E}, {B} -> {F}, {F} ->{G, H}, {D} -> {I, J} }.
What is the key for R? Decompose R into 2NF, then 3NF relations. (15 points)
Answer:
To help in solving this problem systematically, we can first find the closures of all
single attributes to see if any is a key on its own as follows:
{A}+ ( {A, I},
{B}+ ( {B},
{C}+ ( {C},
{D}+ ( {D},
{E}+ ( {E},
{F}+ ( {F},
{G}+ ( {G},
{H}+ ( {H, J},
{I}+ ( {I},
{J}+ ( {J}
Since none of the single attributes is a key, we next calculate the closures of pairs of attributes that are possible keys:
{A, B}+ ( {A, B, C, I},
{B, D}+ ( {B, D, E, F},
{A, D}+ ( {A, D, G, H, I, J}
None of these pairs are keys either since none of the closures includes all attributes. But
the union of the three closures includes all the attributes: