Dependency Preserving Decomposition The second property of decomposition is Dependency Preserving Decomposition. If the original table is decomposed into multiple fragments, then somehow, we suppose to get all original FDs from these fragments. In other words, every dependency in original table must be preserved or say, every dependency must be satisfied by at least one decomposed table. Let R be the original relational schema having FD set F. Let R1 and R2 having FD set F1 and F2 respectively, are the decomposed sub-relations of R. The decomposition of R is said to be preserving if
F1 ∪ F2 ≡ F {Decomposition Preserving Dependency}
If F1 ∪ F2 ⊂ F {Decomposition NOT Preserving Dependency}
and F1 ∪ F2 ⊃ F {this is not possible}
How to find whether a decomposition is preserving dependency or not ?
Method 1 : (Not useful for gate students)
The Method 1 is an algorithm to find the preserving dependency.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;
R(ABCDEF) has following FD’s
F = {A→BCD, A→EF, BC→AD, BC→E, BC→F, B→F, D→E}
D = {ABCD, BF, DE}
check whether decomposition is dependency preserving or not
Solution : The following dependencies can be projected into the following decomposition
|
The FDs in the table are preserved also as they are projected in their corresponding decomposition. Check whether BC → E and A → EF preserved in the decomposition or not Apply the algorithm above : For BC → E : Let Z = BC (Z ∩ R1) = BC ∩ ABCD = BC // Intersection (Z ∩ R1)+ = (BC)+ = BCADEF // Closure {(Z ∩ R1)+ ∩ R1} = BCADEF ∩ ABCD = ABCD // Intersection Z= [{(Z ∩ R1)+ ∩ R1}∪Z] = ABCD ∪ BC = ABCD // Updating Z (Union) Z does not contain E(RHS of FD- BC → E), Repeating procedure with R2 Now, z = ABCD (Z ∩ R2) = ABCD ∩ BF = B // Intersection (Z ∩ R2)+ = B+ = BF // Closure {(Z ∩ R2)+ ∩ R2} = BF ∩ BF = BF // Intersection Z= [{(Z ∩ R2)+ ∩ R2}∪Z] = ABCD ∪ BF = ABCDF // Updating Z (Union) Z does not contain E(RHS of FD- BC → E), Repeating procedure with R3 Now Z = ABCDF (Z ∩ R3) = ABCDF ∩ DE = B // Intersection (Z ∩ R3)+ = D+ = DE // Closure {(Z ∩ R3)+ ∩ R3} = DE ∩ DE = BF // Intersection Z= [{(Z ∩ R3)+ ∩ R3}∪Z] = DE ∪ ABCDF = ABCDEF // Updating Z (Union) Stopping the algorithm as Z contains E, So BC→E preserves dependency For A → EF : Let Z = A (Z ∩ R1) = A ∩ ABCD = A // Intersection (Z ∩ R1)+ = A+ = ABCDEF // Closure {(Z ∩ R1)+ ∩ R1} = ABCDEF ∩ ABCD = ABCD // Intersection Z= [{(Z ∩ R1)+ ∩ R1}∪Z] = ABCD ∪ A = ABCD // Updating Z (Union) Z does not contain E and F(RHS of FD- A→EF), Repeating procedure with R2 Now, z = ABCD (Z ∩ R2) = ABCD ∩ BF = B // Intersection (Z ∩ R2)+ = B+ = BF // Closure {(Z ∩ R2)+ ∩ R2} = BF ∩ BF = BF // Intersection Z= [{(Z ∩ R2)+ ∩ R2}∪Z] = ABCD ∪ BF = ABCDF // Updating Z (Union) A→F preserves dependency. Checking for A→E, Repeating procedure with R3 Now Z = ABCDF (Z ∩ R3) = ABCDF ∩ DE = B // Intersection (Z ∩ R3)+ = D+ = DE // Closure {(Z ∩ R3)+ ∩ R3} = DE ∩ DE = BF // Intersection Z= [{(Z ∩ R3)+ ∩ R3}∪Z] = DE ∪ ABCDF = ABCDEF // Updating Z (Union) Stopping the algorithm as Z contains F, So A→F also preserves dependency
Method 2 : (Useful for gate students)
R(ABCDEF) has following FD’s
F = {A→BCD, A→EF, BC→AD, BC→E, BC→F, B→F, D→E}
D = {ABCD, BF, DE}
check whether decomposition is dependency preserving or not
Solution : The following dependencies can be projected into the following decomposition
|
Try to infer the reverse FDs which are present in the table by taking closure w.r.t F.
Look at the RHS of FDs and take closure (B,C,D,A,F,E)
Infer Reverse FDs -
B+ w.r.t F = {BF} //doesn't contain A. So, B → A cannot be inferred
C+ w.r.t F = {C} //doesn't contain A. So, C → A cannot be inferred
D+ w.r.t F = {DF} //doesn't contain A and BC. So, D → A and D → BC
cannot be inferred
A+ w.r.t F = {ABCDEF} // A → BC can be inferred, but it is equal to
A → B and A → C
F+ w.r.t F = {F} //doesn't contain B. So, F → B cannot be inferred
E+ w.r.t F = {E} //doesn't contain D. So, E → D cannot be inferred
No reverse FDs can be inferred from the closure.
Checking BC → E preserves dependency or not -
Compute (BC)+ w.r.t Table FDs
(BC)+ = {BCDAFEE}
as closure of BC w.r.t table FDs contains EF. So BC→EF preserves dependency.
Checking A → EF preserves dependency or not -
Compute A+ w.r.t Table FDs
(A)+ = {ABCDFE}
as closure of A w.r.t table FDs contains EF, So, A → EF preserves dependency.
| Previous | Home | Next |
| Lossless Join Decomposition | Question on Dependency Preserving Decomposition |
]]>