Lossless join decomposition

In database design, a lossless join decomposition is a decomposition of a relation ${\displaystyle r}${\displaystyle r} into relations ${\displaystyle r_{1},r_{2}}${\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]

A relation ${\displaystyle r}${\displaystyle r} on schema ${\displaystyle R}${\displaystyle R} decomposes losslessly onto schemas ${\displaystyle R_{1}}${\displaystyle R_{1}} and ${\displaystyle R_{2}}${\displaystyle R_{2}} if ${\displaystyle \pi _{R_{1}}(r)\bowtie \pi _{R_{2}}(r)=r}${\displaystyle \pi _{R_{1}}(r)\bowtie \pi _{R_{2}}(r)=r}, that is ${\displaystyle r}${\displaystyle r} is the natural join of its projections onto the smaller schemas. A pair ${\displaystyle (R_{1},R_{2})}${\displaystyle (R_{1},R_{2})} is a lossless-join decomposition of ${\displaystyle R}${\displaystyle R} or said to have a lossless join with respect to a set of functional dependencies ${\displaystyle F}${\displaystyle F} if any relation ${\displaystyle r(R)}${\displaystyle r(R)} that satisfies ${\displaystyle F}${\displaystyle F} decomposes losslessly onto ${\displaystyle R_{1}}${\displaystyle R_{1}} and ${\displaystyle R_{2}}${\displaystyle R_{2}}.^[3]

Decompositions into more than two schemas can be defined in the same way.^[4]

A decomposition ${\displaystyle R=R_{1}\cup R_{2}}${\displaystyle R=R_{1}\cup R_{2}} has a lossless join with respect to ${\displaystyle F}${\displaystyle F} if and only if the closure of ${\displaystyle R_{1}\cap R_{2}}${\displaystyle R_{1}\cap R_{2}} includes ${\displaystyle R_{1}\setminus R_{2}}${\displaystyle R_{1}\setminus R_{2}} or ${\displaystyle R_{2}\setminus R_{1}}${\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_{1}\setminus R_{2})\in F^{+}}
• ${\displaystyle (R_{1}\cap R_{2})\to (R_{2}\setminus R_{1})\in F^{+}}${\displaystyle (R_{1}\cap R_{2})\to (R_{2}\setminus R_{1})\in F^{+}}

Multiple sub-schemas ${\displaystyle R_{1},R_{2},...,R_{n}}${\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}}${\displaystyle R_{i},R_{j}} to form a new schema ${\displaystyle R_{i,j}}${\displaystyle R_{i,j}}, we use this new schema (rather than ${\displaystyle R_{i}}${\displaystyle R_{i}} or ${\displaystyle R_{j}}${\displaystyle R_{j}}) to form a lossless join with another schema ${\displaystyle R_{k}}${\displaystyle R_{k}} (which may already be joined (e.g., ${\displaystyle R_{k,l}}${\displaystyle R_{k,l}})).^{[vague ]}

• Let ${\displaystyle R=\{A,B,C,D\}}${\displaystyle R=\{A,B,C,D\}} be the relation schema, with attributes A, B, C and D.
• Let ${\displaystyle F=\{A\rightarrow BC\}}${\displaystyle F=\{A\rightarrow BC\}} be the set of functional dependencies.
• Decomposition into ${\displaystyle R_{1}=\{A,B,C\}}${\displaystyle R_{1}=\{A,B,C\}} and ${\displaystyle R_{2}=\{A,D\}}${\displaystyle R_{2}=\{A,D\}} is lossless under F because ${\displaystyle R_{1}\cap R_{2}=A}${\displaystyle R_{1}\cap R_{2}=A} and we have a functional dependency ${\displaystyle A\rightarrow BC}${\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^{+}}${\displaystyle (R_{1}\cap R_{2}\rightarrow R_{1}\setminus R_{2})\in F^{+}}.^{[5] [6]}

• Join dependency
• Fifth normal form

• Databases
• Data modeling
• Database constraints
• Database normalization
• Relational algebra

• Articles with short description
• Short description is different from Wikidata
• All Wikipedia articles needing clarification
• Wikipedia articles needing clarification from August 2024