Example of Dependency Preserving Decomposition.
Let R = ABCD and F = {A B, B C, C D, D A}
Let a decomposition of R be R1 = AB, R2 = BC, and R3 = CD.
Show that the decomposition is dependency preserving, i.e., all FDs in F can be enforced (or derived) by the projections of F into F1, F2, and F3.
The solution is based on the following algorithm.
Input: X Y in F and a decomposition of R {R1, R2, …, Rn}
Output: return true if X Y is in G+, i.e., Y is a subset of Z else return false
begin
Z := X;
while changes to Z occur do
for i := 1 to n do
Z := Z ((Z Ri)+ Ri) w.r.t. F;
if Y is a subset of Z then return true
else return false;
end;
Solution. Since R1 = AB, A B can be projected into F1, so it is preserved. Similarly, B C is preserved based on R2, and C D is preserved based on R3. What remains to be shown is D A. Apply the above algorithm, we have
X = D and Z = X = D.
When i = 1, consider R1 = AB,
Z R1 = D AB = empty set, we will not get any new attributes.
When i = 2, consider R2 = BC,
Z R2 = D BC = empty set. Same as above.
When i = 3, consider R3 = CD,
Z R3 = D CD = D. Compute D+ in F, we have D+ = ABCD.
So we have (Z R3)+ R3 = ABCD CD = CD.
Update Z := Z ((Z R3)+ R3) = D CD = CD.
Since changes in Z occur, we will enter the for-loop again with Z = CD.
When i = 1, consider R1 = AB,
Z R1 = CD AB = empty set.
When i = 2, consider R2 = BC,
Z R2 = CD BC = C. Compute C+ in F, we get C+ = ABCD, and
(Z R2)+ R2 = ABCD BC = BC,
so Z is updated to Z := CD BC = BCD.
When i = 3, consider R3 = CD,
Z R3 = BCD CD = CD. Compute (CD)+ in F, we have (CD)+ = ABCD.
So we have (Z R3)+ R3 = ABCD CD = CD.
Since changes in Z occur, we will enter the for-loop again with Z = BCD.
When i = 1, consider R1 = AB,
Z R1 = BCD AB = B. Compute B+ in F, we get B+ = ABCD, and
(Z R1)+ R1 = ABCD AB = AB,
so Z is updated to Z := BCD AB = ABCD.
Now, A is in Z = ABCD, so we conclude that D A can be derived from G = F1 F2 F3.