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. Lossless join can also be called non-additive.

Criteria

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

The decomposition is lossless if and only if the natural join of $R_{1}$ and $R_{2}$ results in the original relation $R$ (i.e., $R_{1}\bowtie R_{2}=R$).

Equivalently, the decomposition is lossless if and only if one of the sub-relations (i.e. $R_{1}$ or $R_{2}$) is a subset of the closure of their intersection. In other words, the decomposition of $R$ is lossless if either $R_{1}\subseteq [R_{1}\cap R_{2}]^{+}$ or $R_{2}\subseteq [R_{1}\cap R_{2}]^{+}$ is true.

Criteria for multiple sub-relations

Multiple sub-relations $R_{1},R_{2},...,R_{n}$ have a lossless join if there is some way in which we can repeatedly perform lossless joins until all the relations have been joined into a single relation. Once we have a new sub-relation made from a lossless join, we are not allowed to use any of its isolated sub-relations to join with any of the other relations. For example, if we can do a lossless join on a pair of relations $R_{i},R_{j}$ to form a new relation $R_{i,j}$, we use this new relation (rather than $R_{i}$ or $R_{j}$) to form a lossless join with another relation $R_{k}$ (which may already be joined (e.g., $R_{k,l}$)).

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^{+}$.