FUNDAMENTAL DATABASE

Fundamental Database

Fundamental Database

Problem 1

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:

{A, B, D}+ ( {A, B, C, D, ...