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.

Definition

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

Decompositions into more than two schemas can be defined in the same way.

Criteria

A decomposition $R=R_1\cup R_2$ has a lossless join with respect to $F$ if and only if the closure of $R_1\cap R_2$ includes $R_1\setminus R_2$ or $R_2\setminus R_1$. In other words, one of the following must hold:

• $(R_1\cap R_2)\to (R_1\setminus R_2)\in F^{+}$
• $(R_1\cap R_2)\to (R_2\setminus R_1)\in F^{+}$

Criteria for multiple sub-schemas

Multiple sub-schemas $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 $R_i,R_j$ to form a new schema $R_{i,j}$, we use this new schema (rather than $R_i$ or $R_j$) to form a lossless join with another schema $R_k$ (which may already be joined (e.g., $R_{k,l}$)).Template:Vague

Example

• Let $R=\{A,B,C,D\}$ be the relation schema, with attributes Template:Mvar, Template:Mvar, Template:Mvar and Template:Mvar.
• Let $F=\{A\to BC\}$ be the set of functional dependencies.
• Decomposition into $R_1=\{A,B,C\}$ and $R_2=\{A,D\}$ is lossless under Template:Mvar because $R_1\cap R_2=A$ and we have a functional dependency $A\to BC$. In other words, we have proven that $(R_1\cap R_2\to R_1\setminus R_2)\in F^{+}$.