Lossless and dependency-preserving decomposition

Why it matters

Normalization works by splitting tables, and a split can go wrong in two ways: joining the pieces back can produce rows that were never in the original (information lost by adding false facts), or a rule that one table used to enforce can end up spread across tables where no key can check it. The two properties that rule these out are a favourite exam topic and the reason normalization algorithms are designed the way they are.

The idea

A decomposition replaces a relation R with relations R1, ..., Rn whose attributes together cover R, each being a projection of R. Two properties make it safe.

Lossless join

A decomposition is lossless when natural-joining the pieces always gives back exactly the original relation, for every legal instance. A lossy split produces spurious tuples: extra rows in the join that were not in the original. They come from joining on attributes that are not a key for either side.

The test for a two-way split. Decomposing R into R1 and R2 is lossless if and only if the common attributes R1 ∩ R2 functionally determine all of R1 or all of R2, that is, the shared attributes form a super key of at least one side. Check it with closures: compute (R1 ∩ R2)⁺ and see whether it contains R1 or R2. For splits into more than two relations, the general chase (tableau) test applies, or you apply the two-way test step by step if the decomposition was built by repeated binary splits.

Dependency preservation

A decomposition is dependency-preserving when every original dependency can be enforced within a single piece (more precisely, when the union of the dependencies projected onto each piece implies the original set). If it is not, enforcing a lost rule needs a join or a trigger on every write. Losslessness is non-negotiable; dependency preservation is highly desirable but, as the BCNF lesson showed, sometimes cannot be had together with BCNF.

3NF synthesis

1. 1

   Compute a minimal cover

   Single-attribute right-hand sides, no extraneous left-hand attributes, no redundant dependencies.
2. 2

   One relation per determinant

   For each left-hand side X, create a relation with X and everything it determines in the cover.
3. 3

   Ensure a key is present

   If no relation contains a candidate key of the original, add one relation that is just a candidate key; this guarantees losslessness.
4. 4

   Remove subsumed relations

   Drop any relation whose attributes are a subset of another's.

The result is in 3NF, lossless, and preserves every dependency by construction.

BCNF decomposition

1. 1

   Find a violation

   Find a non-trivial dependency X → Y in a relation R where X is not a super key of R.
2. 2

   Split on it

   Replace R with R1 = X ∪ Y (in practice, X⁺ restricted to R's attributes) and R2 = R − (Y − X). The shared attributes X are a key of R1, so the split is lossless.
3. 3

   Repeat

   Recompute the dependencies that hold in each piece and repeat until every piece is in BCNF.
4. 4

   Check what was lost

   Test whether the original dependencies are still enforceable; if an important one was lost, consider stopping at 3NF.

Trade-offs

Lossless decomposition is mandatory; a lossy schema silently invents data. Dependency preservation keeps rules enforceable by keys alone, at the cost of sometimes accepting 3NF redundancy instead of BCNF. Algorithms guarantee the properties but can produce more tables than a thoughtful designer would; treat them as a check on a design and a tool for exam answers rather than a schema generator.

In an interview

Use the two-way test explicitly: "Splitting Student(roll_no, name, dept_id, dept_name) into (roll_no, name, dept_id) and (dept_id, dept_name) is lossless because the shared attribute dept_id is a key of the second table; both dependencies are preserved, since each lives inside one table." Then mention the BCNF caveat if overlapping keys appear.