Lossless Join Decomposition Criteria

Database Administrators Asked by Kevin Wu on December 23, 2020

On Wikipedia, it says:

The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in
F+ (where
F+ stands for the closure for every attribute or attribute sets in

R1 ∩ R2 → R1 or R1 ∩ R2 → R2

Unfortunately, I do not understand this criteria. It is known that the decomposition is lossless if the join of R1 and R2 is R, but how is this derivable from the criteria above?

One Answer

Here is the proof.

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

The case T1 ∩ T2 → T2 ∈ 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 T1 ∩ T2 → T1 ∈ F+ or T1 ∩ T2 → T2 ∈ F+.

Using reductio ad absurdum, we suppose that none of the two functional dependencies is implied by F. Let W = (T1 ∩ T2)+, Y1 = T1 − W and Y2 = T2 − W. Y1 and Y2 are not empty by hypothesis, and W, Y1 and Y2 are a partition of T. For each Ai ∈ T, 1 ≤?? i ≤?? k, we consider two values ai, ai′ ∈ dom(Ai), such that ai ≠ ai′. Let’s build a relation r with attributes WY1Y2 constituted by the two tuples:

e1[Ai] = ai, 1 ≤? i ≤?? k ?

e2[Ai] = ai if Ai ∈ W; ai′ if Ai ∈ Y1Y2

r satisfies each dependency V → Z ∈ F. In fact, if V ⊈ W, then e1[V] ≠ e2[V], and r obviously satisfies the dependency. If V ⊆ W, then (T1 ∩ T2) → V, so (T1 ∩ T2) → Z for transitivity, from which Z ⊆ W, and so e1[Z] = e2[Z], an this implies that r satifies the dependency. Moreover, since Y1 and Y2 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.

Answered by Renzo on December 23, 2020

Add your own answers!

Related Questions

Table as an Index?

0  Asked on October 28, 2021 by akagixxer


Source Control Dynamics

0  Asked on October 28, 2021 by johnff


SQL Server setting up logins for backup site

1  Asked on October 28, 2021 by user1430949


Diagnose slow script executions on specific server

2  Asked on October 28, 2021 by lvaro-gonzlez


Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP