LOSSY AND LOSSLESS DECOMPOSITION
Decomposition of Tables is very common whenever we Normalize the Table. Decomposition of Table is dividing table into one or more tables. So whenever we divide the table it should always be lossless . After decomposition of Table we also need to Join it under certain circumstances.
Let us consider a Dummy Table:
R(A,B,C)
|
A |
B |
C |
|
1 |
2 |
1 |
|
2 |
2 |
2 |
|
3 |
3 |
2 |
Decomposing R in R1 and R2.
Rule for Decomposition: There should be a common attribute in both decomposed tables so that if we need to join the tables in future , we will have a common attribute.
R1(AB)
|
A |
B |
|
1 |
2 |
|
2 |
2 |
|
3 |
3 |
R2(BC)
|
B |
C |
|
2 |
1 |
|
2 |
2 |
|
3 |
2 |
Query: Find the value of C if the value of A=1.
For this query we need to join the table.
SQL Query: SELECT R2.C from R2 NATURAL JOIN R1 where R1.A=1
R1 NATURAL JOIN R2
Perform the Cartesian product.
|
A |
B |
B |
C |
|
1 |
2 |
2 |
1 |
|
1 |
2 |
2 |
2 |
|
1 |
2 |
3 |
2 |
|
2 |
2 |
2 |
1 |
|
2 |
2 |
2 |
2 |
|
2 |
2 |
3 |
2 |
|
3 |
3 |
2 |
1 |
|
3 |
3 |
2 |
2 |
|
3 |
3 |
3 |
2 |
Finds consistent tuples and deletes inconsistent tuples i.e. we only select the tuple having same value of B
|
A |
B |
B |
C |
|
1 |
2 |
2 |
1 |
|
1 |
2 |
2 |
2 |
|
2 |
2 |
2 |
1 |
|
2 |
2 |
2 |
2 |
|
3 |
3 |
3 |
2 |
Deletes the duplicate attributes
R’
|
A |
B |
C |
|
1 |
2 |
1 |
|
1 |
2 |
2 |
|
2 |
2 |
1 |
|
2 |
2 |
2 |
|
3 |
3 |
2 |
Here R’ table after decomposition contains five tuples whereas the original table had only three tuples, hence it is lossy decomposition as it contains duplicate values. Suppose if we execute the above question here , for A=1 , we will have two values of C .
Lossless Decomposition:
Rule for Lossless Decomposition
Common attribute of a decomposed table must be a candidate of Super Key .
So in the above case the common attribute will be A rather than B or C.
Lets decompose the table again
R1(AB)
R2(AC)
Rules:
AB union AC=ABC