Multivalued dependencies and 4NF

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What does 3NF synthesis guarantee? from Lesson 4.4.6
2. State BCNF. from Lesson 4.4.4
3. What is the Cartesian product of {a, b} and {x, y}? from Lesson 0.2.2

1 · The Hook

A course has several teachers and several textbooks, and every teacher uses every textbook of the course. The table COURSE_INFO(course, teacher, book) has key (course, teacher, book): all attributes. No non-trivial FD holds, so it is in BCNF. Yet adding one new textbook means inserting a row for every teacher. The redundancy is real but invisible to FDs. It is a multivalued dependency.

2 · Predict First

A third textbook "Date" is adopted for DBMS. How many rows must be inserted? Could you instead store the teachers and the books in two separate tables?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

2 rows (one per teacher). Yes: COURSE_TEACHER(course, teacher) and COURSE_BOOK(course, book), joined on course, give back exactly the table, because teachers and books are independent of each other given the course.

Multivalued dependency (MVD)

X →→ Y ("X multidetermines Y") holds on R if, whenever two tuples agree on X, the tuples obtained by swapping their Y-values also exist. In words: the set of Y-values for an X-value is independent of the rest of the attributes (Z = R − X − Y).

course →→ teacher (and then also course →→ book): for DBMS, the teachers {Rao, Mehta} pair with every book {Korth, Navathe}.

Facts:

• Complementation: if X →→ Y then X →→ (R − X − Y).
• Every FD is an MVD: X → Y implies X →→ Y.
• Trivial MVD: Y ⊆ X, or X ∪ Y = R.

Fourth normal form (4NF)

R is in 4NF if for every non-trivial MVD X →→ Y, X is a superkey.

4NF ⊂ BCNF (every FD is an MVD, so the BCNF condition is included). COURSE_INFO is in BCNF but not 4NF: course →→ teacher is non-trivial and course is not a superkey.

Decomposing into 4NF

Split on the violating MVD X →→ Y: R₁ = X ∪ Y, R₂ = X ∪ (R − X − Y). For COURSE_INFO: (course, teacher) and (course, book). The decomposition is lossless exactly because the MVD holds: {R₁, R₂} is lossless iff R₁ ∩ R₂ →→ R₁ (or →→ R₂), the MVD version of the binary test.

Beyond 4NF (mention only)

5NF (project-join normal form) handles join dependencies: tables that can be rebuilt only from three or more projections. GATE has not tested 5NF in detail.

4 · Visual

COURSE_INFO (BCNF, not 4NF)               4NF
DBMS Rao   Korth                           COURSE_TEACHER        COURSE_BOOK
DBMS Rao   Navathe                         DBMS Rao              DBMS Korth
DBMS Mehta Korth                           DBMS Mehta            DBMS Navathe
DBMS Mehta Navathe                         (2 rows)              (2 rows)
(teachers x books = 4 rows)                add a book: 1 row, not one per teacher

5 · Worked Examples

Example 1 Easy

Is every relation in 4NF also in BCNF?

Solution

Yes. Every FD is an MVD, so a 4NF relation's FDs also have superkey left sides.

Example 2 Medium

A course has 3 teachers and 5 books, all independent. How many rows does the combined table need for that course, and how many in the two 4NF tables together?

Solution

Combined: 3 × 5 = 15. 4NF: 3 + 5 = 8.

Example 3 GATE

EMP(ename, project, skill): an employee's projects and skills are independent. Which MVDs hold and what is the 4NF decomposition?

Solution

ename →→ project and ename →→ skill. 4NF: (ename, project), (ename, skill).

8 · Connect the Dots

Chapter 4.4 is complete: 1NF to 4NF and the algorithms. Next: the Chapter 4.4 Lock-in and the Phase 4 checkpoint, then Phase 5: how tables are actually stored on disk and found quickly with indexes.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — MVD

Which is always true?

1. (A) Every FD is an MVD
2. (B) Every MVD is an FD
3. (C) MVDs and FDs are unrelated
4. (D) A relation in BCNF is in 4NF

Q2 · NAT · 2 mark(s) — Rows

A course has 4 teachers and 6 books, independent of each other. How many rows describe it in the single table (course, teacher, book)?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — 4NF

R(course, teacher, book) with course →→ teacher and no FDs. R is:

1. (A) in BCNF but not 4NF
2. (B) in 4NF
3. (C) not in 1NF
4. (D) not in BCNF

Q4 · MCQ · 2 mark(s) — Complementation

In R(A, B, C, D), A →→ B holds. Which MVD must also hold?

1. (A) A →→ CD
2. (B) B →→ A
3. (C) A →→ C only
4. (D) CD →→ A

Q5 · MSQ · 2 mark(s) — Decomposition

For R(course, teacher, book) with course →→ teacher, which decomposition is lossless and in 4NF?

1. (A) (course, teacher, book) unchanged
2. (B) (course, teacher), (course, book)
3. (C) (course, teacher), (teacher, book)
4. (D) (teacher, book), (course, book)

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

multivalued dependency (MVD) →→complementation ruletrivial MVDfourth normal form (4NF)join dependency / 5NF (mention)