Lossless Join Decomposition Criteria

Here is the proof.

(⇐) Suppose T₁ ∩ T₂ → T₁ ∈ F⁺. Let r a valid instance of R⟨T, F⟩, and s = π _T1(r ) ⨝ π _T2(r ). If t ∈ s, then we need to show that t ∈ r. By definition of s, we have two tuples u and v in r such that u [T₁] = t [T₁], v [T₂] = t [T₂] and u [T₁ ∩ T₂] = v [T₁ ∩ T₂] = t [T₁ ∩ T₂]. Since T₁ ∩ T₂ → T₁ ∈ F⁺, then u [T₁] = v [T₁] and so t = v.

The case T₁ ∩ T₂ → T₂ ∈ F⁺ can be proved in the same way.

(⇒) Suppose that, for each valid instance r of R⟨T,F⟩, r = π _T1(r ) ⨝ π _T2(r ); we need to show that T₁ ∩ T₂ → T₁ ∈ F⁺ or T₁ ∩ T₂ → T₂ ∈ F⁺.

Using reductio ad absurdum, we suppose that none of the two functional dependencies is implied by F. Let W = (T₁ ∩ T₂)⁺, Y₁ = T₁ − W and Y₂ = T₂ − W. Y₁ and Y₂ are not empty by hypothesis, and W, Y₁ and Y₂ are a partition of T. For each A_i ∈ T, 1 ≤?? i ≤?? k, we consider two values a_i, a_i′ ∈ dom(A_i), such that a_i ≠ a_i′. Let’s build a relation r with attributes WY₁Y₂ constituted by the two tuples:

e₁[A_i] = a_i, 1 ≤? i ≤?? k ?

e₂[A_i] = a_i if A_i ∈ W; a_i′ if A_i ∈ Y₁Y₂

r satisfies each dependency V → Z ∈ F. In fact, if V ⊈ W, then e₁[V] ≠ e₂[V], and r obviously satisfies the dependency. If V ⊆ W, then (T₁ ∩ T₂) → V, so (T₁ ∩ T₂) → Z for transitivity, from which Z ⊆ W, and so e₁[Z] = e₂[Z], an this implies that r satifies the dependency. Moreover, since Y₁ and Y₂ are not empty, π _T1 (r ) and π _T2 (r ) contain two tuples and their natural join contains four tuples, more than those of r:

π _T1 (r ) ⨝ π _T2 (r )

contradicting the hypothesis.