Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 79 ยท Database Design Theory

BCNF and Lossless Decomposition

Learn Boyce-Codd normal form, how it differs from 3NF, the lossless-join chase test, dependency preservation and 3NF synthesis, with live Python tools.

Third normal form allows one loophole: a dependency X -> A is acceptable if A is a prime attribute, even when X is not a key. That loophole is there for a good reason, but it leaves a little redundancy behind. Boyce-Codd normal form (BCNF) closes it with a simpler, stricter rule. The price is that BCNF cannot always be reached without losing a dependency, and understanding that trade-off is the heart of this lesson.

Splitting a table is not free either. A bad split creates rows that never existed. So we also need two tests for any decomposition: is it lossless (can we rebuild the original?) and is it dependency preserving (can we still enforce every rule locally?). By the end you will run both tests, plus an algorithm that always produces a 3NF design, in Python.

BCNF in one line

Every determinant is a key For each non-trivial X -> Y, X is a superkey.
Stricter than 3NF No "unless Y is prime" escape.
May cost a dependency Some FDs can no longer be checked in one table.
1 / 2

The BCNF definition

A relation R is in BCNF when, for every non-trivial functional dependency X -> Y that holds in R, X is a superkey of R. Compare that with 3NF from 1NF, 2NF and 3NF, which also accepts the case where every attribute of Y - X is prime. Every BCNF relation is in 3NF, but not the other way around.

The classic example is an address table: R(street, city, zip). In many places a street and city together determine the zip code, and a zip code lies inside one city:

  • street, city -> zip
  • zip -> city

Using letters, with A = street, B = city, C = zip, these are AB -> C and C -> B. The candidate keys are AB and AC (since AC determines B through C -> B). Every attribute is prime, so the relation is in 3NF: C -> B is allowed because B is prime. But it is not in BCNF, since C is not a superkey. The consequence is real: the pair (zip, city) is repeated for every street in that zip code.

The BCNF decomposition algorithm

The algorithm is a repeated split:

  1. Find an FD X -> Y that holds in a relation R and violates BCNF (X is not a superkey of R).
  2. Replace R by two relations: R1 = X+ (the closure of X, restricted to the attributes of R) and R2 = (R - X+) โˆช X.
  3. Repeat on R1 and R2 until every piece is in BCNF.

For a piece that is a smaller relation, you must use the FDs that hold within it, called the projection of F onto that relation. It is computed by taking each subset X of the piece's attributes and recording what X+ determines inside the piece. Every split loses no information, because the attributes that R1 and R2 share, X, form a key of R1. That is the lossless-join condition, discussed next.

Testing a decomposition

Lossless join

A decomposition of R into R1, ..., Rn is lossless if for every legal instance of R, the natural join of the projections equals the original instance. Lossy decompositions invent extra "spurious" rows that were never stored. For two pieces there is a neat test: the decomposition into R1 and R2 is lossless when the common attributes R1 โˆฉ R2 determine all of R1 or all of R2. In other words, the shared columns must be a key of at least one side.

For more than two pieces, use the chase (tableau) test. Build a table with one row per piece and one column per attribute. Put a special symbol "a" in each cell whose attribute belongs to that piece, and a unique symbol "b" elsewhere. Then apply the FDs: whenever two rows agree on the left side of an FD, make them agree on the right side (preferring "a"). If some row ends up all "a" symbols, the decomposition is lossless.

Dependency preservation

A decomposition preserves dependencies if every FD in F can be enforced by looking at one of the pieces alone, without joining. Formally, the union of the projections of F onto the pieces must imply all of F. In practice you test one FD X -> Y at a time: start with result = X, and repeatedly add closure(result โˆฉ Ri) โˆฉ Ri for every piece Ri; the FD is preserved if Y ends up inside result. If an FD is not preserved, enforcing it needs a join on every insert, which is slow and often skipped.

Python BCNF decomposition, chase test and preservation check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The address relation splits into BC (city, zip) and AC (street, zip). The split is lossless, since the shared column C is a key of BC. But AB -> C is lost: street and city never appear together in one table anymore, so the database cannot check that rule without a join. That is the BCNF trade-off in one picture. Some schemas, like this one, have no BCNF decomposition that keeps every dependency.

What a lossy split looks like

If the shared columns are not a key of either side, the join manufactures rows. Take a table of (student, course, room) with no useful FDs and split it into (student, course) and (course, room).

SQL A lossy decomposition invents rows

Press Run (or Ctrl + Enter) to see the result here.

The original had two rows, but the join returns four: Ana in R2 and Bo in R1 are spurious. The shared column course does not determine room (there are two rooms for DB) nor student, so the test fails. If the real rule were course -> room, the same split would be lossless and the spurious rows could not exist.

Synthesizing a 3NF design

Because BCNF can force you to give up a dependency, there is a second algorithm that is always lossless and always dependency preserving, at the price of stopping at 3NF. It builds the schema from the FDs instead of splitting a big table.

  1. Compute a minimal cover (from Attribute Closure, Keys and Minimal Cover).
  2. For each group of FDs with the same left side X, create a relation with X plus all the right sides.
  3. If no relation contains a candidate key of the original schema, add one more relation holding a candidate key.
  4. Remove any relation whose attributes are contained in another relation.

Here is a scheduling schema: C course, T teacher, H hour, R room, S student, G grade, with FDs C -> T, HR -> C, HT -> R, CS -> G, HS -> R.

Python 3NF synthesis, verified

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output lists every relation as a sorted string of attribute letters: CT, CHR, HRT, CGS and HRS. Each one holds one cluster of dependencies: course to teacher, hour and room to course, hour and teacher to room, course and student to grade, and hour and student to room. The only candidate key, HS, already sits inside HRS, so no extra relation is added, and the list of lost FDs is empty. Dependency preservation is guaranteed by construction, since every FD of the cover lives entirely inside one relation. Because synthesis guarantees 3NF only, individual relations may still hold BCNF-violating FDs, as in the address example.

Testing preservation by projecting FDs

The shortcut above tests one FD at a time. There is also a definition-level test that is worth knowing, because it explains why a dependency gets lost. It has three steps:

  1. Project F onto every piece Ri. The projection F_i is the set of FDs X -> Y in F+ with X and Y both inside Ri. You get it by closing each subset X of Ri under the full F and keeping the part of X+ that lies inside Ri. Closing under the full F matters: an FD can reach a piece through attributes that live in another piece.
  2. Take the union G = F_1 โˆช ... โˆช F_n. This is everything the pieces can enforce on their own.
  3. Compare. The decomposition is dependency preserving when G implies every FD of F, that is, when X+ computed under G contains Y for each X -> Y in F.

The classic example is an address table R(Street, City, Zip) where a street and city determine the zip code (SC -> Z) and a zip code determines the city (Z -> C). The candidate keys are SC and SZ. BCNF is broken by Z -> C, since Z is not a key, so the BCNF algorithm splits off ZC and leaves ZS. The program checks what survives.

Python Project FDs onto the pieces and compare the union with F

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the BCNF split, the piece ZC keeps Z -> C, and ZS keeps nothing, so G is just Z -> C. From G alone, SC determines only itself, so SC -> Z is lost: a new row could repeat a street and city with a different zip code, and no single table would notice. Enforcing it would need a join on every insert. Keeping the single table SCZ loses nothing but leaves the redundancy of Z -> C (every row with the same zip repeats the city). The third example shows a split that keeps everything because each FD fits inside one piece.

The trade-off in one sentence

For this schema you must choose: BCNF with a lost dependency, or 3NF with a little redundancy. 3NF synthesis always preserves dependencies and is lossless, so it is the safe default when the lost rule matters. BCNF decomposition is always lossless but may lose dependencies, so it is the better choice when the lost rule is rare or can be enforced another way, for example with a trigger or a unique index on a helper table.

Which one should you use?

Aim for BCNF first. If the BCNF decomposition loses a dependency that you care about, either keep that relation in 3NF form or enforce the lost rule in another way, such as a trigger or a constraint on a helper table. In practice, most real designs in 3NF are already in BCNF; the examples that are not are the "overlapping candidate keys" cases like the address table.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the BCNF condition?

    BCNF requires every determinant of a non-trivial FD to be a superkey, with no exception for prime attributes.
  2. 2. R(A, B, C) has FDs AB -> C and C -> B. Which statement is correct?

    The keys are AB and AC, so B is prime and C -> B is allowed in 3NF. In BCNF, C must be a superkey, and it is not.
  3. 3. When is a binary decomposition of R into R1 and R2 lossless?

    If R1 โˆฉ R2 is a key of one side, each row of the other side joins with exactly one row, so no spurious rows appear.
  4. 4. Which guarantee does the 3NF synthesis algorithm give that BCNF decomposition cannot?

    Synthesis builds one relation per group of FDs from a minimal cover, so every FD sits inside a relation, and the key-relation step makes the join lossless.

Summary

  • BCNF: for every non-trivial FD X -> Y, X must be a superkey; it is stricter than 3NF, which also accepts Y made of prime attributes.
  • BCNF decomposition repeatedly splits a violating relation into X+ and (R - X+) โˆช X; it is always lossless but may lose dependencies.
  • A decomposition is lossless when the join rebuilds every legal instance; test with the common-attribute rule (two pieces) or the chase (any number).
  • Dependency preservation means every FD can be enforced inside a single table; compute it by closing the left side through the pieces.
  • 3NF synthesis (minimal cover, one relation per left side, add a key if missing, drop subsets) is always lossless and dependency preserving.
  • Lossy splits create spurious rows when the shared columns are not a key.

Next: Multivalued Dependencies, 4NF and Denormalization.