Dependency preserving

1. DAVID DENG
CS157B
MARCH 23, 2010
Dependency Preserving
Decomposition

2. Intro
Decomposition help us eliminate redundancy, root
of data anomalies.
Decomposition should be:
1. Lossless
2. Dependency Preserving

3. What’s Dependency Preservation?
When the decomposition of a relational scheme
preserved the associated set of functional
dependencies.
Formal Definition:
If R is decomposed into R1, R2,…, Rn, then
{F1ÈF2È…ÈFn}
+
= F
+

4. Algorithm to check for Dependency Preservation
begin;
for each X  Y in F and with R (R1, R2, …, Rn)
{
let Z = X;
while there are changes in Z
{
from i=1 to n
Z = Z È ((Z Ç Ri)
+
Ç Ri) w.r.t to F;
}
if Y is a proper subset of Z, current fd is preserved
else decomposition is not dependency preserving;
}
this is a dependency preserving decomposition;
end;

5. Explain Algorithm Part 1
1. Choose a functional dependency in set F, say you choose
X  Y.
2. Let set Z to the “left hand side” of the functional
dependency, X such Z = X

Starting with R1 in the decomposed set {R1, R2,…Rn)
3. Intersect Z with R1, Z Ç R1
4. Find the closure of the result from step 3 (Z Ç R1) using
original set F
5. Intersect the result from step 4 ((Z Ç R1)
+
) with R1 again.

6. Explain Algorithm Part 2
6. Updated Z with new attribute in the result from step 5.
7. Repeat step 3-6 from R2, R3, …, Rn.
8. If there’s any changes between original Z before step 3
and after step 7, repeat step 3-7.

9. Check whether Y is a proper subset of current Z. If it is
not, this decomposition is a violation of dependency
preservation. You can stop now.
10. If Y is a proper subset of current Z, repeat 1-9 until you
check ALL functional dependencies in set F.

7. Another look at Algorithm
Test each X  Y in F for dependency preservation
result = X
while (changes to result) do
for each Ri in decomposition
t = (result Ç Ri)+ Ç Ri
result = result È t
if Y Í result, return true;
else, return false;
[Note: If any false is returned for algorithm, whole
decomposition is not dependency preserving.]

8. Let’s walk through an example
of using this algorithm.

9. Example using Algorithm
Given the following:
R(A,B,C,D,E)
F = {ABC, CE, BD, EA}
R1(B,C,D)R2(A,C,E)
Is this decomposition dependency preserving?

10. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=AB
For Z Ç R1 = AB Ç BCD = B
{B}
+
= BD
{B}
+
Ç R1 = BD Ç BCD = BD
Update Z = AB È BD = ABD, continue

11. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=ABD
For Z Ç R2 = ABD Ç ACE = A
{A}
+
= A
{A}
+
Ç R2 = A Ç ACE = A
Update Z, Z is still ABD
Since Z changed, repeat checking R1 to R2.

12. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=ABD
For Z Ç R1 = ABD Ç BCD = BD
{BD}
+
= BD
{BD}
+
Ç R1 = BD Ç BCD = BD
Update Z = ABD È BD = ABD, so Z hasn’t
changed but you still have to continue.

13. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=ABD and checking R2 was done 2 slides ago
Z will still be ABD.
Since Z hasn’t change, you can conclude ABC
is not preserved.
Let’s practice with other functional
dependencies.

14. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=X=B
For Z Ç R1 = B Ç BCD = B
{B}
+
= BD
{B}
+
Ç R1 = BD Ç BCD = BD
Update Z = B È BD = BD
Since Y=D is proper subset of BD, BD is
preserved.

15. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=X=C
For Z Ç R2 = C Ç ACE = C
{C}
+
= CEA
{C}
+
Ç R1 = CEA Ç ACE = ACE
Update Z = C ÈACE= ACE
Since Y=E is proper subset of ACE, CE is
preserved.

16. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Z=X=E
For Z Ç R1 = E Ç ACE = E
{E}
+
= EA
{E}
+
Ç R1 = EA Ç ACE = EA
Update Z = E È EA= EA
Since Y=A is proper subset of EA, EA is
preserved.

17. Example
R(A,B,C,D,E) F = {ABC, CE, BD, EA}
Decomposition:R1(B,C,D)R2(A,C,E)
Shortcut:
For any functional dependency, if both LHS
and RHS collectively are within any of the
sub scheme Ri. Then this functional
dependency is preserved.

18. Exercise #1
Let R{A,B,C,D}
and
F={AB, BC, CD, DA}
Let’s decomposed R into
R1 = AB, R2 = BC, and R3 = CD
Is this a dependency preserving decomposition?

19. Answer to Exercise #1
Yes it is.
You can immediately see that AB, BC, CD are
preserved for R1, R2, R3
The key is to check whether DA is preserved.
Let’s walk through the algorithm.

R{A,B,C,D} F={AB, BC, CD, DA}
Decomposition: R1 = AB, R2 = BC, and R3 = CD

20. Answer to Exercise #1
Z = X = D
For Z Ç R1 = D Ç AB = empty set
For Z Ç R2 = D Ç BC = empty set
For Z Ç R3 = D Ç CD = D
Find {D}
+
= DABC
Find {D}
+
Ç R3 = DABC Ç CD = CD
Update Z to CD. Since Z changed, repeat.
R{A,B,C,D} F={AB, BC, CD, DA}
Decomposition: R1 = AB, R2 = BC, and R3 = CD

21. Answer to Exercise #1
Z = CD
For Z Ç R1 = CD Ç AB = empty set
For Z Ç R2 = CD Ç BC = C
Find {C}
+
= CDAB
Find {C}
+
Ç R2 = CDAB Ç BC = BC
Update Z = CD È BC = BCD
R{A,B,C,D} F={AB, BC, CD, DA}
Decomposition: R1 = AB, R2 = BC, and R3 = CD

22. Answer to Exercise #1
Z = BCD
For Z Ç R3 = BCD Ç CD = CD
Find {CD}+ = CDAB
Find {CD}+ Ç R3 = CDAB Ç CD = CD
Update Z is still BCD. Since Z changed, repeat going
trough R1 to R3.
R{A,B,C,D} F={AB, BC, CD, DA}
Decomposition: R1 = AB, R2 = BC, and R3 = CD

23. Answer to Exercise #1
Z = BCD
For Z Ç R1 = BCD Ç AB = B
Find {B}
+
= BCDA
Find {B}
+
Ç R1 = BCDA Ç AB = AB
Update Z = BCD È AB = ABCD.
Since Y = A is a subset of ABCD, function DA is
preserved.
R{A,B,C,D} F={AB, BC, CD, DA}
Decomposition: R1 = AB, R2 = BC, and R3 = CD

24. Exercise #2
R{A,B,C,D,E)
F={ABD, BE}
Decomposition:
R1{A,B,C}R2{A,D}R3{B,D,E}
Is this a dependency preserving decomposition?

25. Answer to Exercise #2
Let’s start with ABD:
Z = A
Z Ç R1 = A Ç ABC = A
{A}
+
= ABDE
{A}
+
Ç R1 = ABDE Ç ABC = AB
Update Z = A È AB = AB
R{A,B,C,D,E) F={ABD, BE}
Decomposition: R1{A,B,C} R2{A,D}R3{B,D,E}

26. Answer to Exercise #2
Z = AB
Z Ç R2 = A Ç AD = A
{A}
+
= ABDE
{A}
+
Ç R1 = ABDE Ç AD = AD
Update Z = AB È AD = ABD
Thus A BD preserved
R{A,B,C,D,E) F={ABD, BE}
Decomposition: R1{A,B,C} R2{A,D}R3{B,D,E}

27. Answer to Exercise #2
Based on R3, BE is preserved.
Check B  E:
Z = B
Z Ç R1 = B Ç ABC = B
{B}
+
= BE
{B}
+
Ç R1 = BE Ç ABC = B
Update Z = B still the same
R{A,B,C,D,E) F={ABD, BE}
Decomposition: R1{A,B,C} R2{A,D}R3{B,D,E}

28. Answer to Exercise #2
Z = B
Z Ç R2 = B Ç AD = empty set
Z Ç R3 = B Ç BDE = B
{B}
+
= BE
{B}
+
Ç R3 = BE Ç BDE = BE
Update Z = B È BE = BE
Thus BE preserved
R{A,B,C,D,E) F={ABD, BE}
Decomposition: R1{A,B,C} R2{A,D}R3{B,D,E}

29. End
Reference:
Yu Hung Chen, “Decomposition”,
http://www.cs.sjsu.edu/faculty/lee/cs157/Decomposition_Yu
HungChen.ppt, SJSU (lol), 2005
Gary D. Boetticher, “Preserving Dependencies”,
http://www.youtube.com/watch?v=olgwucI3thI, University
of Houston Clear Lake, 2009
Dr. C. C. Chan, “Example of Dependency Preserving
Decomposition”,
http://www.cs.uakron.edu/~chan/cs475/Fall2000/Example
Dp%20decomposition.htm, University of Akron, Fall 2000
Tang Nan, “Functional Dependency”,
http://www.se.cuhk.edu.hk/~seg3550/2006/tutorial/t9.ppt