Lossless join decomposition

(Redirected from 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]

Criteria

Lossless join can also be called nonadditive.[2]

If ${\displaystyle R}$ is split into ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$, for this decomposition to be lossless (i.e., ${\displaystyle R_{1}\bowtie R_{2}=R}$) then at least one of the two following criteria should be met.

Check 1: Verify join explicitly

Projecting on ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$, and joining them back, results in the relation you started with.[3][unreliable source?]

Check 2: Via functional dependencies

Let ${\displaystyle R}$ be a relation schema.

Let F be a set of functional dependencies on ${\displaystyle R}$.

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

The decomposition is a lossless-join decomposition of ${\displaystyle 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):[4]

• ${\displaystyle R_{1}\cap R_{2}\rightarrow R_{1}}$
• ${\displaystyle R_{1}\cap R_{2}\rightarrow R_{2}}$

Examples

• 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^{+}}$.

References

1. ^ Pohler, K (2015). "Lossless-Join Decomposition: applications in quantitative computing metrics". International Journal of Applied Computer Science. 21 (4): 190–212.
2. ^ Elmasri, Ramez (2016). Fundamentals of database systems (Seventh ed.). Hoboken, NJ: Pearson. p. 461. ISBN 978-0133970777.
3. ^ "Lossless Join Property". Stackoverflow.com. Retrieved 2016-02-07.
4. ^ "Lossless Join Decomposition" (PDF). University at Buffalo. Jan Chomicki. Retrieved 2012-02-08.
5. ^ "Lossless-Join Decomposition". Cs.sfu.ca. Retrieved 2016-02-07.
6. ^ "Archived copy". Archived from the original on 2014-02-21. Retrieved 2014-02-12.{{cite web}}: CS1 maint: archived copy as title (link)