Decomposition in Relational Database

Decomposition :

In RDBMS Decomposition is the process of breaking down the functions of an organization into progressively greater levels of details. It replaces a relation with a collection of smaller relations by breaking the table into multiple tables in a database. It should always be lossless, because it confirms that the information in the original relation can be accurately reconstructed based on the decomposed relations. If there is no proper decomposition of the relation, then it may lead to problems like loss of information. The decomposition of a relation scheme R consists of replacing the relation schema by two or more relation schema that each contain a subset of the attributes of R and together include all attributes in R. Decomposition helps in eliminating some of the problems of bad design such as redundancy, inconsistencies and anomalies.

Types of Decomposition :

There are three types of Decomposition :

1. Lossless Decomposition
2. Lossy Join Decomposition
3. Dependency-Preserving Decomposition

1. Lossless Decomposition :

The Decomposition of Relation R into R1 and R2 is Lossless when the join of R1 and R2 does yield the same relation as in R. In Lossless Decomposition the Decomposition must be Lossless. It means that the information should not get lost from the relation that is decomposed. It gives a guarantee that the join will result in the same relation as it was decomposed. A relational table is decomposed (or factored) into two or more smaller tables, in such a way that the designer can capture the precise content of the original table by joining the decomposed parts. This is called lossless-join decomposition. It is also known as non-additive Decomposition. Let R be a relation schema. If we decompose R into relation R1 and R2, then Decomposition is lossless if

          R1 ⋈ R2 = R

For example consider the following table student_details with five attributes : stud_id, stud_name, Address, course and stud_grade_on_course.

The above relation is decomposed into two relations namely students, student_course_details


students schema contains (stud_id, stud_name, Address).


student_course_details schema contains (stud_id, course, stud_grade_on_course). So, the above decomposition is a Lossless Join Decomposition, because the two relations contains one common field that is 'stud_id' and therefore join is possible. Now we applying the natural join on the decomposed relations.

                          students ⋈ student_course_details 


Now at the above when we applied  a natural join in both relations (students and student_course_details), then no any spurious tuples are generated. Hence, the decomposition is Lossless Join Decomposition.


2. Lossy Decomposition

The Decomposition of Relation R into R1 and R2 is lossy when the join of R1 and R2 does not yield the same relation as in R. One of the disadvantages of decomposition into two or more relational schemes (or tables) is that some information is lost during retrieval of original relation or table. Let R be a relation schema. If we decompose R into relation R1 and R2, then Decomposition is Lossy if     

       R1 ⋈ R2 ≠ R.

For example consider the following table student_details with five attributes : stud_id, stud_name, Address, course and department.


The above relation is decomposed into two relations namely students, courses


 students schema contains (stud_id, stud_name, Address, course).


 courses schema contains (course, department). Now we applying the natural join on the decomposed relations.

                          students ⋈ courses


Now at the above when we applied  a natural join in both relations (students and courses), spurious tuples are generated. Hence, above decomposition is a Lossy decomposition.


3. Dependency-Preserving Decomposition :

The Dependency Preservation Decomposition is another type of decomposed relational database. Dependency Preservation Decomposition, If we decompose a relation R into relations R1 and R2, then all dependencies of R is either must be a part of R1 or R2 or must be derivable from combination of FD’s (Functional Dependency) of R1 and R2.

For example let a relation R(A,B,C,D) and set a FD  F = { A -> B ,  A -> C  , C -> D}  are given.

 Then a relation R is decomposed into -

        R1 = (A, B, C) with FDs F1 = {A -> B, A -> C}, and

                R2 = (C, D) with FDs F2 = {C -> D}

 now if, F' = F1 ∪ F2 = {A -> B, A -> C, C -> D}

 then so, F' = F.

 and so, F'+ = F+ 

where F+ stands for the closure for every attribute or attribute sets in F. Thus, the decomposition is dependency preserving decomposition.



No comments:

Post a Comment