Boyce-Codd Normal Form and the Cost of Losing a Dependency

Third normal form and Boyce-Codd normal form differ by one clause, and that clause decides whether a decomposition can preserve the original constraints. Every textbook states the result — 3NF is always achievable with lossless join and dependency preservation, BCNF is always achievable with lossless join but not always with both — and almost none of them show why, or what the loss means when it happens in a real schema. Both are worth understanding concretely, because the choice between them is a real engineering decision that shows up as either a redundant column or an unenforceable constraint.

The definitions, and the gap between them

A functional dependency X → A violates third normal form in relation R when X is not a superkey of R and A is not a prime attribute — that is, A is not part of any candidate key. The dependency is then a transitive dependency of a non-prime attribute on a key.

BCNF tightens this by removing the second condition: X → A violates BCNF whenever X is not a superkey, regardless of whether A is prime. Equivalently, in a BCNF relation every non-trivial dependency has a superkey on its left.

The difference is exactly the case where X determines a prime attribute but is not itself a superkey. Such a dependency is sometimes called a dependency on a proper subset of a candidate key, when A is part of a composite key that X only partly determines. The textbook example:

Enrolment(student, course, instructor)
  {student, course} → instructor
  instructor → course

Candidate keys are {student, course} and {student, instructor}. The dependency instructor → course has a non-superkey left side, but its right side course is prime — it appears in the first candidate key. So the relation is in 3NF and not in BCNF.

The anomaly this permits is concrete. The same instructor teaching the same course to two students produces two rows with the same (instructor, course) pair. If the instructor’s course assignment changes, the update must touch every enrolment row for that instructor, and a partial update leaves the table asserting that one instructor teaches two different courses. That is an update anomaly, and it is exactly the anomaly BCNF eliminates.

Decomposition and what “lossless” means

A decomposition replaces R with relations R1, …, Rk whose union of attributes is attrs(R). Two properties are at stake.

Lossless join: the natural join of the decomposed relations must reproduce exactly the original relation, no tuples added and none lost. For a two-way decomposition into R1 and R2, the condition is that (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 holds under F+. For k relations the general test is the chase, described in the chase as a general implication test.

Dependency preservation: the union of the projections of F onto each Ri must imply F. Formally, with Fi = {X → Y ∈ F+ : XY ⊆ attrs(Ri)}, the decomposition preserves dependencies when (F1 ∪ … ∪ Fk)+ = F+.

The second property is not about correctness of data, it is about enforceability. If a dependency is not in any Fi, then no single relation’s constraints can reject a violation of it. The system can still store data that violates the dependency, and detecting the violation requires joining the decomposed relations back together — a check that costs a join per insert and that no declarative constraint can express.

Consider the standard counterexample for BCNF. Let

R(city, street, zip)
  {city, street} → zip
  zip → city

Candidate keys are {city, street} and {zip, street}. The dependency zip → city has a non-superkey left side, so R is not in BCNF. Decomposing on that dependency gives R1(zip, city) and R2(street, zip).

The decomposition is lossless: the common attribute zip determines city, so R1 ∩ R2 → R1 holds. But {city, street} → zip is now spread across both relations — city lives in R1, street and zip in R2 — and neither R1 nor R2 contains all three attributes. The dependency is not preserved.

The consequence in operation: inserting ('Cambridge', 'Main St', '02139') into the join of R1 and R2 requires a matching row in R1 and a matching row in R2. Nothing prevents inserting ('Cambridge', '02139') into R1 and ('Main St', '02142') into R2, whose join asserts that Main St in Cambridge has zip 02142. The database accepts this. Only a join of the two relations reveals that {city, street} → zip is violated, and by then the anomaly is stored.

Under 3NF, the same schema is left as one relation, or decomposed differently, so the dependency remains checkable. The price is that the update anomaly survives: correcting a zip code requires updating every street row in that city.

Why 3NF is always reachable

The synthesis algorithm constructs a 3NF decomposition directly from a minimal cover, and the construction is the proof that dependency preservation costs nothing in 3NF.

Given F, compute a minimal cover Fc: no dependency in Fc is redundant, and no left side has an extraneous attribute. Then:

1. For each dependency X → A in Fc, create a relation with attributes X ∪ {A}. Group dependencies with identical left sides into one relation.
2. If no created relation contains a candidate key of R, add a relation consisting of the attributes of some candidate key.
3. Remove any relation whose attributes are a subset of another’s.

Step 1 guarantees dependency preservation: each dependency in Fc has all its attributes inside one relation, so it appears in that relation’s projection. Since Fc is equivalent to F, the union of projections implies F.

Step 2 guarantees lossless join: the added key relation intersects every other relation in a way that lets the chase succeed, because the key determines all attributes of R.

Step 3 is a size optimization that does not affect either property.

Every relation produced has the property that for each dependency X → A it contains, X is a superkey of that relation — because the relation is exactly X ∪ {A}, plus possibly other attributes determined by X if left sides were grouped. Any remaining dependency with a non-superkey left side has a prime right side, which is the 3NF condition. The algorithm cannot produce a relation that violates 3NF, which is why the guarantee is unconditional.

Note what synthesis does not promise: it does not produce the fewest relations, and different minimal covers of the same F can produce different decompositions with different relation counts. It also does not remove all redundancy. A 3NF schema can contain a dependency X → A where X is not a superkey and A is prime, and that dependency’s redundancy persists.

Why BCNF is not always reachable with both properties

The impossibility is a theorem about a class of schemas rather than about every schema, and the (city, street, zip) example shows the mechanism. There, zip → city must be enforced, and a BCNF decomposition cannot keep both zip and city in one relation with zip as the left side unless zip is a superkey — which it is not, since {zip, street} is the candidate key. Putting zip and city together in a relation (zip, city) is BCNF, and it does not contain street, so {city, street} → zip has attributes in two relations.

The alternatives are exhausted by the same reasoning. Any relation containing all three attributes still violates BCNF, because zip → city has a non-superkey left side there. Any relation containing city and street but not zip cannot enforce the dependency that relates them to zip. There is no third option, so no dependency-preserving BCNF decomposition of this schema exists.

Deciding in general whether a given schema admits both a BCNF decomposition and dependency preservation is itself a hard problem — it is NP-hard, which is why normalization tools test specific decompositions rather than searching for one.

Choosing between the two

The trade is between a redundant column and a join-time constraint, and it should be made by asking which failure is worse for the workload.

Keeping 3NF with the unnormalized relation means update anomalies require discipline. A zip correction must be applied to every row in the city, and a partial application leaves inconsistent data that no constraint detects. In a schema where such attributes change rarely and reads dominate, the anomaly is cheap to manage — a maintenance statement, not a correctness hazard.

Choosing BCNF means the dependency becomes an application invariant. Every insert into the join of the decomposed relations must be checked by code that knows about both relations, and every bulk load must be validated by a join. The cost is a join per write, plus the risk that some path bypasses the check. In exchange, the update anomaly is gone: city is stored once per zip, and a correction is a single-row update.

There is a third option that is often the right one and is rarely mentioned in the textbook framing: keep BCNF and materialize the join as a view with a uniqueness constraint, where the system supports it. The dependency is then enforced at the join, and the base relations stay normalized. Implementations differ in whether they allow constraints on views, and the portability cost is real.

Related boundaries

BCNF is defined over functional dependencies only. A relation can be in BCNF and still contain redundancy caused by multivalued dependencies, which is what fourth normal form addresses — see multivalued dependencies and fourth normal form. And BCNF says nothing about join dependencies that are not implied by FDs, which is the territory of fifth normal form, covered in join dependencies and fifth normal form.

The normalization ladder is not a sequence of increasing quality. It is a sequence of increasingly strong conditions, each of which removes a specific class of anomaly at a specific cost. BCNF and 3NF are the two rungs where the cost becomes visible as a design choice rather than a theorem, and the choice is not settled by the theory — only by which anomaly the schema can afford.