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,

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

EMPLOYEE relation –

DEPARTMENT table –

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

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₁ and R₂ 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₁ ∩ R₂ -> R₁
R₁ ∩ R₂ -> R₂

Example 1

Let R(A, B, C) and F = {A -> B}, then the decomposition of R into R₁ (A, B) and R₂ (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₁ ∩ R₂ -> R₁

Example 2

Let R(A, B, C) and F (A -> B). The decomposition of R into R₁ (A, B) and R₂ (B, C) is not loss less join decomposition because F+ does not contain.

R₁ ∩ R₂ -> R₁ or
R₁ ∩ R₂ -> R₂

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₁ = (A, B, C) and

R₂ = (A, D, E) is loss join decomposition because F+ contains A -> ABC (obtained by augmentation of A -> BC) which is equivalent R₁ ∩ R₂ -> 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.

1. 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.
2. Set S (i, j) = bij for all matrix entries (each bij is a distinct symbol associated with indices (i, j)).
3. 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)).
4.  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.
5. If a row is made up entirely of “a” symbols, then the decomposition has the loss less join property otherwise it does not.

Examples 

1. Consider the following relation schema,

   R = (SSN, Ename, Pnumber, Plocation, Hours)
   D = (R₁, R₂)

   Where,
   R₁ = Emp-locs (ename, Plocation)
   R₂ = Emp-Proj (SSN, Pnumber, Hours, Pname, Plocation)

   F = (SSN -> Ename; Pnumber -> (Pname, Plocation), (SSN, Pnumber) -> Hours);

   To check whether the given decomposition D = (R₁, R₂) is a loss less join decomposition. We use the first algorithm

   • (R₁ ∩ R₂) -> (R₁ – R₂)
   • (R₁ ∩ R₂) -> (R₂ – R₁)

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

2. 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₁, R₂, R₃};
   R₁ = {A, B, C, D, E},
   R₂ = {B, F, G, H},
   R₃ = {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₁, R₂, 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₁ and R₂, then, Either R₁ or R₂ must satisfy all dependency. or, combination of functional dependencies of R₁ and R₂ must derive dependencies of R₁.
• 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₁(ABC) and R₂(AD). This is dependency preserving because FD A->BC is a part of relation R₁(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₁, R₂, R₃, R₄, R₅,…… R_n with functional dependencies F₁, F₂, F₃, F₄, F₅,…. F_n

Then, decomposition is dependency preserving if the closure of F’ (where F’ = F₁ U F₂ 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₁ = (A, B, C) with the FD’s
F₁ = {A -> B, A -> C}
R₂ = (C, D) with the FD’s
F₂ = {C -> D}
F’ = F₁ U F₂ = {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₁ = {A, B, D} with FDs
F₁ = {A -> B, A -> D} and
R₂ = {B, C} with functional dependencies
F₂ = { }

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.