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

Changes access method for non-correlated subquery

2  Asked on March 2, 2021 by rfusca


Restart ORACLE OHAS without restarting databases

1  Asked on March 1, 2021 by mikhail-aksenov


Postgres – Find index order ASC or DESC

1  Asked on February 28, 2021 by bhuvanesh


How can I check my config files my.cnf for example

0  Asked on February 27, 2021 by plisken


How often does Postgres or Mysql make the fsync call?

4  Asked on February 23, 2021 by user1870400


Handling the foreign keys in data entry

1  Asked on February 22, 2021 by ramy-khalifa


Non-yielding issue on SQL Server

1  Asked on February 19, 2021 by titanl0rd


PostgreSQL: Check the structure of foreign tables

1  Asked on February 19, 2021 by radu-dumbrveanu


Order of returned rows with IN statement

2  Asked on February 18, 2021 by gandalf-stormcrow


Ask a Question

Get help from others!

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