Lossless-Join Decomposition

In computer science the concept of a Lossless-Join Decomposition is central in removing redundancy safely from databases while preserving the original data.

Lossless-join Decomposition

Can also be called Nonadditive. If you decompose a relation $R$ into relations $R_1,R_2$ you will have a Lossless-Join if a natural join of the two smaller relations yields back the original relation, i .e.;

$R_1\bowtie R_2=R$.

If $R$ is split into $R_1$ and $R_2$, for this decomposition to be lossless then at least one of the two following criteria should be met.

Check 1: Verify join explicitly

Projecting on $R_1$ and $R_2$, and joining back, results in the relation you started with.

Check 2: Via functional dependencies

Let $R$ be a relation schema.

Let F be a set of functional dependencies on $R$.

Let $R_1$ and $R_2$ form a decomposition of $R$ .

The decomposition is a lossless-join decomposition of $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):

• $R_1\cap R_2\to R_1$
• $R_1\cap R_2\to R_2$

Example

• Let $R=(A,B,C,D)$ be the relation schema, with A, B, C and D attributes.
• 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 F because $R_1\cap R_2=A)$. A is a superkey in $R_1$, meaning we have a functional dependency $\{A\to BC\}$.  In other words, now we have proven that $(R_1\cap R_2\to R_1)\in F^{+}$.