Define dependency preservation / What is dependency preservation? / Why do we need dependency preserving decomposition? / The need for dependency preserving decomposition / dependency preserving decomposition example / What is dependency Preservation property for decomposition? / Why dependency preservation is important? / Dependency preservation property of normalization process
Dependency Preservation
A
decomposition of a relation R into R1, R2, R3,
…, Rn is dependency preserving decomposition with respect to the set
of Functional Dependencies F that hold on R only if the following is hold;
(F1 U F2 U F3 U … U Fn)+
= F+
where,
F1,
F2, F3, …, Fn – Sets of
Functional dependencies of relations R1, R2, R3,
…, Rn.
(F1
U F2 U F3 U … U Fn)+ - Closure
of Union of all sets of functional dependencies.
F+ -
Closure of set of functional dependency F of R.
If
the closure of set of functional dependencies of individual relations R1,
R2, R3, …, Rn are equal to the set of
functional dependencies of the main relation R (before decomposition), then we
would say the decomposition D is lossless dependency preserving decomposition.
Discussion with Example of Non-dependency preserving decomposition:
Dependency
preservation is a concept that is very much related to Normalization process. Remember
that the solution for converting a relation into a higher normal form is to
decompose the relation into two or more relations. This is done using the set
of functional dependencies identified in the lower normal form state.
For example,
let us assume a relation R (A, B, C, D) with set of functional dependencies F =
{A→B, B→C, C→D}. There
is no partial dependency in the given set F. Hence, this relation is in 2NF.
Is
R (A, B, C, D) in 3NF? No. The reason is Transitive Functional Dependency. How do
we convert R into 3NF? The solution is decomposition.
Assume that we decompose
R(A, B, C, D) into R1(A, C, D) and R2(B, C).
In
R1(A, C, D), the FD C→D holds. In
R2(B, C), the FD B→C holds. But,
there is no trace of the FD A→B. Hence,
this decomposition does not preserve dependency.
What
wrong would the above decomposition cause?
In
R, the following were held;
- value of B depends on value of A,
- value of C depends on value of B,
- value of D depends on value of C.
after
decomposition, the relations R1 and R2 are holding the following;
- value of C depends on value of B,
- value of D depends on value of C.
The
dependency A→B is missing. This causes acceptance
of any values for B in R2. It causes duplicate values to be entered into R2 for B which may not depend on A. If
we would like to avoid this type of duplication, then we need to perform a join operation between R1 and R2 to accept a new value for B which is costlier
operation. Hence, we demand the decomposition to be a dependency preserving
decomposition.
Few
key points;
- We would like to check easily that updates to the database do not result in illegal relations being created.
- It would be nice if our design allowed us to check updates without having to compute natural joins.
- We can permit a non-dependency preserving decomposition if the database is static. That is, if there is no new insertion or update in the future.
Example:
Assume
R(A, B, C, D) with FDs A→B, B→C, C→D.
Let
us decompose R into R1 and R2 as follows;
R1(A,
B, C)
R2(C,
D)
The
FDs A→B, and B→C are hold in R1.
The
FD C→D holds in R2.
All the functional dependencies hold here. Hence,
this decomposition is dependency preserving.