BCNF, lossless joins and when to denormalise

Part of the free LogicWiz SQL & Databases course, Module 10: Normalization. The queries and practice run in the app on real Postgres.

Kabir split a table in two to "normalise" it. When he joined them back, the result had more rows than he started with. Where did the extra rows come from, and which ones are real?

You'll learn to

• Test for BCNF and tell it apart from 3NF
• Check whether a decomposition is lossless, by rule and by SQL
• Explain dependency preservation and the 3NF vs BCNF trade-off
• Decide when to denormalise on purpose

Learn

BCNF: every determinant is a key

Boyce-Codd Normal Form (BCNF): for every non-trivial FD X → Y, X is a superkey.

It is 3NF without the escape clause. 3NF also allows X → A when A is prime; BCNF does not. So every BCNF table is in 3NF, but not the other way round.

The gap shows up only when a table has overlapping candidate keys, like the one below.

enrol(student, course, teacher)

Rules: each teacher teaches one course (teacher → course); a student takes a course from one teacher (student, course → teacher). Keys: {student, course} and {student, teacher}. Every attribute is prime, so it is in 3NF. But teacher → course has teacher not a superkey, so it is not in BCNF: "Dr. Rao teaches DBMS" is stored twice.

Lossless join: can you get the original back?

When you split R into R1 and R2, joining them back must give exactly R. That is a lossless (non-additive) join decomposition.

The test: the common attributes R1 ∩ R2 must be a superkey of R1 or of R2. In other words, R1 ∩ R2 → R1 or R1 ∩ R2 → R2.

• Split enrol into (student, course) and (course, teacher): common = course. course → teacher? No (DBMS has two teachers). Lossy.
• Split into (teacher, course) and (student, teacher): common = teacher, and teacher → course, so teacher is a key of the first. Lossless.

A lossy split adds fake rows

-- r1 = (student, course), r2 = (course, teacher)
SELECT r1.student, r1.course, r2.teacher
FROM r1
JOIN r2 ON r2.course = r1.course
ORDER BY 1, 2, 3;

Seven rows come back from four. "Aarav, DBMS, Dr. Sen", "Meher, DBMS, Dr. Rao" and "Riya, DBMS, Dr. Sen" are spurious: invented by the join. Nothing was lost; extra rows appeared, and you can no longer tell which are real.

The BCNF split joins back exactly

-- teaches = (teacher, course), takes = (student, teacher)
SELECT s.student, t.course, s.teacher
FROM takes s
JOIN teaches t ON t.teacher = s.teacher
EXCEPT
SELECT student, course, teacher
FROM enrol;

Zero rows: the join gives nothing that wasn't in enrol. (Swap the two halves of EXCEPT to check that nothing is missing either.) Both new tables are in BCNF, and "Dr. Rao teaches DBMS" is stored once.

Dependency preservation, and the price of BCNF

A decomposition is dependency preserving if every original FD can still be checked inside a single table, without a join.

The BCNF split above loses student, course → teacher: no table has all three columns, so nothing stops Aarav from taking DBMS from both Dr. Rao and Dr. Sen. You'd need a join (or a trigger) to enforce it.

The trade-off to remember:

• 3NF: a lossless and dependency-preserving decomposition always exists.
• BCNF: lossless is always possible, but dependency preservation is not guaranteed.

In practice, most designs reach BCNF anyway; when they can't, 3NF is the usual stopping point.

Denormalise, on purpose

Normalised tables are great for writes. Reads that join six tables on every app open can be slow. Denormalisation stores some redundancy deliberately, for speed:

• an order-history table that keeps restaurant name and total, so the screen needs no joins
• a like_count on a post instead of COUNT(*) every time
• reporting tables and materialised views for dashboards

The rule: normalise first, measure, then denormalise only the hot path, and have a plan to keep copies in sync (a trigger, a batch job, or the price being a snapshot that should never change, like the price at the time of order).

"Lossy" does not mean rows go missing. A lossy decomposition gives extra, fake rows (spurious tuples) when joined back. The information lost is which combinations were real.

Exam favourites: (1) "Is this decomposition lossless?" Check R1 ∪ R2 = R, and that R1 ∩ R2 is a key of R1 or of R2 (compute the closure of the common attributes). (2) "Is it dependency preserving?" Project F onto each table and check that every original FD follows from their union. (3) "3NF but not BCNF?" Look for X → A where A is prime but X is not a superkey.

In one line

BCNF: every determinant is a superkey. A split is lossless when the common columns are a key of one side; 3NF always keeps dependencies, BCNF may not. Denormalise only on purpose.

Interview corner

What is the difference between 3NF and BCNF?

BCNF requires the left side of every non-trivial FD to be a superkey. 3NF also allows X → A when A is a prime attribute. So a table can be in 3NF but not BCNF only when it has overlapping candidate keys, like (student, course, teacher) with teacher → course.

What is a lossless join decomposition?

Splitting R into R1 and R2 such that R1 ⋈ R2 gives exactly R, with no spurious rows. It is lossless if the common attributes are a superkey of R1 or of R2. In SQL you can check it: join back and EXCEPT the original in both directions; both should be empty.

When would you denormalise?

When a read path is hot and the joins are measured to be the bottleneck: feeds, order history, dashboards, counters. You store copies (a cached total, a name snapshot, a materialised view) and keep them in sync with triggers, jobs or application code. Normalise first; denormalise specific paths with a reason.

Why not always go to BCNF?

A BCNF decomposition is always lossless, but it may lose a functional dependency, which then can't be enforced by a key in one table. 3NF always allows a lossless, dependency-preserving design, so some teams stop at 3NF when BCNF would cost a dependency.