Lossless join decomposition

In database design, a lossless join decomposition is a decomposition of a relation r into relations r_1, r_2 such that a natural join of the two smaller relations yields back the original relation.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In database design, a lossless join decomposition is a decomposition of a relation 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. Lossless join can also be called non-additive.

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^+

Example

Let R = \{A, B, C, D\} be the relation schema, with attributes , , and . 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 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^+ .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1379007379 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.