Lossless join decomposition

This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (July 2014)

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] Lossless join can also be called nonadditive.^[2]

Criteria[edit]

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

The decomposition is lossless if and only if the natural join of ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$ results in the original relation ${\displaystyle R}$ (i.e., ${\displaystyle R_{1}\bowtie R_{2}=R}$).^{[3][unreliable source?]}

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

Criteria for multiple sub-relations[edit]

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[edit]

• 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[edit]