Explain lossless join decomposition and dependency preserving decomposition.

Mumbai University > Computer Engineering > Sem 4 > Database Management System

Marks: 5M

Year: May 2014

1 Answer

Lossless Join Decomposition:

  • The lossless join property is a feature of decomposition supported by normalization. It is the ability to ensure that any instance of the original relation can be identified from corresponding instances in the smaller relations.

    R : relation, F : set of functional dependencies on R,

    X,Y : decomposition of R

  • A decomposition {R1, R2,…, Rn} of a relation R is called a lossless decomposition for R if the natural join of R1, R2,…, Rn produces exactly the relation R.
  • A decomposition is lossless if we can recover:

    R(A, B, C) -> Decompose -> R1(A, B) R2(A, C) -> Recover -> R’(A, B, C)

    Thus,R’ = R

  • Decomposition is lossles if :

    X ∩ Y -> X, that is: all attributes common to both X and Y functionally determine ALL the attributes in X.

    X ∩ Y -> Y, that is: all attributes common to both X and Y functionally determine ALL the attributes in Y

    If X ∩ Y forms a superkey of either X or Y, the decomposition of R is a lossless decomposition.

Dependency Preserving Decomposition:

  • A decomposition D = {R1, R2, ..., Rn} of R is dependency-preserving with respect to F if the union of the projections of F on each Ri in D is equivalent to F;

    if (F1∪ F2 ∪ …∪Fn)+ = F +

  • Example-

    R= (A, B, C )

    F = {A ->B, B->C}

    Key = {A}

    Ris not in BCNF

    Decomposition R1 = (A, B), R2 = (B, C)

    R1 and R2 are in BCNF, Lossless-join decomposition, Dependency preserving

  • Each Functional Dependency specified in F either appears directly in one of the relations in the decomposition.
  • It is not necessary that all dependencies from the relation R appear in some relation Ri.
  • It is sufficient that the union of the dependencies on all the relations Ri be equivalent to the dependencies on R.
  • is lost in the decomposition
Please log in to add an answer.