# 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.**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.