🔐 LOSSLESS DECOMPOSITION

🔐 LOSSLESS DECOMPOSITION

DBMS • Normalization • Lossless Join • Step-by-Step Examples

📘 What will you learn?

This interactive lesson explains:
✔ What is Decomposition?
✔ What is Lossless Decomposition?
✔ Why decomposition is required
✔ Lossless Join
✔ Step-by-step example
✔ Lossless decomposition using Functional Dependency
✔ Lossy vs Lossless decomposition
✔ Short exam questions

📖 What is Decomposition?

Decomposition means dividing one large relation into two or more smaller relations.

The purpose is to reduce redundancy and avoid problems such as update, insertion and deletion anomalies.

Example

EMPLOYEE( Employee_ID, Employee_Name, Department_ID, Department_Name )

We can divide it into:

EMPLOYEE(Employee_ID, Employee_Name, Department_ID)

DEPARTMENT(Department_ID, Department_Name)

❓ Why Do We Decompose a Relation?

1

Reduce Data Redundancy
The same information does not need to be stored repeatedly.

2

Avoid Update Anomaly
Changing information in one place does not require many repeated updates.

3

Avoid Insertion Anomaly
New information can be inserted without unnecessary data.

4

Avoid Deletion Anomaly
Deleting one record should not accidentally remove unrelated information.

🎯 Decomposition is mainly used during database normalization.

🔐 What is Lossless Decomposition?

A decomposition is called Lossless if we can join the decomposed relations and obtain exactly the original relation.

Original Relation ↓ Decomposition ↓ JOIN ↓ Original Relation

No information is lost.

The join does not produce incorrect or extra tuples.

Simple Meaning

Think of a paper being divided into two pieces. If the two pieces can be joined together perfectly to reconstruct the original paper, the decomposition is lossless.

📊 Simple Lossless Example

Original Relation

Student_ID	Student_Name	Course_ID
101	Rahul	C01
102	Anita	C02

Decompose into Two Relations

R1(Student_ID, Student_Name)

R2(Student_ID, Course_ID)

R1

Student_ID	Student_Name
101	Rahul
102	Anita

R2

Student_ID	Course_ID
101	C01
102	C02

Both tables contain Student_ID. Therefore they can be joined using Student_ID.

R1 ⋈ R2

ON Student_ID

The original information can be reconstructed.

Therefore the decomposition is LOSSLESS.

🧮 Step-by-Step Lossless Decomposition

Consider:

R(A, B, C)

Functional Dependency:
A → B

Decompose R into:

R1(A, B)

R2(A, C)

1

Common attribute between R1 and R2 is:

A

2

Given Functional Dependency:

A → B

3

R1 contains:

A and B

4

Because A determines B, the common attribute A can determine all attributes of R1.

5

Therefore joining R1 and R2 using A can reconstruct the original relation.

🎯 RESULT

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

Since A → B, the decomposition is:
LOSSLESS ✅

🔗 Lossless Decomposition Using Functional Dependency

For a binary decomposition of relation R into R1 and R2, the decomposition is lossless when the common attributes can determine all attributes of at least one decomposed relation.

R1 ∩ R2 → R1
OR
R1 ∩ R2 → R2

Example

R(A,B,C)

R1(A,B)
R2(A,C)

A → B

1

Find common attributes:

R1 ∩ R2 = {A}

2

Check whether A determines R1.

3

Given A → B. Therefore A determines both attributes of R1: A and B.

4

Therefore:

A → R1

The decomposition satisfies the lossless condition.

LOSSLESS DECOMPOSITION ✅

⚠️ Lossy Decomposition

A decomposition is called Lossy when joining the decomposed relations produces extra or incorrect tuples, or when the original relation cannot be reconstructed correctly.

Original Relation ↓ Decomposition ↓ JOIN ↓ ❌ Extra Tuples / Incorrect Information

Important:

A lossy decomposition may create spurious tuples during JOIN.

Example

Student	Course
Rahul	DBMS
Anita	OS

If the decomposition does not preserve the required relationship, joining the smaller relations may incorrectly combine Rahul with OS or Anita with DBMS.

Spurious tuple = Incorrect tuple produced after JOIN.

⚖️ Lossless vs Lossy Decomposition

Feature	Lossless	Lossy
Information	Preserved	May be incorrect
JOIN	Reconstructs original relation	May produce extra tuples
Spurious Tuples	No	Possible
Database Design	Preferred	Not preferred
Normalization	Desired	Should be avoided

📐 Lossless Join Test Condition

For a binary decomposition of R into R1 and R2, let the common attributes be:

R1 ∩ R2

The decomposition is lossless if the common attributes functionally determine all attributes of R1 or all attributes of R2.

(R1 ∩ R2) → R1

OR

(R1 ∩ R2) → R2

Example

R1(A,B)
R2(A,C)

Common Attribute = A

Given A → B

A determines R1(A,B). Therefore:

LOSSLESS ✅

📋 Quick Summary

Concept	Meaning
Decomposition	Splitting a relation into smaller relations
Lossless	Original relation can be reconstructed
Lossy	JOIN may produce incorrect/extra tuples
Common Attribute	Attribute shared by decomposed relations
Spurious Tuple	Incorrect tuple generated by JOIN
FD	Helps determine whether decomposition is lossless

Remember:

LOSSLESS = No information is lost + correct JOIN

LOSSY = Incorrect/extra tuples may appear

❓ Short Questions & Answers

Q1. What is decomposition?

Decomposition is the process of dividing a large relation into two or more smaller relations.

Q2. What is lossless decomposition?

A decomposition is lossless if joining the decomposed relations reconstructs the original relation without losing information or producing incorrect tuples.

Q3. What is a lossy decomposition?

A lossy decomposition may produce extra or incorrect tuples when the decomposed relations are joined.

Q4. What is a spurious tuple?

A spurious tuple is an incorrect or extra tuple produced after joining decomposed relations.

Q5. Why is lossless decomposition important?

It ensures that the original information can be reconstructed correctly after decomposition.

Q6. What is the role of Functional Dependency?

Functional Dependencies help determine whether a decomposition satisfies the lossless-join condition.

B.K. PAUL

Bhairab Ganguly College

DBMS • Normalization • Lossless Decomposition

Interactive Learning Module