Algorithms: 3NF synthesis, BCNF decomposition

0 · Recall Warm-up

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

1. What is the highest NF of R(A, B, C, D) with F = {AB → C, C → D, D → A}? from Lesson 4.4.5
2. Which normal form always allows a lossless, dependency-preserving decomposition? from Lesson 4.4.4
3. Give the three steps of the minimal cover algorithm. from Lesson 4.2.5

1 · The Hook

Knowing a table is in 2NF is not enough: you must produce a better schema. Two standard algorithms do it: 3NF synthesis (lossless and dependency preserving, guaranteed) and BCNF decomposition (lossless, guaranteed; preservation not guaranteed). GATE asks how many tables each produces and whether the result preserves dependencies.

2 · Predict First

R(A, B, C, D, E) with F = {A → B, B → C, CD → E}. Key AD. 3NF synthesis makes one table per FD. How many tables, and is an extra one needed for the key?

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

3 · Core Concept

Predict First — the answer

FD tables: AB, BC, CDE. None of them contains the key AD, so add a table AD. Total 4 tables.

3NF synthesis algorithm

1. Find a minimal cover G of F.
2. For each left side X in G, make a relation with X and all attributes A such that X → A in G (group same left sides).
3. If no relation contains a candidate key of R, add one relation consisting of a candidate key.
4. Remove any relation whose attributes are a subset of another relation's.

Guarantees: every relation is in 3NF; the decomposition is lossless (the key relation glues everything) and dependency preserving (every FD of G sits in its own table).

3NF example

R(A, B, C, D, E), F = {A → B, B → C, CD → E}. Minimal cover = F. Tables: AB, BC, CDE. Key AD is not inside any → add AD. Result {AB, BC, CDE, AD}: 4 relations.

BCNF decomposition algorithm

1. If R is in BCNF, stop.
2. Pick a violating FD X → Y (X not a superkey of R; take Y = X⁺ − X for a bigger, quicker step).
3. Replace R by R₁ = X ∪ Y and R₂ = R − (Y − X). (Lossless: R₁ ∩ R₂ = X, and X → R₁.)
4. Repeat on each piece, using the FDs projected from F⁺ onto that piece.

Guarantees: every piece in BCNF; lossless. Not guaranteed to preserve dependencies. The result can depend on which violation you pick first.

BCNF example

R(A, B, C, D, E), F = {A → B, B → C, CD → E}, key AD.

• Violation A → B, with A⁺ = ABC: split into ABC and ADE (R minus BC).
• ABC: FDs A → B, B → C (key A); B → C violates → split BC and AB.
• ADE: projected FDs: AD → E (since AD⁺ = ABCDE), key AD → BCNF.
• Result {AB, BC, ADE}: 3 relations, lossless. CD → E is not preserved (C and D never together, and AD → E is not enough to derive CD → E).

Comparing the outcomes

4 · Visual

BCNF decomposition tree for R(ABCDE), F = {A->B, B->C, CD->E}

                 ABCDE
          A->B violates (A+ = ABC)
           /                \
        ABC                 ADE     (AD -> E, AD is key: BCNF)
   B->C violates
     /       \
   AB        BC
leaves: AB, BC, ADE      lossless; CD -> E not preserved

5 · Worked Examples

Example 1 Easy

3NF synthesis for R(A, B, C) with F = {A → B, B → C}.

Solution

Minimal cover = F. Tables AB, BC. Key A is in AB. Result {AB, BC}.

Example 2 Medium

BCNF decomposition of R(A, B, C) with F = {AB → C, C → B}.

Solution

Keys AB, AC. Violation C → B: split into CB and AC. Both two-attribute → BCNF. AB → C is not preserved (Lesson 4.4.4).

Example 3 GATE

How many relations does 3NF synthesis produce for R(A, B, C, D, E, F) with F = {A → B, C → D, E → F}?

Solution

Minimal cover = F: tables AB, CD, EF. Key = ACE (never on the right); none of the tables contains it → add ACE. 4 relations.

8 · Connect the Dots

Lessons 4.4.1–4.4.5 diagnosed; this lesson treated. Last topic of the phase: a redundancy that FDs cannot even describe: multivalued dependencies and 4NF.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — 3NF synthesis

How many relations does 3NF synthesis produce for R(A, B, C, D) with F = {A → B, C → D}?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — BCNF decomposition

R(A, B, C, D) with F = {A → B, B → C, C → D} is decomposed into BCNF by repeatedly splitting on a violating FD X → X⁺ − X. Starting with B → C (B⁺ = BCD), how many relations result?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Guarantees

Which guarantee does the BCNF decomposition algorithm always give?

1. (A) Dependency preservation
2. (B) Minimum number of tables
3. (C) Every table in 4NF
4. (D) Lossless join

Q4 · MCQ · 2 mark(s) — Key relation

In 3NF synthesis for R(A, B, C, D) with F = {AB → C, C → D}, is an extra key relation needed?

1. (A) Yes, add ABCD
2. (B) No, because CD is a key
3. (C) No, ABC already contains the key AB
4. (D) Yes, add AB

Q5 · MSQ · 2 mark(s) — Algorithms

Which statements are true?

1. (A) 3NF synthesis always gives a dependency-preserving decomposition.
2. (B) BCNF decomposition always gives the same result whatever violation is chosen first.
3. (C) BCNF decomposition always gives a lossless decomposition.
4. (D) 3NF synthesis needs a minimal cover as input.

11 · Concept Ledger

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

3NF synthesis algorithmkey relationBCNF decomposition algorithmprojected FDs during decomposition