Dependency Preservation

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 R₁, R₂, R₃, …, R_n is dependency preserving decomposition with respect to the set of Functional Dependencies F that hold on R only if the following is hold;

(F₁ U F₂ U F₃ U … U F_n)⁺ = F⁺

where,

F₁, F₂, F₃, …, F_n – Sets of Functional dependencies of relations R₁, R₂, R₃, …, R_n.

(F₁ U F₂ U F₃ U … U F_n)⁺ - 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 R₁, R₂, R₃, …, R_n 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.