Relation R with an associated set of functional dependencies, F, is decomposed…

2024

Relation R with an associated set of functional dependencies, F, is decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is

  1. A.

    Zero

  2. B.

    More than zero but less than that of an equivalent 3NF decomposition

  3. C.

    Proportional to the size of F+

  4. D.

    Indeterminate

Attempted by 4 students.

Show answer & explanation

Correct answer: A

CONCEPT: Boyce-Codd Normal Form (BCNF) requires that for every non-trivial functional dependency X -> Y holding in a relation, X must be a superkey of that relation. A superkey on the left-hand side of every dependency is exactly the structural condition that prevents a functional dependency from forcing any attribute value to be duplicated across rows.

APPLICATION: When relation R (with functional dependencies F) is decomposed into BCNF, each of the resulting relations individually satisfies this superkey condition for all its non-trivial dependencies. So in every decomposed relation, no value can be repeated purely as a consequence of a functional dependency -- the redundancy that functional dependencies could otherwise cause is completely removed. The correct option is therefore Zero.

CROSS-CHECK: Contrast this with 3NF, which allows a dependency X -> Y where X is not a superkey provided Y is a prime attribute (part of some candidate key) -- so a 3NF decomposition can legitimately retain some FD-based redundancy that BCNF eliminates. This is exactly why BCNF is considered strictly stronger than 3NF on this dimension, and it rules out any answer that describes the redundancy as merely reduced, as scaling with the number of dependencies in F+, or as undetermined -- the elimination is unconditional and follows purely from the BCNF definition, for any valid decomposition. (Note: this result covers only redundancy traceable to functional dependencies; BCNF decompositions can still carry redundancy caused by other dependency types, such as multivalued dependencies, which is a separate consideration outside this question's scope.)

Explore the full course: Computer Science

Loading lesson…