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

Definition

A relation ${\displaystyle r}$ on schema ${\displaystyle R}$ decomposes losslessly onto schemas ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$ if ${\displaystyle \pi _{R_{1}}(r)\bowtie \pi _{R_{2}}(r)=r}$, that is ${\displaystyle r}$ is the natural join of its projections onto the smaller schemas. A pair ${\displaystyle (R_{1},R_{2})}$ is a lossless-join decomposition of ${\displaystyle R}$ or said to have a lossless join with respect to a set of functional dependencies ${\displaystyle F}$ if any relation ${\displaystyle r(R)}$ that satisfies ${\displaystyle F}$ decomposes losslessly onto ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$.^[3]

Decompositions into more than two schemas can be defined in the same way.^[4]

Criteria

A decomposition ${\displaystyle R=R_{1}\cup R_{2}}$ has a lossless join with respect to ${\displaystyle F}$ if and only if the closure of ${\displaystyle R_{1}\cap R_{2}}$ includes ${\displaystyle R_{1}\setminus R_{2}}$ or ${\displaystyle R_{2}\setminus R_{1}}$. In other words, one of the following must hold:^[4]

• ${\displaystyle (R_{1}\cap R_{2})\to (R_{1}\setminus R_{2})\in F^{+}}$
• ${\displaystyle (R_{1}\cap R_{2})\to (R_{2}\setminus R_{1})\in F^{+}}$

Criteria for multiple sub-schemas

Multiple sub-schemas ${\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 schemas have been joined into a single schema. Once we have a new sub-schema made from a lossless join, we are not allowed to use any of its isolated sub-schema to join with any of the other schemas. For example, if we can do a lossless join on a pair of schemas ${\displaystyle R_{i},R_{j}}$ to form a new schema ${\displaystyle R_{i,j}}$, we use this new schema (rather than ${\displaystyle R_{i}}$ or ${\displaystyle R_{j}}$) to form a lossless join with another schema ${\displaystyle R_{k}}$ (which may already be joined (e.g., ${\displaystyle R_{k,l}}$)).^[vague]

Example

• 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}$ and we have a functional dependency ${\displaystyle A\rightarrow BC}$. In other words, we have proven that ${\displaystyle (R_{1}\cap R_{2}\rightarrow R_{1}\setminus R_{2})\in F^{+}}$.^[5][6]