Skip to content

Lesson 22: BCNF and Decomposition

The strongest ordinary normal form, and what it costs

About this lesson

Course: Database Management Systems

Unit 5: Database Design · 10 Lecture Hours

Lesson duration: 2 lectures

Reading: Elmasri & Navathe, Ch. 14.5, 15.1

Learning Outcomes

  1. Define BCNF and test a relation for it.
  2. Explain exactly when a relation is in 3NF but not BCNF.
  3. Apply the BCNF decomposition algorithm.
  4. Apply the 3NF synthesis algorithm.
  5. State the trade-off: BCNF may sacrifice dependency preservation.

22.1 Boyce-Codd Normal Form

BCNF

A relation R is in Boyce-Codd Normal Form if, for every non-trivial functional dependency X → Y that holds in R, X is a superkey of R.

Equivalently: every determinant is a superkey.

Compare the two definitions side by side; the difference is one clause.

3NF (general definition) BCNF
For every non-trivial X → A X is a superkey OR A is prime X is a superkey

BCNF is 3NF with the escape clause removed

3NF forgives a dependency whose determinant is not a superkey, provided the dependent attribute is prime. BCNF forgives nothing.

Therefore every BCNF relation is in 3NF, but not conversely. BCNF is strictly stronger.

When is a relation in 3NF but not BCNF?

The three conditions, all required together

A relation can be in 3NF but not BCNF only if all three hold:

  1. There are two or more candidate keys, and
  2. the candidate keys are composite, and
  3. the candidate keys overlap — they share at least one attribute.

If a relation has only one candidate key, or its keys are single attributes and disjoint, 3NF and BCNF coincide.

This is worth remembering, because it means BCNF violations are relatively rare in practice — most relations that reach 3NF are already in BCNF.

The classic example

TEACHING( Student, Subject, Teacher )

Business rules:

  • Each teacher teaches exactly one subject: Teacher → Subject
  • For a given student and subject, there is exactly one teacher: Student, Subject → Teacher

Candidate keys. (Student, Subject)⁺ = {Student, Subject, Teacher} = R. Minimal (neither alone works). Candidate key. (Student, Teacher)⁺ = {Student, Teacher} → (Teacher → Subject) {Student, Teacher, Subject} = R. Minimal. Candidate key.

Two candidate keys, both composite, overlapping on Student — the three conditions are met.

Prime attributes: Student, Subject, Teacher — all of them. Non-prime: none.

In 3NF? Yes. Test each dependency:

  • Student, Subject → Teacher: determinant is a superkey. Passes.
  • Teacher → Subject: determinant is not a superkey (Teacher⁺ = {Teacher, Subject} ≠ R) — but Subject is prime, so the second condition rescues it. Passes.

Since there are no non-prime attributes at all, no 2NF or 3NF violation is even possible.

In BCNF? No. Teacher → Subject has a determinant that is not a superkey, and BCNF has no escape clause.

The redundancy BCNF is objecting to

Student Subject Teacher
Ankit Database Gupta
Riya Database Gupta
Sana Database Gupta
Ankit Physics Rao

The fact "Gupta teaches Database" is stored three times. All three anomalies follow:

  • Insertion: a newly appointed teacher cannot be recorded until some student is assigned to them (Student is part of every key and cannot be NULL).
  • Deletion: if the three Database students leave, the fact that Gupta teaches Database is lost.
  • Modification: if Gupta switches to Networks, three rows must change together.

So a relation can be in 3NF and still suffer every classic anomaly. That is precisely why BCNF exists.

22.2 The BCNF Decomposition Algorithm

Algorithm

D := { R }
while some relation Q in D is not in BCNF:
    find a non-trivial FD  X -> Y  in Q  where X is NOT a superkey of Q
    replace Q in D by the two relations
        Q1 = ( X ∪ Y )          -- the offending dependency, with X as its key
        Q2 = ( Q − Y )          -- the rest, with X retained as a foreign key
return D

Each step is guaranteed lossless, because the common attribute set is X, and X is the key of Q1 (Lesson 5).

Applying it to TEACHING

The violating dependency is Teacher → Subject. So X = {Teacher}, Y = {Subject}.

  • Q1 = (Teacher, Subject) — key Teacher
  • Q2 = (Student, Teacher) — key (Student, Teacher)
TEACHES ( Teacher, Subject )        -- key Teacher
STUDIES ( Student, Teacher )        -- key (Student, Teacher)

Check TEACHES: the only determinant is Teacher, which is its key. BCNF. Check STUDIES: the only key is (Student, Teacher); no smaller determinant exists. BCNF.

Lossless? Common attribute is Teacher; Teacher⁺ = {Teacher, Subject} ⊇ TEACHES, so Teacher is a superkey of TEACHES. Yes, lossless.

The price: a lost dependency

The original dependency Student, Subject → Teacher is no longer enforceable.

Student and Subject now live in different relations, so no constraint on either table can express the rule. Checking it requires joining STUDIES and TEACHES on every insert.

Consequence — the following two rows are individually legal but jointly violate the business rule:

STUDIES TEACHES
Ankit Gupta Gupta Database
Ankit Sharma Sharma Database

Ankit now has two teachers for Database, which Student, Subject → Teacher forbade. Nothing in the decomposed schema prevents it.

This decomposition is lossless but NOT dependency preserving.

22.3 The Fundamental Trade-off

The theorem to remember

  • A lossless-join decomposition into BCNF relations always exists.
  • A lossless-join and dependency-preserving decomposition into 3NF relations always exists.
  • A lossless-join and dependency-preserving decomposition into BCNF may not exist.

TEACHING is the standard witness for the third statement.

                     lossless?      dependency        redundancy
                                    preserving?       remaining?
   3NF  synthesis      ALWAYS         ALWAYS           possibly some
   BCNF decomposition  ALWAYS         NOT ALWAYS       none (from FDs)

   You may have any two of {BCNF, lossless, dependency preserving},
   but not always all three.  Lossless is never negotiable.

Which should you choose?

Stay in 3NF when the lost dependency matters — when it is a rule the business genuinely needs enforced cheaply, and the residual redundancy is small and controlled.

Go to BCNF when the redundancy is large and the lost dependency is either unimportant or can be enforced in the application or by a trigger.

Never give up losslessness — a lossy decomposition corrupts the data itself, producing spurious tuples on reassembly. The other two properties are trade-offs; this one is a correctness requirement.

In practice most designers stop at 3NF for transactional schemas, because dependency preservation is worth more than the last increment of redundancy, and because (as noted) most 3NF relations happen to be in BCNF anyway.

22.4 The 3NF Synthesis Algorithm

Rather than decomposing top-down, 3NF can be synthesised bottom-up from a minimal cover — and the result is guaranteed to be both lossless and dependency preserving.

Algorithm (3NF synthesis)

  1. Compute a minimal cover G of F (Lesson 2).
  2. For each dependency X → Y in G, create a relation (X ∪ Y). Merge relations whose determinants are identical.
  3. If no relation created so far contains a candidate key of R, add one more relation consisting of any candidate key of R. (This step guarantees losslessness.)
  4. Remove any relation that is a subset of another.

Worked example

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

Step 1 — minimal cover. Split the right sides: A → B, A → C, CD → E, B → D, E → A. Check for extraneous left attributes in CD → E: is C extraneous? D⁺ = {D}, no. Is D extraneous? C⁺ = {C}, no. Check redundancy: removing any one of the five loses information (verify each with a closure). So the cover is already minimal:

G = { A → B, A → C, CD → E, B → D, E → A }

Step 2 — one relation per dependency, merging equal determinants:

R1 ( A, B, C )      from A → B and A → C merged
R2 ( C, D, E )      from CD → E
R3 ( B, D )         from B → D
R4 ( E, A )         from E → A

Step 3 — does any relation contain a candidate key? The candidate keys are A, E, BC, CD (computed in Lesson 2). R1 contains A; R2 contains CD; R4 contains E. Yes — no extra relation is needed.

Step 4 — subset removal. None is a subset of another.

Result: R1(A,B,C), R2(C,D,E), R3(B,D), R4(E,A) — all in 3NF, the decomposition lossless and dependency preserving by construction.

Step 3 is not optional

Omit it and the decomposition may be lossy. Consider R(A,B,C) with the single dependency A → B. Step 2 gives only R1(A,B); attribute C is lost entirely. Step 3 adds a candidate key relation R2(A,C), restoring both C and losslessness.

22.5 Higher Normal Forms (brief)

Beyond BCNF

4NF removes multivalued dependencies (MVDs). X ↠ Y means that for each value of X there is a set of Y values independent of the other attributes. A relation is in 4NF if it is in BCNF and every non-trivial MVD has a superkey determinant.

Example. EMP(Ename, {Project}, {Dependent}) where projects and dependants are independent. Storing both in one relation forces every combination to be listed — 3 projects × 2 dependants = 6 rows for facts that need 3 + 2 = 5. Split into EMP_PROJECT and EMP_DEPENDENT.

5NF (Project-Join Normal Form) removes join dependencies — cases where a relation must be decomposed into three or more fragments to remove redundancy, though no two-way decomposition suffices.

These are beyond the scope of this course, but a complete answer to "list the normal forms" should mention them.

22.6 Solved Questions

Solved Question 1

Q. Define BCNF. How does it differ from 3NF? Under what conditions can a relation be in 3NF but not BCNF?

A. A relation is in BCNF if for every non-trivial FD X → Y, X is a superkey.

Difference from 3NF. The general 3NF definition allows X → A when X is a superkey or A is prime. BCNF deletes the second alternative. So BCNF is 3NF with the escape clause removed, and is strictly stronger: every BCNF relation is in 3NF, but not conversely.

Conditions for 3NF-but-not-BCNF. All three must hold simultaneously:

  1. The relation has two or more candidate keys;
  2. the candidate keys are composite;
  3. the candidate keys overlap (share at least one attribute).

If any fails, 3NF and BCNF coincide. Hence BCNF violations are relatively rare.

Why these conditions? A 3NF-but-not-BCNF violation needs a dependency X → A where X is not a superkey and A is prime. For A to be prime it must lie in some candidate key; for X to be a non-superkey determinant of a key attribute while the relation is still in 3NF, another candidate key must exist and share attributes with the first. TEACHING(Student, Subject, Teacher) with keys (Student, Subject) and (Student, Teacher) — overlapping on Student — is the canonical instance.

Solved Question 2

Q. Show that TEACHING(Student, Subject, Teacher) with Student,Subject → Teacher and Teacher → Subject is in 3NF but not BCNF. Decompose it and state what is lost.

A.

Candidate keys. (Student, Subject)⁺ = R and is minimal → candidate key. (Student, Teacher)⁺ = {Student, Teacher} →(Teacher → Subject) = R, minimal → candidate key. Prime: all three attributes. Non-prime: none.

3NF — satisfied. With no non-prime attributes, no 2NF or 3NF violation is possible. Checking each FD by the general definition: Student,Subject → Teacher has a superkey determinant; Teacher → Subject has a non-superkey determinant but Subject is prime, so the second condition applies. In 3NF.

BCNF — violated. Teacher → Subject has determinant Teacher with Teacher⁺ = {Teacher, Subject} ≠ R, so it is not a superkey, and BCNF permits no exception.

The redundancy. "Gupta teaches Database" is repeated once per student of Gupta, giving insertion, deletion and modification anomalies.

Decomposition on the violating dependency X = {Teacher}, Y = {Subject}:

TEACHES ( Teacher, Subject )     key Teacher
STUDIES ( Student, Teacher )     key (Student, Teacher)

Both are in BCNF: each relation's only determinant is its own key.

Lossless? Yes. Common attribute Teacher; Teacher⁺ ⊇ TEACHES, so the common attributes form a superkey of one fragment.

What is lost: the dependency Student, Subject → Teacher. Student and Subject now sit in different relations, so no single-table constraint can enforce it. Two individually legal rows — Ankit/Gupta in STUDIES and Ankit/Sharma in STUDIES, with both teachers teaching Database — jointly break the rule, and nothing detects it. Enforcement would require a join on every insert, or a trigger.

The decomposition is lossless but not dependency preserving — the standard illustration that BCNF and dependency preservation can be incompatible.

Solved Question 3

Q. State the BCNF decomposition algorithm and apply it to R(A,B,C,D) with AB → CD and D → A.

A. (Algorithm as in Section 4.2.)

Candidate keys. AB⁺ = {A,B} → {A,B,C,D} = R, minimal → candidate key. BD⁺ = {B,D} →(D→A) {A,B,D} →(AB→CD) {A,B,C,D} = R; is it minimal? B⁺ = {B}, D⁺ = {A,D} — neither is R, so BD is a candidate key.

Candidate keys: AB, BD. Prime: A, B, D. Non-prime: C.

3NF? AB → CD — superkey determinant, fine. D → A — D⁺ = {A,D} ≠ R, so not a superkey; but A is prime, so 3NF forgives it. In 3NF.

BCNF? D → A has a non-superkey determinant. Violated.

(Note that this relation satisfies the three conditions: two candidate keys, both composite, overlapping on B.)

Decompose on X = {D}, Y = {A}:

  • Q1 = X ∪ Y = (D, A) — key D
  • Q2 = R − Y = (B, C, D) — the rest, with D retained

Check Q1(D, A): only determinant is D, its key. BCNF. Check Q2(B, C, D): which dependencies hold here? Projecting F onto {B,C,D}: BD⁺ = R, so BD → C holds; nothing smaller determines anything. The only determinant is BD, the key. BCNF.

Lossless? Common attribute D; D⁺ = {A,D} ⊇ Q1. Yes.

Dependency preserving? D → A is checkable in Q1. AB → CD is not checkable — A is in Q1, B and C in Q2, and no fragment contains all of A, B, C, D. Not dependency preserving. Again the characteristic BCNF trade-off.

Solved Question 4

Q. State the 3NF synthesis algorithm and apply it to R(A,B,C,D,E,F) with F = {A → BC, C → DE, E → F, F → A}.

A. (Algorithm as in Section 4.4.)

Step 1 — minimal cover. Split the right sides: A → B, A → C, C → D, C → E, E → F, F → A. Every left side is a single attribute, so none can be extraneous. Test redundancy: removing A → B leaves A⁺ (under the rest) = {A,C,D,E,F} which excludes B, so keep it; similar checks retain all six. The cover is already minimal.

Step 2 — one relation per dependency, merging identical determinants:

R1 ( A, B, C )     from A → B and A → C
R2 ( C, D, E )     from C → D and C → E
R3 ( E, F )        from E → F
R4 ( F, A )        from F → A

Step 3 — does some relation contain a candidate key? Compute the keys. A⁺ = {A,B,C,D,E,F} = R, so A is a candidate key. Likewise C⁺ = {C,D,E,F,A,B} = R, E⁺ = {E,F,A,B,C,D} = R, and F⁺ = R. Candidate keys: A, C, E, F (a cycle of determinants). R1 contains A, so the condition is met — no extra relation needed.

Step 4 — subset removal. None is a subset of another.

Result: R1(A,B,C), R2(C,D,E), R3(E,F), R4(F,A).

Properties, guaranteed by construction: every relation is in 3NF; the decomposition is dependency preserving (each dependency of the cover sits inside one relation); and it is lossless (a relation contains a candidate key).

Are they also in BCNF? R1(A,B,C): the determinants holding here are A (its key) and C, and C⁺ = R ⊇ R1, so C is also a superkey of R1. Both determinants are superkeys — BCNF. Similar checks show the same for the others. Here 3NF synthesis happened to yield BCNF, which is common.

Solved Question 5

Q. State the trade-off between BCNF and dependency preservation. Which property must never be sacrificed, and why?

A. Three properties are wanted from a decomposition: it should be lossless, dependency preserving, and its fragments should be in as high a normal form as possible.

The theorems:

Target Lossless? Dependency preserving?
3NF always achievable always achievable
BCNF always achievable not always achievable

TEACHING(Student, Subject, Teacher) is the standard witness for the negative result: any BCNF decomposition loses Student, Subject → Teacher.

Losslessness must never be sacrificed. The reason is a difference in kind, not degree:

  • Losing a dependency costs enforcement: the constraint can still be checked, just more expensively — with a join, a trigger, or application code. The data remains correct, and the correct answer to every query is still obtainable.
  • A lossy decomposition corrupts the data itself. Rejoining the fragments produces spurious tuples — rows that were never in the original relation and assert facts that are simply false. There is no way to tell the genuine rows from the invented ones, and no amount of later care recovers the lost information.

So losslessness is a correctness requirement, while dependency preservation and normal form are engineering trade-offs.

Practical guidance. Decompose to 3NF by synthesis, which gives all three properties whenever they are jointly achievable. Then check whether the result is already in BCNF — usually it is. If it is not, weigh the residual redundancy against the cost of enforcing the lost dependency, and choose deliberately. Most transactional schemas stop at 3NF.

Solved Question 6

Q. Give the sequence of all normal forms with a one-line criterion for each, and state which anomaly each removes.

A.

Normal form Criterion Removes
1NF All attribute values are atomic; no repeating groups, composite or multivalued attributes Non-relational structure; makes querying possible at all
2NF 1NF, and no non-prime attribute is partially dependent on a candidate key Redundancy from attributes belonging to part of a composite key
3NF 2NF, and for every non-trivial X → A, X is a superkey or A is prime Redundancy from transitive dependencies — facts about a second entity
BCNF Every determinant is a superkey (no exceptions) The remaining redundancy from FDs, where the dependent attribute is prime
4NF BCNF, and every non-trivial multivalued dependency has a superkey determinant Redundancy from independent multivalued facts stored together
5NF / PJNF Every join dependency is implied by the candidate keys Redundancy removable only by decomposing into three or more relations

Each form is strictly stronger than its predecessor: 5NF ⊂ 4NF ⊂ BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF.

The unifying idea is the one from Unit 3, Lesson 1: a relation should describe one kind of thing. Each normal form detects a different way in which a second kind of fact has crept in — via part of a key (2NF), via another non-prime attribute (3NF), via a prime attribute (BCNF), or via an independent multivalued fact (4NF).

For this course, 1NF to BCNF are examinable; 4NF and 5NF should be known by name and criterion.

22.7 Exercises

A. Short answer

  1. Define BCNF in one sentence.
  2. State the difference between 3NF and BCNF precisely.
  3. Give the three conditions under which a relation can be in 3NF but not BCNF.
  4. Which decomposition target always allows dependency preservation?
  5. Why must losslessness never be sacrificed?
  6. What does step 3 of the 3NF synthesis algorithm guarantee?
  7. What does 4NF remove?

B. Test and decompose

For each: find all candidate keys, determine the highest normal form, and if it is not in BCNF, decompose. State whether your decomposition preserves dependencies.

  1. R(A,B,C) with AB → C, C → A.
  2. R(A,B,C,D) with A → BCD, BC → AD, D → B.
  3. R(A,B,C,D) with AB → C, C → D, D → A.
  4. R(A,B,C,D,E) with AB → CDE, E → AB.
  5. ADDRESS(Street, City, State, PIN) with Street,City,State → PIN and PIN → City,State.
  6. ENROL(Student, Course, Instructor) where each instructor teaches one course, and a student takes each course from one instructor.
  7. SUPPLY(Supplier, Part, City) where each supplier is in one city, and only one supplier of a given part is in a given city.

C. Synthesis

  1. Apply the 3NF synthesis algorithm to R(A,B,C,D,E) with F = {AB → C, C → D, D → E, E → A}.
  2. Apply it to R(A,B,C,D,E,G) with F = {A → BC, CD → E, B → D, E → A, G → A}.
  3. Show, with an example, why omitting step 3 of the synthesis algorithm can produce a lossy decomposition.

D. Analysis

  1. Prove that every BCNF relation is in 3NF.
  2. Prove that a relation with exactly two attributes is always in BCNF.
  3. Prove that a relation with a single candidate key is in BCNF if and only if it is in 3NF.
  4. For TEACHING, construct explicit rows in the decomposed schema that jointly violate Student,Subject → Teacher while each table is individually valid. Then write the SQL query a trigger would need in order to detect the violation.
  5. A designer refuses to go beyond 3NF, saying "BCNF costs a lost dependency". Under what circumstances is this reasoning correct, and under what circumstances is it wrong?
  6. Give a relation in BCNF that still exhibits redundancy. Which normal form addresses it?
  7. Explain why most relations that reach 3NF are already in BCNF, referring to the three conditions.

E. Objective — True or False with reason

  1. Every 3NF relation is in BCNF.
  2. Every BCNF relation is in 3NF.
  3. A lossless BCNF decomposition always exists.
  4. A dependency-preserving BCNF decomposition always exists.
  5. A relation with one candidate key that is in 3NF is in BCNF.
  6. Losing a dependency corrupts the data.

Answers to Section E

  1. False. TEACHING(Student, Subject, Teacher) is the standard counter-example.
  2. True. BCNF's condition implies 3NF's first alternative, so 3NF is automatically satisfied.
  3. True. The decomposition algorithm splits on X → Y into (X ∪ Y) and (R − Y), whose common attributes X form a key of the first — always lossless.
  4. False. This is exactly what TEACHING disproves.
  5. True. With one candidate key the three conditions for a 3NF-but-not-BCNF violation cannot be met, so the two forms coincide.
  6. False. It costs enforcement — the rule needs a join or a trigger — but the stored data remains correct. Only a lossy decomposition corrupts data, by producing spurious tuples.

Lesson Summary

  • BCNF: every determinant is a superkey. It is 3NF with the "or A is prime" escape clause removed, and is strictly stronger.
  • A relation is in 3NF but not BCNF only when it has two or more overlapping composite candidate keys — so BCNF violations are uncommon.
  • The BCNF decomposition algorithm splits on a violating X → Y into (X ∪ Y) and (R − Y); every step is lossless.
  • The 3NF synthesis algorithm builds one relation per dependency of a minimal cover, plus a candidate-key relation if needed — always lossless and dependency preserving.
  • Trade-off: lossless BCNF always exists; lossless and dependency-preserving BCNF may not. Never sacrifice losslessness — it corrupts data, whereas a lost dependency merely costs enforcement.