# Lossless Decomposition in DBMS

**DBMS | Lossless Decomposition**: Here, we are going to learn about the **Lossless Decomposition**, **rule for Lossless Decomposition**, its properties.

Submitted by Anushree Goswami, on June 29, 2019

**Lossless decomposition occurs when the natural join of the decomposition of relation R gives exactly the same result as R**. Let us consider the decomposition of relation **R** as **A**, **B**, and **C**.

Here, **if R'= R, it is Lossless Decomposition**.

## Rule for Lossless Decomposition

- There must be functional dependency relationship in between the attributes of the relation, i.e., if
**A**,**B**, and**C**are the attributes of the relation**R**and we decompose the relation into**R (A, B) and R (A, C)**, then**A → B**(**B**attribute depends on A attribute) and**A → C**(**C**attribute depend on**A**attribute). This means that the relationship is having**lossless decomposition**. - Only if the above condition holds, then after the natural join of
**decomposed relations of R**,**R (A, B) and R(A, C)**, the new relation obtained,**R'**will be equal to**R**. This shows that the relationship is having**lossless decomposition**.

### Properties of Lossless Decomposition

Let us consider relation as **R** and set of Functional Dependency on **R** as **F**.**A, B**: Attributes of **R**.

The, decomposition is lossless if,

**A ∩ B → A**, which means all the attributes that are common on both**A & B**functionally determines all the attributes in**A**.**A ∩ B → B**, which means all the attributes that are common on both**A & B**functionally determine all the attributes in**B**.**A ∩ B**forms on the super key of either**A**or**B**, then also the decomposition of**R**is lossless.

**For e.g. – Table R:**

Decomposition of Relation into R (A, B) and R (A, C), we get -

**R (A, B) -**

**R (A, C) -**

Now, Doing Natural Join of R (A, B) and R (A, C), we get -

**= R'**

Here, **R' = R**, this shows that **relation R is Lossless Decomposition**.

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.