Lossless-Join Decomposition

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

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

Lossless-join Decomposition[edit]

Can also be called Nonadditive. If you decompose a relation R into relations R_1 and R_2 you will guarantee a Lossless-Join if R_1R_2 = R.

If R is split into R1 and R2, for the decomposition to be lossless then at least one of the two should hold true.

Projecting on R1 and R2, and joining back, results in the relation you started with.[1] Let R be a relation schema.

Let F be a set of functional dependencies on R.

Let R_1 and R_2 form a decomposition of R.

The decomposition is a lossless-join decomposition of R 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):[2]

  • R_1 ∩ R_2R_1
  • R_1 ∩ R_2R_2

Example[edit]

  • Let R = (A, B, C, D) be the relation schema, with A, B, C and D attributes.
  • 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), A is a superkey in R_1 ( A \rightarrow BC ) so R_1 \cap R_2 \rightarrow R_1.

[3] [4]

References[edit]