Home » DBMS

Dependency preserving decomposition | DBMS

In this tutorial, we are going to learn about the Dependency preserving decomposition in the database management system with example and solution.
Submitted by Anushree Goswami, on August 16, 2019

A Dependency preserving decomposition of a relation R is R1, R2, R3...Rn concerning the set of Functional Dependencies FD if,

 (FD1 ∪ FD2 ∪ ... ∪ FDn)+ = FD+
 

where,

  • FD1, FD2, FD3…...FDn Sets of Functional dependencies of relations R1, R2, R3 ...Rn.
  • (FD1 U FD2 U FD3 U … U FDn)+ -> Closure of Union of all sets of functional dependencies.
  • FD+ -> Closure of set of functional dependency FD of R. 

With FD (FD1) R is decomposed or divided into R1 and with FD(FD2) into R2, then the possibility of three cases arise,

    FD1 ∪ FD2 = FD -> Decomposition is dependency preserving. 
    FD1 ∪ FD2 is a subset of FD -> Not Dependency preserving.
    FD1 ∪ FD2 is a superset of FD -> This case is not possible. 

For the lossless dependency preserving decomposition, the closure of the set of functional dependencies of discrete relations R1, R2, R3 ...Rn should be equal to the set of functional dependencies of the main relation R before decomposition.

Dependency preservation and Normalization process, both concepts works on some similarity. As in Normalization process, to change the form of a relationship into a higher normal form, the solution is by decomposing the relation into two or more relations, which is done by using the set of functional dependencies associated in the lower normal form state.

For example:

Let suppose a relation R (P, Q, R, S) with a set of functional dependency FD = (P→Q, Q→R, R→S).

In the given set FD, there is no partial dependency. As a consequence, this relation is in 2NF.

The relation R (P, Q, R, S) is not in 3NF because of Transitive Functional Dependency. To convert this relation R (P, Q, R, S) into 3NF, the solution which is preferred is decomposition.

Q) Let suppose, a relation R (P, Q, R, S) with a set of Functional Dependency FD = (PQ→R, R→S, S→P) is given. Into R1 (P, Q, R) and R2(R, S), relation R (P, Q, R, S) is decomposed. Find out whether the decomposition is dependency preserving or not.

Solution:

Decomposed relations of relation R (P, Q, R, S) are R1 (P, Q, R) and R2 (R, S). To solve this problem, we need to first find the closure of Functional Dependencies FD1 and FD2 of the relations R1 (P, Q, R) and R2(R, S).

1) To find the closure of FD1, we have to consider all combinations of (P, Q, R). i.e., we need to find out the closure of P, Q, R, PQ, QR, and RP.

    closure (P) = {P} // Trivial
    closure (Q) = {Q}  // Trivial
    closure (R) = {R, P, S} //but S can't be in closure as S is not 
                            //present in R1 (P, Q, R).
                = {R, P}
    (R--> P // Removing R from right side as it is trivial attribute)
    closure (PQ) = {P, Q, R, S}
                = {P, Q, R}
    (PQ --> R // Removing PQ from right side as these are trivial attributes)
    closure (QR) = {Q, R, S, P}
                = {P, Q, R}
    (QR --> P // Removing QR from right side as these are trivial attributes)
    Closure (PR) = {P, R, S}
    (PR --> S // Removing PR from right side as these are trivial attributes)
    FD1 {R --> P, PQ --> R, QR --> P}.

2) Similarly FD2 {R--> S}

In the original Relation Dependency FD= {PQ→R, R→S, S→P}.

    PQ --> R is present in FD1.
    R --> S is present in FD2.
    S --> P is not preserved.

From the given result, in FD1, PQ holds R (PQ --> R) and in FD2, R holds S (R --> S). But, there is no follow up in Functional Dependency S holds P (S --> P).

FD1 U FD2 is a subset of FD.

So as a consequence, given decomposition is not dependency preserving.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.