Lossless join decomposition
In database design, a lossless join decomposition is a decomposition of a relation into relations 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]
Criteria
Lossless join can also be called nonadditive.[2]
If is split into and , for this decomposition to be lossless (i.e., ) then at least one of the two following criteria should be met.
Check 1: Verify join explicitly
Projecting on and , and joining them back, results in the relation you started with.[3][unreliable source?]
Check 2: Via functional dependencies
Let be a relation schema.
Let F be a set of functional dependencies on .
Let and form a decomposition of .
The decomposition is lossless if one of the sub-relations (i.e. or ) is a subset of the closure of their intersection. In other words, the decomposition is a lossless-join decomposition of if at least one of the following functional dependencies are in F+ (where F+ stands for the closure for every attribute or attribute sets in F):[4]
Criteria for multiple sub-relations
Multiple sub-relations have a lossless join if there is some way in which we can repeatedly perform lossless joins until all the relations have been joined into a single relation. Once we have a new sub-relation made from a lossless join, we are not allowed to use any of its isolated sub-relations to join with any of the other relations. For example, if we can do a lossless join on a pair of relations to form a new relation , we use this new relation (rather than or ) to form a lossless join with another relation (which may already be joined (e.g., )).
Examples
- Let be the relation schema, with attributes A, B, C and D.
- Let be the set of functional dependencies.
- Decomposition into and is lossless under F because . A is a superkey in , meaning we have a functional dependency . In other words, now we have proven that .
References
- ^ Pohler, K (2015). "Lossless-Join Decomposition: applications in quantitative computing metrics". International Journal of Applied Computer Science. 21 (4): 190–212.
- ^ Elmasri, Ramez (2016). Fundamentals of database systems (Seventh ed.). Hoboken, NJ: Pearson. p. 461. ISBN 978-0133970777.
- ^ "Lossless Join Property". Stackoverflow.com. Retrieved 2016-02-07.
- ^ "Lossless Join Decomposition" (PDF). University at Buffalo. Jan Chomicki. Retrieved 2012-02-08.
- ^ "Lossless-Join Decomposition". Cs.sfu.ca. Retrieved 2016-02-07.
- ^ "www.data-e-education.com - Lossless Join Decomposition". Archived from the original on 2014-02-21. Retrieved 2014-02-12.