Dependency Preserving Decomposition with Example
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 R_{1} and R_{2} having FD set F_{1} and F_{2} respectively, are the decomposed subrelations of R. The decomposition of R is said to be preserving if
F_{1} ∪ F_{2} ≡ F {Decomposition Preserving Dependency}
If F_{1} ∪ F_{2} ⊂ F {Decomposition NOT Preserving Dependency}
and F_{1 }∪ F_{2 }⊃ 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 {R_{1}, R_{2}, …, R_{n}}
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 ∩ R_{i})^{+} ∩ R_{i}) 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
ABCD (R1) 
BF (R2) 
DE (R3) 
A → BCD
BC → AD 
B → F 
D → E 

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 ∩ R_{1}) = BC ∩ ABCD = BC // Intersection
(Z ∩ R_{1})^{+} = (BC)^{+} = BCADEF // Closure
{(Z ∩ R_{1})^{+} ∩ R_{1}} = BCADEF ∩ ABCD = ABCD // Intersection
Z= [{(Z ∩ R_{1})^{+} ∩ R_{1}}∪Z] = ABCD ∪ BC = ABCD // Updating Z (Union)
Z does not contain E(RHS of FD BC → E), Repeating procedure with R_{2}
Now, z = ABCD
(Z ∩ R_{2}) = ABCD ∩ BF = B // Intersection
(Z ∩ R_{2})^{+} = B^{+} = BF // Closure
{(Z ∩ R_{2})^{+} ∩ R_{2}} = BF ∩ BF = BF // Intersection
Z= [{(Z ∩ R_{2})^{+} ∩ R_{2}}∪Z] = ABCD ∪ BF = ABCDF // Updating Z (Union)
Z does not contain E(RHS of FD BC → E), Repeating procedure with R_{3}
Now Z = ABCDF
(Z ∩ R_{3}) = ABCDF ∩ DE = B // Intersection
(Z ∩ R_{3})^{+} = D^{+} = DE // Closure
{(Z ∩ R_{3})^{+} ∩ R_{3}} = DE ∩ DE = BF // Intersection
Z= [{(Z ∩ R_{3})^{+} ∩ R_{3}}∪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 ∩ R_{1}) = A ∩ ABCD = A // Intersection
(Z ∩ R_{1})^{+} = A^{+} = ABCDEF // Closure
{(Z ∩ R_{1})^{+} ∩ R_{1}} = ABCDEF ∩ ABCD = ABCD // Intersection
Z= [{(Z ∩ R_{1})^{+} ∩ R_{1}}∪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 ∩ R_{2}) = ABCD ∩ BF = B // Intersection
(Z ∩ R_{2})^{+} = B^{+} = BF // Closure
{(Z ∩ R_{2})^{+} ∩ R_{2}} = BF ∩ BF = BF // Intersection
Z= [{(Z ∩ R_{2})^{+} ∩ R_{2}}∪Z] = ABCD ∪ BF = ABCDF // Updating Z (Union)
A→F preserves dependency. Checking for A→E, Repeating procedure with R3
Now Z = ABCDF
(Z ∩ R_{3}) = ABCDF ∩ DE = B // Intersection
(Z ∩ R_{3})^{+} = D^{+} = DE // Closure
{(Z ∩ R_{3})^{+} ∩ R_{3}} = DE ∩ DE = BF // Intersection
Z= [{(Z ∩ R_{3})^{+} ∩ R_{3}}∪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
ABCD (R1) 
BF (R2) 
DE (R3) 
A → B
A → C
A → D
BC → A
BC → D 
B → F 
D → E 

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.
Incoming search terms:
 decomposition in dbms with example
 dependency preserving decomposition
 Dependency preservation
 dependency preservation in dbms
 dependency preservation in dbms tutorial
 dependency preserving decomposition in dbms
 dependency preserving decomposition in dbms example
 dependency preserving decomposition example
 dependency preservation example
 dependency preserving
Related
Pingback: http://www.citymonte.it/en/oakleysunglassesp01.asp