Lossless-Join Decomposition

In computer science the concept of a Lossless-Join Decomposition is central in removing redundancy safely from databases while preserving the original data.

Lossless-join Decomposition

Can also be called Nonadditive. If you decompose a relation [math]\displaystyle{ R }[/math] into relations [math]\displaystyle{ R_1, R_2 }[/math] you will have a Lossless-Join if a natural join of the two smaller relations yields back the original relation, i .e.;

[math]\displaystyle{ R_1 \bowtie R_2 = R }[/math].

If [math]\displaystyle{ R }[/math] is split into [math]\displaystyle{ R_1 }[/math] and [math]\displaystyle{ R_2 }[/math], for this decomposition to be lossless then at least one of the two following criteria should be met.

Check 1: Verify join explicitly

Projecting on [math]\displaystyle{ R_1 }[/math] and [math]\displaystyle{ R_2 }[/math], and joining back, results in the relation you started with.

Check 2: Via functional dependencies

Let [math]\displaystyle{ R }[/math] be a relation schema.

Let F be a set of functional dependencies on [math]\displaystyle{ R }[/math].

Let [math]\displaystyle{ R_1 }[/math] and [math]\displaystyle{ R_2 }[/math] form a decomposition of [math]\displaystyle{ R }[/math] .

The decomposition is a lossless-join decomposition of [math]\displaystyle{ R }[/math] 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):

• [math]\displaystyle{ R_1 \cap R_2 \rightarrow R_1 }[/math]
• [math]\displaystyle{ R_1 \cap R_2 \rightarrow R_2 }[/math]

Example

• Let [math]\displaystyle{ R = (A, B, C, D) }[/math] be the relation schema, with A, B, C and D attributes.
• Let [math]\displaystyle{ F = \{ A \rightarrow BC \} }[/math] be the set of functional dependencies.
• Decomposition into [math]\displaystyle{ R_1 = (A, B, C) }[/math] and [math]\displaystyle{ R_2 = (A, D) }[/math] is lossless under F because [math]\displaystyle{ R_1 \cap R_2 = A) }[/math]. A is a superkey in [math]\displaystyle{ R_1 }[/math], meaning we have a functional dependency [math]\displaystyle{ \{A \rightarrow BC\} }[/math].  In other words, now we have proven that [math]\displaystyle{ (R_1 \cap R_2 \rightarrow R_1) \in F^+ }[/math].