Lossless-Join Decomposition

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science the concept of a Lossless-Join Decomposition is central in removing redundancy safely from databases while preserving the original data.[1]

Lossless-join Decomposition[edit]

Can also be called Nonadditive.[citation needed] If you decompose a relation into relations you will have a Lossless-Join if a natural join of the two smaller relations yields back the original relation, i .e.;

.

If is split into and , for this decomposition to be lossless then at least one of the two following criteria should be met.

Check 1: Verify join explicitly[edit]

Projecting on and , and joining back, results in the relation you started with.[2]

Check 2: Via functional dependencies[edit]

Let be a relation schema.

Let F be a set of functional dependencies on .

Let and form a decomposition of .

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):[3]

Example[edit]

  • Let be the relation schema, with A, B, C and D attributes.
  • 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 .

[4][5]

References[edit]

  1. ^ Pohler, K (2015). "Lossless-Join Decomposition: applications in quantitative computing metrics". International Journal of Applied Computer Science. 21 (4): 190–212.
  2. ^ "Lossless Join Property". Stackoverflow.com. Retrieved 2016-02-07.
  3. ^ "Lossless Join Decomposition" (PDF). University at Buffalo. Jan Chomicki. Retrieved 2012-02-08.
  4. ^ "Lossless-Join Decomposition". Cs.sfu.ca. Retrieved 2016-02-07.
  5. ^ "Archived copy". Archived from the original on 2014-02-21. Retrieved 2014-02-12. Cite uses deprecated parameter |dead-url= (help)CS1 maint: archived copy as title (link)