Chapter 12 · Normalization and Practical Schema Design
Boyce-Codd Normal Form
BCNF strengthens third normal form: every determinant must identify an entire row. That rule removes subtle redundancy, but a BCNF decomposition can make some dependencies harder to enforce locally.
Learning outcomes
Define BCNF and distinguish it precisely from third normal form.
Find determinants that are not superkeys.
Decompose a 3NF relation into BCNF relations using a violating dependency.
Test binary decompositions for losslessness.
Evaluate the tradeoff between stronger redundancy control and dependency preservation.
BCNF in one rule
Third normal form allows one exception: a dependency can have a non-superkey determinant when every dependent attribute is prime—that is, part of some candidate key. BCNF removes that exception.
| Normal form | Allowed nontrivial dependency X → A |
|---|---|
| 3NF | X is a superkey, or A is a prime attribute. |
| BCNF | X must be a superkey. No prime-attribute exception. |
A relation that is 3NF but not BCNF
Consider teaching(student_id, course_id, instructor_id) with these business rules:
(student_id, course_id) -> instructor_idinstructor_id -> course_idEach instructor teaches exactly one course, while a student may study with several instructors. Candidate keys are (student_id, course_id) and (student_id, instructor_id). Therefore course_id is prime. The dependency instructor_id → course_id satisfies 3NF’s exception but violates BCNF because instructor_id is not a superkey of the original relation.
See the redundancy
DROP TABLE IF EXISTS teaching;CREATE TABLE teaching ( student_id INTEGER NOT NULL, course_id INTEGER NOT NULL, instructor_id INTEGER NOT NULL, PRIMARY KEY (student_id, course_id), UNIQUE (student_id, instructor_id)) STRICT;INSERT INTO teaching VALUES(101, 501, 31),(102, 501, 31),(103, 501, 31),(101, 502, 32),(103, 502, 32);The fact “instructor 31 teaches course 501” is repeated once per student. Reassigning that instructor requires several row updates.
SELECT instructor_id, COUNT(DISTINCT course_id) AS course_countFROM teachingGROUP BY instructor_idHAVING COUNT(DISTINCT course_id) > 1;Decompose on the violating dependency
The determinant and its dependent form one relation; the determinant remains as the bridge in the other.
DROP TABLE IF EXISTS student_instructor;DROP TABLE IF EXISTS instructor_course;CREATE TABLE instructor_course ( instructor_id INTEGER PRIMARY KEY, course_id INTEGER NOT NULL) STRICT;CREATE TABLE student_instructor ( student_id INTEGER NOT NULL, instructor_id INTEGER NOT NULL REFERENCES instructor_course(instructor_id), PRIMARY KEY (student_id, instructor_id)) STRICT, WITHOUT ROWID;INSERT INTO instructor_course VALUES(31, 501),(32, 502);INSERT INTO student_instructor VALUES(101, 31), (102, 31), (103, 31),(101, 32), (103, 32);Reconstruct the teaching relation
SELECT si.student_id, ic.course_id, si.instructor_idFROM student_instructor AS siJOIN instructor_course AS ic ON ic.instructor_id = si.instructor_idORDER BY si.student_id, ic.course_id;The shared attribute instructor_id is a key of instructor_course. That makes the binary decomposition lossless for the dependency used to decompose it.
The BCNF decomposition algorithm
while some relation R violates BCNF: choose a nontrivial dependency X -> Y where X is not a superkey of R replace R with: R1 = X union Y R2 = R - (Y - X) repeat on R1 and R2The algorithm guarantees a lossless decomposition, but it does not guarantee that every original dependency can be enforced without joining relations.
Dependency-preservation tradeoff
Stronger redundancy control
Every determinant is a key, eliminating more update anomalies than 3NF.
Dependency-friendly synthesis
A canonical 3NF design can preserve all dependencies while remaining lossless.
Possible enforcement cost
A lost dependency may require a cross-table assertion, trigger, materialized check, or application transaction.
Workload and risk
Prefer BCNF when the removed redundancy is material; prefer dependency-preserving 3NF when local enforcement is critical.
Do not infer dependencies from names alone
| Claim | Required business meaning |
|---|---|
| instructor_id → course_id | Each instructor teaches exactly one course for the modeled time scope. |
| course_id → instructor_id | Each course has exactly one instructor for the modeled time scope. |
| (course_id, term_code) → instructor_id | One instructor is assigned per course offering and term. |
| instructor_id → course_id is false | An instructor may teach multiple courses. |
Changing the time scope or cardinality changes the dependency set and therefore the correct schema.
Checkpoint
3NF or BCNF?
- What exception does 3NF allow that BCNF rejects?
- Why is instructor_id not a superkey of teaching?
- How does the decomposition remove redundancy?
- Why is the decomposition lossless?
- When might a dependency-preserving 3NF design be preferable?
Review the answers
3NF permits a non-superkey determinant when the dependent is prime. instructor_id does not identify a student row. The instructor-course fact is stored once. The shared determinant is a key of one component. 3NF may be preferable when every dependency must be enforced locally and the remaining redundancy is acceptable.
Summary and references
- BCNF requires every nontrivial determinant to be a superkey.
- A relation can satisfy 3NF while violating BCNF.
- Decompose around a violating determinant to remove repeated facts.
- The standard BCNF decomposition is lossless.
- BCNF may sacrifice dependency preservation, so the final choice is an engineering tradeoff.