DBMS Notes

Dependency Preserving Decomposition

As we know table decomposition should be either lossless or dependency preserving to avoid the loss of data. So According to dependency preserving,

The decomposition of relation R with FD’s (F), into relation R1 and R2 with their FD’s (F1) and (F2) respectively will be dependency preserving if.

Closure of F (F+) = Closure of F1 (F1+) U Closure of F2 (F2+)

Above equation can explain as

“If a relation R is decompose into relation R1 and R2, then the dependencies of R either must be a part of R1 or R2 or must be derivable from the dependencies of R1 and R2.”

Note: After Union of R1 and R2 attributes, the Resultant must be equal to attributes of original relation R.

Some more Explanation is here,

Hidden Dependencies

 Some dependencies are directly given but some dependencies are derived from other dependencies. So these derivable dependencies are known as hidden dependencies. Let explain with example

  • Suppose a relation R(A,B,C,D)
  • Give FD’s = A→B, B→C
  • From given dependencies, we can drive FD=A→C.
  • So, dependency (A→C) is a hidden dependency.

Dependency Preserving Example

Let explain the dependency preserving with example

Suppose a relation R with A, B, C and D and its FD’s are A→B, B→C. This Relation R is decompose into tables R1 with A, B attributes, R2 with B, C attributes and R3 with B, D attributes.

Solution

1. First of all Find the closure of each attribute which given in left hand side of given FD’s of Relation R(ABCD). As given in following diagram.

2. Second, Find all Non-Trivial FD’s of Decomposed Relations (R1, R2 and R3) as given under.  

3. Third, find all those Non-trivial FD’s which are not determine from given Relation R(ABCD). Let’s check one by one all Non-Trivial FD’s of all decomposed relations R1, R2 and R3.

i. Check (A→B):

As A→B of Relation R1(AB), is directly given in the FD’s of Relation R(ABCD). So, this Dependency can determine from original table R(ABCD). Because Closure of A in Original Table can determining “B”. So, this is valid Dependency.

ii. Check (B→A):

As B→A of Relation R1 (AB), is not directly given in the FD’s of Relation R(ABCD). This Dependency cannot determined from FD’s of original table R(ABCD). Because Closure of B in Original Table cannot determining “A”. So this is valid a Dependency.

iii. Check (B→C):

As B→C of Relation R2(BC), is directly given in the FD’s of Relation R(ABCD). So this Dependency can determined from original table R(ABCD). Because Closure of B in Original Table can determining “C”. So, this is valid Dependency.

iv. Fourth Check (C→B):

As C→B of Relation R2(BC), is not directly given in the FD’s of Relation R(ABCD). But this Dependency can determined from original table R(ABCD) Because Closure of C in Original Table can determining “B”. So, this is valid Dependency.

v. Fifth Check (B→D):

As B→D of Relation R3(BD), is not directly given in the FD’s of Relation R(ABCD). But this Dependency can determined from original table R(ABCD) Because Closure of B in Original Table can determining “D”. So, this Dependency is valid.

vi. Sixth Check (D→B):

As D→B of Relation R3(BD), is directly given in the FD’s of Relation R(ABCD). So, this Dependency can determine from original table R(ABCD) Because Closure of D in Original Table can determining “B”. Thus, this is also a valid Dependency.

So, above all Non-trivial FD’s are valid except 2nd FD (B→A), As in the following diagram

4. Find the closure of all valid Non-trivial FD’s of Decomposed Relations (R1, R2 and R3) as given below

5. If all dependencies of given relation are preserve through all valid non-trivial dependencies of its decomposed tables. Then the original table will also preserve. 

Explanation of Above diagram

We will check all valid Non-trivial FD’s of decomposed tables (one by one) and see whether these FD’s can preserve all FD’s of original Relation. If it preserves, then the decomposition is dependency preserving otherwise not. 

As all Four FD’s of original Relation are preserve through valid Non-trivial FD’s No, 1,3,4 and 5. So, it is a dependency preserving decomposition

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest