Lossless join decomposition

In database design, a lossless join decomposition is a decomposition of a relation ${\displaystyle R}$ into relations ${\displaystyle 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.^[1]

Criteria

Lossless join can also be called nonadditive.^[2]

If ${\displaystyle R}$ is split into ${\displaystyle R_{1}$ and ${\displaystyle R_{2}$, for this decomposition to be lossless (i.e., ${\displaystyle 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 ${\displaystyle R_{1}$ and ${\displaystyle R_{2}$, and joining them back, results in the relation you started with.^{[3][unreliable source?]}

Check 2: Via functional dependencies

Let ${\displaystyle R}$ be a relation schema.

Let F be a set of functional dependencies on ${\displaystyle R}$.

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

The decomposition is lossless if one of the sub-relations (i.e. ${\displaystyle R_{1}$ or ${\displaystyle R_{2}$) is a subset of the closure of their intersection. In other words, the decomposition is a lossless-join decomposition of ${\displaystyle 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):^[4]

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

Criteria for multiple sub-relations

Multiple sub-relations ${\displaystyle 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 ${\displaystyle R_{i},R_{j}$ to form a new relation ${\displaystyle R_{i,j}$, we use this new relation (rather than ${\displaystyle R_{i}$ or ${\displaystyle R_{j}$) to form a lossless join with another relation ${\displaystyle R_{k}$ (which may already be joined (e.g., ${\displaystyle R_{k,l}$)).

Examples

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

^[5][6]

References