Lossless Decompositions

Prime Directive in decomposition:

• Never introduce extraneous information in the decomposition

Lemma 1

• If R₁ and R₂ is a decomposition of R, then:

  content(R) is a subset of content(R₁) * content(R₂)

• Proof: too complicated to put on a webpage.

Lemma 2

• Let R₁ and R₂ be a decomposition of R (so the condition of Lemma 1 holds).

  If

  • R₁ INTERSECT R₂ -> R₁ or
  • R₁ INTERSECT R₂ -> R₂

  then content(R) = content(R₁) * content(R₂)

• Proof:
  • Because R₁ and R₂ is a decomposition of R, we have from Lemma 1 that content(R) is a subset of content(R₁) * content(R₂)

  • To complete the proof, you need to show that content(R₁) * content(R₂) is a subset of content(R)