Spurious Tuples: How to Mathematically Prove Lossless Join Decomposition

When normalizing a database schema to eliminate redundancy, an original relation R is decomposed into a set of smaller relations \R₁, R₂, ..., R_k\.

However, an arbitrary split can result in a catastrophic failure mode known as a Lossy-Join Decomposition: upon executing a natural join to reconstruct the original data, the database synthesizes Spurious Tuples (phantom rows representing relationships that never existed in the real world).

1. What Are Spurious Tuples?

Consider a relation:

Employee(EmpName, Project, Branch) 

With data:

  • (Alice, ProjectX, London)
  • (Bob, ProjectX, Paris)

Suppose a developer decomposes this table into:

  • R₁(EmpName, Project)
  • R₂(Project, Branch)

When executing a natural join R₁ bowtie R₂ matching on the common attribute Project:

  1. (Alice, ProjectX, London) (Original)
  2. (Bob, ProjectX, Paris) (Original)
  3. (Alice, ProjectX, Paris) (SPURIOUS!)
  4. (Bob, ProjectX, London) (SPURIOUS!)

The database now claims Alice works in Paris and Bob works in London. Information has been irreversibly corrupted.

2. The Formal Lossless Join Theorem

For a decomposition of relation R into two relations R₁ and R₂ with a set of functional dependencies F:

The decomposition is a Lossless-Join Decomposition if and only if the common attributes (R₁ ∩ R₂) form a Superkey for at least one of the decomposed relations.

Mathematically:

(R₁ ∩ R₂) → R₁ ∈ F^+ quad OR quad (R₁ ∩ R₂) → R₂ ∈ F^+ 

Verification Algorithm:

  1. Identify the common attributes: C = R₁ ∩ R₂.
  2. Compute the attribute closure of C using Armstrong's axioms: C^+.
  3. Check if R₁ ⊆ C^+ or R₂ ⊆ C^+.
    • If yes: Lossless Join guaranteed.
    • If no: Lossy Join (spurious tuples will occur).

Explore functional dependency solvers and decomposition matrices at Binary Dose.