Lossless decomposition

Explain lossless and lossy decomposition with suitable example.

1. Lossless Decomposition
MANASY JAYASURYA
Dept. of Computer Science & Applications
St.Mary’s College,Thrissur

2. What is Decomposition?
•Decomposition – the process of breaking
down in parts or elements.
•Decomposition in database means breaking
tables down into multiple tables
•From Database perspective means going to a
higher normal form

3. Decomposition
Important that decompositions are “good”,
Two Characteristics of Good Decompositions
•1) Lossless
•2) Preserve dependencies

4. What is lossless?
Lossless means functioning without a loss.
In other words, retain everything.
Important for databases to have this feature.

5. Formal Definition
•Let R be a relation schema.
•Let F be a set of functional dependencies on R.
•Let and form a decomposition of R.
•The decomposition is a lossless-join
decomposition of R if at least one of the
following functional dependencies are in F
+
1) R1 R2
∩
 R1
2) R1 R2
∩
 R2

6. In Simpler Terms…
•R1 R2
∩
 R1
•R1 R2
∩
 R2
If R is split into R1 and R2, for the decomposition to
be lossless then at least one of the two should
hold true.
Projecting on R1 and R2, and joining back, results in
the relation you started with

7. Why lossless?
Ensures that attributes involved in the natural
join (R1 R2) are a candidate key for at least
∩
one of the two relations.
This ensures we can never get the situation
where false tuples are generated, as for any
value on the join attributes there will be a
unique tuple in one of the relations.

8. A decomposition is lossless if we can recover:
R(A,B,C)
R1(A,B) R2(A,C)
R’(A,B,C) should be the same as
R(A,B,C)
Must ensure R’ = R
Decompose
Recover
Lossless Decomposition

9. Lossless Decomposition
•Sometimes the same set of data is reproduced:
•(Word, 100) + (Word, WP)  (Word, 100, WP)
•(Oracle, 1000) + (Oracle, DB)  (Oracle, 1000, DB)
•(Access, 100) + (Access, DB)  (Access, 100, DB)
Name Price Category
Word 100 WP
Oracle 1000 DB
Access 100 DB
Name Price
Word 100
Oracle 1000
Access 100
Name Category
Word WP
Oracle DB
Access DB

10. Lossy Decomposition
•Sometimes it’s not:
•(Word, WP) + (100, WP) = (Word, 100, WP)
•(Oracle, DB) + (1000, DB) = (Oracle, 1000, DB)
•(Oracle, DB) + (100, DB) = (Oracle, 100, DB)
•(Access, DB) + (1000, DB) = (Access, 1000, DB)
•(Access, DB) + (100, DB) = (Access, 100, DB)
Name Price Category
Word 100 WP
Oracle 1000 DB
Access 100 DB
Category Name
WP Word
DB Oracle
DB Access
CategoryPrice
WP 100
DB 1000
DB 100
What’s
wrong?

11. Ensuring lossless decomposition
R(A
1
, ..., A
n
, B
1
, ..., B
m
, C
1
, ..., C
p
)
R(A
1
, ..., A
n
, B
1
, ..., B
m
, C
1
, ..., C
p
)
If A
1
, ..., A
n
 B
1
, ..., B
m
or A
1
, ..., A
n
 C
1
, ..., C
p
Then the decomposition is lossless
R
1
(A
1
, ..., A
n
, B
1
, ..., B
m
)
R
1
(A
1
, ..., A
n
, B
1
, ..., B
m
)
R
2
(A
1
, ..., A
n
, C
1
, ..., C
p
)
R
2
(A
1
, ..., A
n
, C
1
, ..., C
p
)
Note: don’t need both