Dependency Preserving Decomposition with Example

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 ∪ 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```
 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.```

Incoming search terms:

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