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

Marks: 5M

Year: May 2014

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