DBMS Decomposition Types And Properties With Example

Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners. Also, if you are interested in content writing, you can mail us at tutorialwing@gmail.com.

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 –

Tutorialwing Database DBMS types of decomposition types

  • 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 R1 and R2 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+.

R1 ∩ R2 -> R1
R1 ∩ R2 -> R2

Example 1

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

Example 2

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

R1 ∩ R2 -> R1 or
R1 ∩ R2 -> R2

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

R1 = (A, B, C) and

R2 = (A, D, E) is loss join decomposition because F+ contains A -> ABC (obtained by augmentation of A -> BC) which is equivalent R1 ∩ R2 -> R1.

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 = (R1, R2)

    Where,
    R1 = Emp-locs (ename, Plocation)
    R2 = Emp-Proj (SSN, Pnumber, Hours, Pname, Plocation)

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

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

    • (R1 ∩ R2) -> (R1 – R2)
    • (R1 ∩ R2) -> (R2 – R1)

    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 = {R1, R2, R3};
    R1 = {A, B, C, D, E},
    R2 = {B, F, G, H},
    R3 = {D, I, J}

    To check whether D has a loss less join property, we use the 2nd algorithm since the decomposition has 3 relations R1, R2, R3.

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 R1 and R2, then, Either R1 or R2 must satisfy all dependency. or, combination of functional dependencies of R1 and R2 must derive dependencies of R1.
  • 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 R1(ABC) and R2(AD). This is dependency preserving because FD A->BC is a part of relation R1(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 R1, R2, R3, R4, R5,…… Rn with functional dependencies F1, F2, F3, F4, F5,…. Fn

Then, decomposition is dependency preserving if the closure of F’ (where F’ = F1 U F2 U …..Fn ) 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
R1 = (A, B, C) with the FD’s
F1 = {A -> B, A -> C}
R2 = (C, D) with the FD’s
F2 = {C -> D}
F’ = F1 U F2 = {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
R1 = {A, B, D} with FDs
F1 = {A -> B, A -> D} and
R2 = {B, C} with functional dependencies
F2 = { }

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.

Support Us

If you like Tutorialwing and would like to contribute, you can email an article on any educational topic at tutorialwing@gmail.com. We would love to publish your article. See your article on Tutorialwing and help others with your knowledge. Follow Facebook, LinkedIn, Google+, Twitter, Youtube for latest updates.
Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners