In this post, we will learn about dbms decomposition types and properties. We will go through different types – LossLess decomposition and dependency preserving, of decomposition in dbms with example.

## What is Decomposition ?

Decomposition is the process of breaking down bigger relation into smaller relations. So,

- It breaks a bigger table into smaller tables in database.
- Also, there should not be any loss of information while breaking into smaller parts. i.e. We should be able to construct bigger table using smaller ones, when needed.
- If we can not construct bigger table from smaller ones, then there is loss of information.
- It is needed when relation is not in appropriate normal format.
- It is used to eliminate problems like anomalies, inconsistencies and redundancy.

## Decomposition Types And Properties –

Below are the types of decomposition –

- Loss Less Decomposition
- Dependency Preserving

At first we see First decomposition types and properties – i.e. Loss Less Decomposition. We will go through different examples, related algorithms etc. for loss less decomposition.

### 1. Loss Less Decomposition

- If the information is not lost after decomposition, then decomposition is loss less decomposition.
- If you perform natural JOIN operation on decomposed relations, resultant relation will be original relation which was decomposed.

For example,

Consider **EMPLOYEE_DEPARTMENT** table,

EMP_ID | EMP_NAME | EMP_AGE | EMP_CITY | DEPT_ID | DEPT_NAME |

22 | Rahul | 29 | Delhi | 120 | Sales |

33 | Shyam | 35 | Mumbai | 138 | Marketing |

46 | Aryan | 35 | Bangalore | 169 | Finance |

52 | Katherine | 26 | Noida | 175 | Production |

60 | Ali | 45 | Patna | 178 | Sales |

Now, we will decompose this into two relations – **EMPLOYEE** and **DEPARTMENT**.

**EMPLOYEE** relation –

EMP_ID | EMP_NAME | EMP_AGE | EMP_CITY |

22 | Rahul | 29 | Delhi |

33 | Shyam | 35 | Mumbai |

46 | Aryan | 35 | Bangalore |

52 | Katherine | 26 | Noida |

60 | Ali | 45 | Patna |

**DEPARTMENT** table –

DEPT_ID | EMP_ID | DEPT_NAME |

120 | 22 | Sales |

138 | 33 | Marketing |

169 | 46 | Finance |

175 | 52 | Production |

178 | 60 | Sales |

Now, if you perform natural JOIN operation on EMPLOYEE and DEPARTMENT, resultant will be –

EMP_ID | EMP_NAME | EMP_AGE | EMP_CITY | DEPT_ID | DEPT_NAME |

22 | Rahul | 29 | Delhi | 120 | Sales |

33 | Shyam | 35 | Mumbai | 138 | Marketing |

46 | Aryan | 35 | Bangalore | 169 | Finance |

52 | Katherine | 26 | Noida | 175 | Production |

60 | Ali | 45 | Patna | 178 | Sales |

Which is same as **EMPLOYEE_DEPARTMENT**. So, it’s Loss Less Join Decomposition.

Continuing our topic on decomposition types and properties, now we will see algorithm for loss less Join decomposition.

### Algorithms for Loss Less Join Decomposition

Let R be a relation schema and let F be a set of functional dependencies on R. Let R_{1} and R_{2} form a decomposition of R. This decomposition is a loss-less join decomposition of R if at least one of the following functional dependencies is in F+.

R_{1} ∩ R_{2} -> R_{1}

R_{1} ∩ R_{2} -> R_{2}

**Example 1**

Let R(A, B, C) and F = {A -> B}, then the decomposition of R into R_{1} (A, B) and R_{2} (A, C) is loss less join decomposition, because

A -> B is the FD in F

By augmentation rule, it gives.

A -> AB

which is equal to R_{1} ∩ R_{2} -> R_{1}

**Example 2**

Let R(A, B, C) and F (A -> B). The decomposition of R into R_{1} (A, B) and R_{2} (B, C) is not loss less join decomposition because F+ does not contain.

R_{1} ∩ R_{2} -> R_{1} or

R_{1} ∩ R_{2} -> R_{2}

**Example 3
**

Let R = (A, B, C, D, E) and

F = {A -> BC, CD -> E, B -> D, E -> A}

Then the decomposition of R into

R_{1} = (A, B, C) and

R_{2} = (A, D, E) is loss join decomposition because F+ contains A -> ABC (obtained by augmentation of A -> BC) which is equivalent R_{1} ∩ R_{2} -> R_{1.}

The above algorithm is best suited, when the number of decomposition for a relation schema R is 2 i.e. the universal relation R is decomposed into two smaller relations.

But if the number of decompositions is more than 2 then the following algorithm can be used.

- Create a matrix S with one row i for each relation R1 in the decomposition D and one column j for each attribute Aj in R.
- Set S (i, j) = bij for all matrix entries (each bij is a distinct symbol associated with indices (i, j)).
- For each row i representing relation schema Ri for each column j representing attribute Aj. If Ri includes attribute Aj then set S (i, j) = aj; (each aj is a distinct symbol associated with index(j)).
- Repeat the following until a loop execution results in no changes to S
- For each functional dependency X -> Y in F.
- For all rows in S, which have the same symbols in the columns corresponding to attributes in X
- Make symbols in each column that correspond to an attribute in Y be the same in all these rows as follows:

If any of the rows has an “a” symbol for the column, set the others rows to that same “a” symbol in the column. If no “a” symbol exists for the attribute in any of the rows choose one of the “b” symbol that appears in one of the rows for the attribute and set the other rows to that “b” symbol in the column.

- If a row is made up entirely of “a” symbols, then the decomposition has the loss less join property otherwise it does not.

**Examples **

- Consider the following relation schema,
R = (SSN, Ename, Pnumber, Plocation, Hours)

D = (R_{1}, R_{2})Where,

R_{1}= Emp-locs (ename, Plocation)

R_{2}= Emp-Proj (SSN, Pnumber, Hours, Pname, Plocation)F = (SSN -> Ename; Pnumber -> (Pname, Plocation), (SSN, Pnumber) -> Hours);

To check whether the given decomposition D = (R

_{1}, R_{2}) is a loss less join decomposition. We use the first algorithm- (R
_{1}∩ R_{2}) -> (R_{1}– R_{2}) - (R
_{1}∩ R_{2}) -> (R_{2}– R_{1})

Hence, since both aren’t satisfied, the decomposition D doesn’t possess Loss less join property.

- (R
- Consider the universal relation,
R = {A, B, C, D, E, F, G, H, I, J} and the set of functional dependencies

F = {(A, B) -> C, A -> D, E, B -> F, F -> (G, H), D -> I, J}And the decomposition,

D = {R_{1}, R_{2}, R_{3}};

R_{1}= {A, B, C, D, E},

R_{2}= {B, F, G, H},

R_{3}= {D, I, J}To check whether D has a loss less join property, we use the 2nd algorithm since the decomposition has 3 relations R

_{1}, R_{2}, R_{3. }

Thus, we saw what is lossless decomposition in dbms. Now, we see next decomposition types and properties – i.e. Dependency Preserving.

### 2. Dependency Preserving

- In dependency preserving, at-least one decomposed table must satisfy every dependency.
- If a relation R is decomposed into R
_{1}and R_{2}, then, Either R_{1}or R_{2}must satisfy all dependency. or, combination of functional dependencies of R_{1}and R_{2}must derive dependencies of R_{1}. - For example, Let’s assume there is a relation R (A, B, C, D) with functional dependency set (A->BC). The relation R is decomposed into R
_{1}(ABC) and R_{2}(AD). This is dependency preserving because FD A->BC is a part of relation R_{1}(ABC)

In other words,

Given a relation schema R and set of functional dependencies associated with it F. Also, R is decomposed into several other relation schemas R_{1}, R_{2}, R_{3}, R_{4}, R_{5},…… R_{n} with functional dependencies F_{1}, F_{2}, F_{3}, F_{4}, F_{5},…. F_{n}

Then, decomposition is dependency preserving if the closure of F’ (where F’ = F_{1} U F_{2} U …..F_{n} ) is identical to F^{+} i.e.

F’^{+} = F^{+} .

**Example 1**

Let R (A, B, C, D) and F = {A -> B, A -> C, C -> D}

R is decomposed into

R_{1} = (A, B, C) with the FD’s

F_{1} = {A -> B, A -> C}

R_{2} = (C, D) with the FD’s

F_{2} = {C -> D}

F’ = F_{1} U F_{2} = {A -> B, A -> C, C -> D}

Hence, F’^{+} = F^{+}

Hence, the decomposition is dependency preserving and also loss less.

**Example 2**

R (A, B, C, D) and F = {A -> B, A -> C, C -> D} is decomposed into

R_{1} = {A, B, D} with FDs

F_{1} = {A -> B, A -> D} and

R_{2} = {B, C} with functional dependencies

F_{2} = { }

This is not a dependency preserving and also not loss less join decomposition.

Thus, we went through tutorial on DBMS decomposition types and properties with example.

You must be logged in to post a comment.