Use the schema R in the following questions:



R = (ABCDEFGH, {BE ? GH, G ? FA, D ? C, F ? B})

(a) What is a key of R?
(b) What is the attribute closure of GH ?
(c) Can there be a key that does not contain D? If such a key exists, give it; otherwise explain why it is not possible.
(d) Is the schema in BCNF? Give the reason for your answer.
(e) Use one cycle of the BCNF synthesis algorithm to decompose R into two sub-relations. For each sub-relation, explain whether or not it is in BCNF.
(f) Give the general condition that guarantees that a decomposition is lossless. Apply the condition to your decomposition to show whether or not it is lossless.
(g) Give the general condition that guarantees that a decomposition is dependency preserv- ing. Apply the condition to your decomposition to show whether or not it is dependency preserving.
(h) * Consider a schema (R, ), where R is a set of attributes and is a set of functional dependencies. Assume further that

(a) What is a key of R?

Solution:

BED or DEG or FED

(b) What is the attribute closure of GH ?

Solution:

(GH)+ = GHFAB

(c) Can there be a key that does not contain D? If such a key exists, give it; otherwise explain why it is not possible.

Solution: No - since D is not uniquely determined by any other set of attributes, it must be a part of the key (since the key uniquely determines all attributes).

(d) Is the schema in BCNF? Give the reason for your answer.

Solution:

No - none of the LHSs are superkeys.

(e) Use one cycle of the BCNF synthesis algorithm to decompose R into two sub-relations. For each sub-relation, explain whether or not it is in BCNF.

Solution:

Four possible decompositions are.

i. R1 = (ABDEFGH, {BE?GH, G?FA, F?B} )

R2 = (DC,{D?C} )

R2 is in BCNF since D is a key. R1 is not in BCNF since the LHS of all FDs are not keys.

ii. R3 = (BCDEGH, {BE?GH, D?C} )

R4 = (GFA, {G?FA} )

R4 is in BCNF since G is a key. R3 is not in BCNF since neither BE or D is a key.

iii. R5 = (ACDEFGH, {G?FA, D?C} )

R6 = (FB, {F?B} )

R6 is in BCNF since F is a key. R5 is not in BCNF since neither D or G is a key.

iv. R7 = (ABCDEF, {F?B, D?C} )

R8 = (BEGH, {BE?GH} )

R8 is in BCNF since BE is a key. R7 is not in BCNF since neither F nor D is a key.

(f) Give the general condition that guarantees that a decomposition is lossless. Apply the condition to your decomposition to show whether or not it is lossless.

Solution:

(intersection of attribute sets of two components)?(key of one component) In all four decompositions the intersection of the attribute sets is the key of one of the components.

(g) Give the general condition that guarantees that a decomposition is dependency preserv- ing. Apply the condition to your decomposition to show whether or not it is dependency preserving.

Solution:

If L is the set of FDs in R and L1 and L2 are the sets of dependencies in the components then L+ = (L1 U L2)+ In the first decomposition L = L1 U L2 so the condition holds. The condition is not true for the other decompositions. For example, in the last decomposition we see that the attribute closure of G using {F B, D?C, BE?GH} does not contain FA (it is just G).

(h)

every dependency in has the form X Y, where the left-hand side, X, consists of a single attribute. For instance, B CD, where B, C, D are attributes, would be an acceptable dependency.

• There is an attribute, A0 ? R, which does not belong to any key of the schema.

i. Prove that if this schema is in the Third Normal Form (3NF) then it is also in Boyce- Codd Normal Form (BCNF).

ii. Find a relation that satisfies all the assumptions above except the assumption about the existence of A0, which is in 3NF, but not in BCNF.

Solution:

(a) Suppose, to the contrary, that the schema is not in BCNF. Then there must be an FD of the form X ? C ? F + such that X is not a superkey, C ? K, for some key K.

(b) The relation over the attributes ABCD with the FDs A ? B, B? A, C?D, D?C. Here the keys are AC and BD. Each of the above FDs violates BCNF, but satisfies 3NF.