Lossless join decomposition

In database design, a lossless join decomposition is a decomposition of a relation $R$ into relations $R_{1},R_{2}$ such that a natural join of the two smaller relations yields back the original relation. This is central in removing redundancy safely from databases while preserving the original data.

Criteria

Can also be called nonadditive.

If $R$ is split into $R_{1}$ and $R_{2}$, for this decomposition to be lossless (i.e., $R_{1}\bowtie R_{2}=R$) then at least one of the two following criteria should be met.

Check 1: Verify join explicitly

Projecting on $R_{1}$ and $R_{2}$, and joining them back, results in the relation you started with.

Check 2: Via functional dependencies

Let $R$ be a relation schema.

Let F be a set of functional dependencies on $R$.

Let $R_{1}$ and $R_{2}$ form a decomposition of $R$ .

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

• $R_{1}\cap R_{2}\rightarrow R_{1}$
• $R_{1}\cap R_{2}\rightarrow R_{2}$

Examples

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