Lossless Decomposition

Decomposition is the process of breaking a relation R into two or more smaller relations R1, R2, ..., Rn such that the union of attributes in all Ri equals the attributes

What is Decomposition?

Decomposition is the process of breaking a relation R into two or more smaller relations R1, R2, ..., Rn such that the union of attributes in all Ri equals the attributes in R.

R(A, B, C, D) → R1(A, B, C) + R2(A, D)

Decomposition is used during normalization to eliminate anomalies.

Lossless Join Decomposition

A decomposition of R into R1 and R2 is lossless (lossless-join) if the original relation R can be exactly reconstructed by taking the natural join of R1 and R2:

R = R1 ⋈ R2 (no spurious tuples added, no tuples lost)

A decomposition is lossy if joining the decomposed parts produces extra (spurious) tuples not in the original relation.

Test for Lossless Decomposition (Binary)

For decomposition of R into R1 and R2, the decomposition is lossless if and only if at least one of the following holds:

Condition 1: (R1 ∩ R2) → R1 (common attributes determine R1)

Condition 2: (R1 ∩ R2) → R2 (common attributes determine R2)

i.e., the common attributes form a superkey of R1 OR R2.

Examples

Example 1 — Lossless Decomposition

1	x	p		1	x		1	p
1	x	q		2	y		1	q
2	y	p	+---+---+	2	p

1	x	p
1	x	q
2	y	p

Example 2 — Lossy Decomposition

1	x	p		1	x		x	p
2	x	q		2	x		x	q

Lossless Test — Tabular Method (Chase Algorithm)

For decomposing R into more than 2 relations, the Chase algorithm tests losslessness:

F = {A	C, B → C, C → D, DE → C, CE → A}
Decompose into	R1(AD), R2(AB), R3(BE), R4(CDE), R5(AE)
Step 1	Create a table with one row per decomposed relation.
R1(AD)	a1 b12 b13 a4 b15
R2(AB)	a1 a2 b23 b24 b25
R3(BE)	b31 a2 b33 b34 a5
R4(CDE)	b41 b42 a3 a4 a5
R5(AE)	a1 b52 b53 b54 a5
Step 2	Apply each FD repeatedly to make symbols equal.
Step 3: If any row becomes (a1, a2, a3, a4, a5)	LOSSLESS ✓
Otherwise	LOSSY ✗

Importance of Lossless Decomposition

Lossless decomposition is a mandatory requirement of any normalization process. Without it:

Joining decomposed tables generates spurious/extra tuples
Original data cannot be recovered
The decomposition is useless (data is effectively lost/corrupted)

Key Rule: ALL normalization decompositions MUST be lossless. If a decomposition is lossy, it is not a valid normalization.

Lossless vs. Dependency Preserving

These are two separate properties of a decomposition:

Property	Meaning	Mandatory?
Lossless Join	Original can be reconstructed exactly	YES — always required
Dependency Preserving	All FDs can be checked in decomposed tables	Desired, but not always achievable (BCNF may sacrifice this)

A good decomposition should ideally be both lossless AND dependency-preserving. 3NF decomposition always guarantees both. BCNF guarantees lossless but not always dependency-preserving.

What is Decomposition?

Decomposition is the process of breaking a relation R into two or more smaller relations R1, R2, ..., Rn such that the union of attributes in all Ri equals the attributes in R.

R(A, B, C, D) → R1(A, B, C) + R2(A, D)

Decomposition is used during normalization to eliminate anomalies.

Lossless Join Decomposition

A decomposition of R into R1 and R2 is lossless (lossless-join) if the original relation R can be exactly reconstructed by taking the natural join of R1 and R2:

R = R1 ⋈ R2 (no spurious tuples added, no tuples lost)

A decomposition is lossy if joining the decomposed parts produces extra (spurious) tuples not in the original relation.

Test for Lossless Decomposition (Binary)

For decomposition of R into R1 and R2, the decomposition is lossless if and only if at least one of the following holds:

Condition 1: (R1 ∩ R2) → R1 (common attributes determine R1)

Condition 2: (R1 ∩ R2) → R2 (common attributes determine R2)

i.e., the common attributes form a superkey of R1 OR R2.

Examples

Example 1 — Lossless Decomposition

1	x	p		1	x		1	p
1	x	q		2	y		1	q
2	y	p	+---+---+	2	p

1	x	p
1	x	q
2	y	p

Example 2 — Lossy Decomposition

1	x	p		1	x		x	p
2	x	q		2	x		x	q

Lossless Test — Tabular Method (Chase Algorithm)

For decomposing R into more than 2 relations, the Chase algorithm tests losslessness:

F = {A	C, B → C, C → D, DE → C, CE → A}
Decompose into	R1(AD), R2(AB), R3(BE), R4(CDE), R5(AE)
Step 1	Create a table with one row per decomposed relation.
R1(AD)	a1 b12 b13 a4 b15
R2(AB)	a1 a2 b23 b24 b25
R3(BE)	b31 a2 b33 b34 a5
R4(CDE)	b41 b42 a3 a4 a5
R5(AE)	a1 b52 b53 b54 a5
Step 2	Apply each FD repeatedly to make symbols equal.
Step 3: If any row becomes (a1, a2, a3, a4, a5)	LOSSLESS ✓
Otherwise	LOSSY ✗

Importance of Lossless Decomposition

Lossless decomposition is a mandatory requirement of any normalization process. Without it:

Joining decomposed tables generates spurious/extra tuples
Original data cannot be recovered
The decomposition is useless (data is effectively lost/corrupted)

Key Rule: ALL normalization decompositions MUST be lossless. If a decomposition is lossy, it is not a valid normalization.

Lossless vs. Dependency Preserving

These are two separate properties of a decomposition:

Property	Meaning	Mandatory?
Lossless Join	Original can be reconstructed exactly	YES — always required
Dependency Preserving	All FDs can be checked in decomposed tables	Desired, but not always achievable (BCNF may sacrifice this)

A good decomposition should ideally be both lossless AND dependency-preserving. 3NF decomposition always guarantees both. BCNF guarantees lossless but not always dependency-preserving.

Lossless Decomposition

What is Decomposition?

Lossless Join Decomposition

Test for Lossless Decomposition (Binary)

Examples

Example 1 — Lossless Decomposition

Example 2 — Lossy Decomposition

Lossless Test — Tabular Method (Chase Algorithm)

Importance of Lossless Decomposition

Lossless vs. Dependency Preserving

Continue learning this concept

Lossless Decomposition

What is Decomposition?

Lossless Join Decomposition

Test for Lossless Decomposition (Binary)

Examples

Example 1 — Lossless Decomposition

Example 2 — Lossy Decomposition

Lossless Test — Tabular Method (Chase Algorithm)

Importance of Lossless Decomposition

Lossless vs. Dependency Preserving

Continue learning this concept