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 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 ∪ F⊃ 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
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 ∩ 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
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.

Previous Home Next
Lossless Join Decomposition Question on Dependency Preserving Decomposition

     

Incoming search terms:

  • dependency preserving decomposition
  • decomposition in dbms with example
  • Dependency preservation
  • dependency preservation in dbms
  • dependency preserving decomposition in dbms
  • dependency preservation in dbms tutorial
  • dependency preserving decomposition example
  • dependency preservation example
  • dependency preserving decomposition in dbms example
  • what is dependency preservation

This article has 1 comment

  1. Pingback: http://www.citymonte.it/en/oakley-sunglasses-p01.asp

Leave a Reply