# Lossless Join Decomposition Criteria

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
F):

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?

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 )

Answered by Renzo on December 23, 2020

## Related Questions

### I’m considering removing SQL Server Partitioning from a Database. Is there anything I should watch out for?

0  Asked on October 28, 2021 by user8440261

### Perform SELECT using WHERE IN clause on JSON Object in MySQL

1  Asked on October 28, 2021 by girish

### Is Buffer Pool Extension (BPE) needed if my database is already on SSD?

1  Asked on October 28, 2021 by jyao

### Cannot connect after Availability Group automatic failover

1  Asked on October 28, 2021

### What is branching factor of mysql myisam’s b-tree

1  Asked on October 28, 2021

### Table as an Index?

0  Asked on October 28, 2021 by akagixxer

### How do you combine multiple update statements for the same row using MySQL trigger

1  Asked on October 28, 2021

### Index usage for database: where are the sys tables located

0  Asked on October 28, 2021

### How to get the list of foreign key together with the index name on that foreign key?

0  Asked on October 28, 2021 by anony-mous

### Source Control Dynamics

0  Asked on October 28, 2021 by johnff

### Cannot use “ON CONFLICT” with postgres updatable view and partial index

1  Asked on October 28, 2021

### What is the maximum latency / distance mysql replication can tolerate without having errors or wrong data?

2  Asked on October 28, 2021 by malazzar

### RDS MSSQL in-place upgrade how to update master db compatibility level when rdsa account is db owner

0  Asked on October 28, 2021 by dev_etter

### How to get non-overlapping distinct intervals from a PostgreSQL table?

2  Asked on October 28, 2021

### Find friends of friends (recursively) efficiently using Postgresql

1  Asked on October 28, 2021 by viktor-vsk

### SQL Server setting up logins for backup site

1  Asked on October 28, 2021 by user1430949

### Group by time interval and output the source and destination station_id and count

2  Asked on October 28, 2021 by deepan-kaviarasu

### Diagnose slow script executions on specific server

2  Asked on October 28, 2021 by lvaro-gonzlez

### Mysql How to update n rows using count function?

1  Asked on October 28, 2021 by fakipo

### User on SQLAgentOperatorRole unable to edit jobs

1  Asked on October 28, 2021 by hikari

Get help from others!