Lossless join decomposition

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.

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:

• (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 A, B, C and D.
• 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 we have a functional dependency A \rightarrow BC. In other words, we have proven that (R_1 \cap R_2 \rightarrow R_1 \setminus R_2) \in F^+.

References

References

1. (2015). "Lossless-Join Decomposition: applications in quantitative computing metrics". International Journal of Applied Computer Science.
2. (2016). "Fundamentals of database systems". Pearson.
3. (1983). "The theory of relational databases". Computer Science Press.
4. (1988). "Principles of Database and Knowledge-base Systems". Computer Science Press.
5. "Lossless-Join Decomposition".
6. "www.data-e-education.com - Lossless Join Decomposition".