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]}

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. Maier, David (1983). The theory of relational databases (PDF). Computer Science Press. p. 101. ISBN   0-914894-42-0 . Retrieved 16 August 2024.
4. Ullman, Jeffrey D. (1988). Principles of Database and Knowledge-base Systems (PDF) (1 ed.). Computer Science Press. p. 397. ISBN   0-88175188-X . Retrieved 16 August 2024.
5. "Lossless-Join Decomposition". Cs.sfu.ca. Retrieved 2016-02-07.
6. "www.data-e-education.com - Lossless Join Decomposition". Archived from the original on 2014-02-21. Retrieved 2014-02-12.