Lossless join decomposition explained

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.^[1] Lossless join can also be called non-additive.^[2]

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} .^[3]

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:^[4] (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} )).

Example

• Let

R = \{A, B, C, D\} be the relation schema, with attributes,, and .

• Let

F = \{ A → BC \} be the set of functional dependencies.

• Decomposition into

R _{1} = \{A, B, C\} and R _{2} = \{A, D\} is lossless under because R _{1} \cap R _{2} = A and we have a functional dependency A → BC . In other words, we have proven that (R _{1} \cap R _{2} → R _{1} \setminus R _{2)} \in F ^{+} .^{[5] [6]}

Notes and References

1. Pohler . K . Lossless-Join Decomposition: applications in quantitative computing metrics . International Journal of Applied Computer Science . 2015 . 21 . 4 . 190–212.
2. Book: Elmasri . Ramez . Fundamentals of database systems . 2016 . Pearson . 978-0133970777 . Seventh . Hoboken, NJ . 461.
3. Book: Maier . David . The theory of relational databases . 1983 . Computer Science Press . 0-914894-42-0 . 101 . 16 August 2024.
4. Book: Ullman . Jeffrey D. . Principles of Database and Knowledge-base Systems . 1988 . Computer Science Press . 0-88175188-X . 397 . 1 . 16 August 2024.
5. Web site: Lossless-Join Decomposition. Cs.sfu.ca. 2016-02-07.
6. Web site: www.data-e-education.com - Lossless Join Decomposition . 2014-02-12 . https://web.archive.org/web/20140221081148/http://www.data-e-education.com/E121_Lossless_Join_Decomposition.html . 2014-02-21 . dead.