written 8.2 years ago by | • modified 2.8 years ago |
Mumbai University > Computer Engineering > Sem 4 > Database Management System
Marks: 5M
Year: May 2014
written 8.2 years ago by | • modified 2.8 years ago |
Mumbai University > Computer Engineering > Sem 4 > Database Management System
Marks: 5M
Year: May 2014
written 8.2 years ago by |
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 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