Decomposition is a process of dividing a relation into multiple relations to remove redundancy while maintaining the original data. In this guide, you will learn decomposition in DBMS with the help of examples.
Types of decomposition:
1. Lossless decomposition
2. Lossy decomposition
1. Lossless decomposition
A lossless decomposition of a relation ensures that:
a) No information is lost during decomposition. This is why the term lossless is used in this decomposition as no information is lost.
b) If a relation R is divided into two relations R1 and R2 using lossless decomposition then the natural join of R1 and R2 would return the original relation R.
Rules of Lossless decomposition: For these rules, we are assuming that a relation R is divided into two relations R1 and R2.
1. Natural join of R1 and R2 should return the original relation R.
R1 U R2 = R
2. The intersection of R1 and R2 should not be null. This is because there are some common attributes present in relation R1 and R2.
R1 ∩ R2 ≠ 0
3. The intersection of R1 and R2 is either a super key of R1 or R2, or both the relations R1 and R2.
R1 ∩ R2 = super key of R1 or R2 or both
Let’s say a relation R (A, B, C), where A is primary key is divided into two relations R1 (A, B) and R2 (C, A).
Let’s check whether this decomposition is loss-less decomposition or not:
Rule 1:
R1 U R2 = (A, B) U (C, A) = (A, B, C)
Union or R1 and R2 gives the original relations, thus first rule of lossless decomposition applies here.
Rule 2:
R1 ∩ R2 = (A, B) ∩ (C, A) = (A)
Result is not null so the second rule also applies here.
Rule 3:
R1 ∩ R2 = (A, B) ∩ (C, A) = (A)
Result is a super key of both the relations thus third rule also applies here.
Rule 4: Dependency preserving
The dependencies that exists in the original relation, exists after decomposition.
Example of LossLess decomposition
StudentCourse Table:
Student_Id Student_Name Course_Id Course_Detail ---------- ------------- --------- ------------- S101 Chaitanya C01 Maths S102 Ajeet C01 Maths S103 Rahul C02 Science S104 Steve C02 Science S105 John C03 English S101 Chaitanya C03 English S102 Ajeet C02 Science
The primary key of given relation is {Student_Id, Course_Id}
This table has redundant data as the Course_Id and Course_Detail are common for several students. Let’s decompose this relation into two relations.
Student Table:
The primary key of this table is {Student_Id, Course_Id}
Student_Id Student_Name Course_Id ---------- ------------ --------- S101 Chaitanya C01 S102 Ajeet C01 S103 Rahul C02 S104 Steve C02 S105 John C03 S101 Chaitanya C03 S102 Ajeet C02
Course Table:
The primary key of this table is {Course_Id}
Course_Id Course_Detail --------- ------------- C01 Maths C02 Science C03 English
Let’s check all the three rules of lossless decomposition to check whether this decomposition is lossless or not.
Rule 1:
{Student} U {Course}
Union Result:
Student_Id Student_Name Course_Id Course_Detail ---------- ------------- --------- ------------- S101 Chaitanya C01 Maths S102 Ajeet C01 Maths S103 Rahul C02 Science S104 Steve C02 Science S105 John C03 English S101 Chaitanya C03 English S102 Ajeet C02 Science
The union results in the original relation StudentCourse so we can say that the first rule holds true.
Rule 2 & 3:
R1 ∩ R2
Result:
Course_Id C01 C02 C03
The result is not null so rule 2 holds true.
The result is a super key of the second relation R2 so the third rule also applies here.
Rule 4: Dependencies in original relation:
Student_Id -> {Student_Name}
Course_Id -> {Course_Detail}
These dependencies are still present in the decomposed relations. Thus we can say that this decomposition is dependency preserving.
Since all the three rules applies here, the decomposition of relation StudentCourse into Student and Course is a lossless decomposition.
2. Lossy Decomposition
As the name suggests, in lossy decomposition, the information is lost during decomposition. The three rules that we discussed above would not apply in lossy decomposition. In lossy decomposition, one or more rules will fail.
Let’s take the same example that we discussed above.
StudentCourse Table:
Student_Id Student_Name Course_Id Course_Detail S101 Chaitanya C01 Maths S102 Ajeet C01 Maths S103 Rahul C02 Science S104 Steve C02 Science S105 John C03 English S101 Chaitanya C03 English S102 Ajeet C02 Science
Now if we divide this relation like this:
Student Table:
The primary key of this table is {Student_Id}
Student_Id Student_Name S101 Chaitanya S102 Ajeet S103 Rahul S104 Steve S105 John
Course Table:
The primary key of this table is {Course_Id}
Course_Id Course_Detail C01 Maths C02 Science C03 English
This is a lossy decomposition as the intersection of Student and Course relation will return null so the second and third rule of lossless decomposition will fail here.
In this decomposition, the relation of Student and Course is lost, there is no way to form the original relation from these two relations as the information that suggests who is attending which course is lost during decomposition.