Questions: Multivalued Dependencies and Fourth Normal Form

Question 1

A table has schema (Course, Instructor, Textbook). Course CS101 has instructors {Smith, Jones} and textbooks {Algorithms, Data Structures}. How many rows must this table contain for CS101?

• A. 2 rows — one per instructor, with textbook nullable
• B. 2 rows — one per textbook, with instructor nullable
• C. 4 rows — every instructor-textbook combination must appear
• D. 3 rows — one for the course plus one per instructor and one per textbook

Answer: (C)

Because instructors and textbooks are independently associated with the course (not with each other), the table must store every combination to avoid implying false associations. With 2 instructors and 2 textbooks, that's 2×2 = 4 rows. This cross-product explosion is caused by storing two independent multivalued dependencies in a single relation. 4NF decomposition eliminates this: split into (Course, Instructor) with 2 rows and (Course, Textbook) with 2 rows.

Question 2

A table with schema (Employee, Skill, Language) is in BCNF. You notice that an employee's skills and languages are assigned independently. What should you do?

• A. Nothing — BCNF is the highest practically relevant normal form
• B. Decompose into (Employee, Skill) and (Employee, Language) to achieve 4NF
• C. Add a foreign key linking Skill to Language to establish a functional dependency
• D. Combine Skill and Language into a single composite attribute

Answer: (B)

Independent multivalued dependencies (Employee →→ Skill and Employee →→ Language) cause cross-product redundancy that BCNF cannot detect — BCNF only addresses functional dependencies. The fix is decomposition into two relations, each recording one independent fact. Adding a foreign key (option C) would create a false dependency that doesn't exist. Option A is wrong because BCNF is insufficient when independent MVDs are present.

Question 3

A relation that is in BCNF can seldom have update anomalies.

• T. True
• F. False

Answer: False

BCNF eliminates anomalies caused by functional dependencies, but multivalued dependencies create a different kind of anomaly that BCNF cannot detect. In a table with independent MVDs (like Course-Instructor-Textbook), adding a new instructor requires adding one row per textbook — an update anomaly driven by the cross-product structure. Only 4NF addresses this. BCNF is necessary but not sufficient for eliminating all redundancy-based anomalies.

Question 4

The multivalued dependency A →→ B means that for each value of A, the set of B values is determined by A alone, independently of other attributes in the relation.

• T. True
• F. False

Answer: True

This is the definition of an MVD: A →→ B means the set of B values associated with a given A value is independent of the other attributes. In the Course-Instructor-Textbook example, Course →→ Instructor means the set of instructors for CS101 is determined by the course alone, not by which textbook is also in the row. This independence causes the cross-product explosion — the sets for A →→ B and A →→ C must be listed in every combination.

Question 5

Explain why BCNF normalization is insufficient to eliminate all redundancy caused by multivalued dependencies, using a concrete example.

Model answer: BCNF only catches violations caused by functional dependencies (where a non-key attribute determines another). In a relation like (Course, Instructor, Textbook), the key is {Course, Instructor, Textbook} and no non-key determines another — no FD is violated, so BCNF is satisfied. But if CS101 has 3 instructors and 4 textbooks independently, the table must store 12 rows. Adding a new textbook means adding 3 rows (one per instructor) — a redundancy-driven update anomaly that BCNF misses entirely because it stems from independent MVDs, not FDs.

The conceptual gap is that BCNF addresses single-valued facts (one value per key), while MVDs address multi-valued facts (sets per key). When two independent multi-valued facts share a table, they multiply. 4NF catches this by requiring every non-trivial MVD's determinant to be a superkey, and decomposition separates the independent facts into tables where each row represents exactly one association.