Dependency preservation

How check dependency preservation in decomposition with example

1. MANASY JAYASURYA
Dept. of Computer Science & Applications
St.Mary’s College,Thrissur

2. Why Do We Preserve The Dependency?
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.

3. Definition
A decomposition D = {R
1
, R
2
, ..., R
n
} of R is
dependency-preserving with respect to F if the union
of the projections of F on each R
i
in D is equivalent to
F; that is
if (F
1
È F
2
È … È F
n
)
+
= F
+

4. In Layman’s Term
Each Functional Dependency specified in F
either appears directly in one of the
relations in the decomposition.

5. Continue…
It is not necessary that all dependencies from the
relation R appear in some relation R
i
. It is sufficient
that the union of the dependencies on all the
relations R
i
be equivalent to the dependencies on R.

6. Property of Dependency-Preservation
If a decomposition is not dependency-preserving,
therefore, that dependency is lost in the
decomposition.
FD
1
FD
2
FD
3
FD
4

7. Example of Dependency Preservation
R(A B C D)
FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
Decomposition:
R
1
(A B C) R
2
(C D)

8. FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
FD
1
FD
2
R
1
( A B C )

9. FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
FD
3
R
2
( C D )

10. FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
R
1
( A B C ) R
2
( C D )
Has all 3 functional dependencies!
Therefore, it’s preserving the
dependencies
FD
1
FD
2
FD
3

11. Example of Non-Dependency Preservation
R(A B C D)
FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
Decomposition:
R
1
(A C D) R
2
(B C)

12. FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
FD
3
R
1
( A C D )

13. FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
FD
2
R
2
( B C )

14. FD
1
: A  B
FD
2
: B  C
FD
3
: C  D
R
1
( A C D ) R
2
( B C )
Does not support FD
1
: A => B
Therefore, it does not preserve the
dependencies
FD
3
FD
2

15. More Example
R(A B C D E)
FD
1
: A  B
FD
2
: BC  D
Decomposition:
R
1
(A C E) R
2
(B C D) R
3
(A B)

16. FD
1
: A  B
FD
2
: BC  D
R
1
( A C E )
No Dependencies

17. FD
1
: A  B
FD
2
: BC  D
FD
2
R
2
( B C D )

18. FD
1
: A  B
FD
2
: BC  D
FD
1
R
3
( A B )

19. FD
1
: A  B
FD
2
: BC  D
R
1
( A C E ) R
2
( B C D )
Has all 2 functional dependencies!
Therefore, it’s preserving the
dependencies
FD
1
FD
2
R
3( A B )

20. Exercise Problem

21. R(A, B, C, D, E, F )
FD
1
: D  A, B
FD
2
: C  E, F
Decomposition:
R
1
( A, C, D )
R
2
( A, D, B )
R
3
( D, E, F )
R
4
( C, E, F )

22. R
1( A C D )
R
2
( A D B )
R
3
( D E F )
R
4
( C E F )
FD
1
FD
2
FD1: D  A, B
FD2: C  E, F

23. Answer
Yes!
This is a dependency-preservation