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$ and $R_2$ you will guarantee a Lossless-Join if $R_1$⋈$R_2$ = $R$.

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 in $F$):

• $R_1$ ∩ $R_2$ → $R_1 - R_2$
• $R_1$ ∩ $R_2$ → $R_2 - R_1$

Example

• Let $R = (A, B, C, D)$ be the relation schema, with $A$, $B$, $C$ and $D$ attributes.
• Let $F = \{ A \rightarrow 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)$ and $A \rightarrow BC$ so $R_1 \cap R_2 \rightarrow R_1 - R_2$.

Normal Forms

Decomposition into BCNF or 3NF must always be lossless.