Decomposition in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Decomposition in DBMS.

 

We have discussed-

• Decomposition is a process of dividing a single relation into two or more sub relations.
• Decomposition of a relation can be completed in the following two ways-

 

 

1. Lossless Join Decomposition
2. Lossy Join Decomposition

 

In this article, we will learn how to determine whether the decomposition is lossless or lossy.

 

Determining Whether Decomposition Is Lossless Or Lossy-

 

Consider a relation R is decomposed into two sub relations R₁ and R₂.

Then,

• If all the following conditions satisfy, then the decomposition is lossless.
• If any of these conditions fail, then the decomposition is lossy.

 

Condition-01:

 

Union of both the sub relations must contain all the attributes that are present in the original relation R.

Thus,

R1 ∪ R2 = R

 

Condition-02:

 

• Intersection of both the sub relations must not be null.
• In other words, there must be some common attribute which is present in both the sub relations.

Thus,

R1 ∩ R2 ≠ ∅

 

Condition-03:

 

Intersection of both the sub relations must be a super key of either R₁ or R₂ or both.

Thus,

R1 ∩ R2 = Super key of R1 or R2

 

PRACTICE PROBLEMS BASED ON DETERMINING WHETHER DECOMPOSITION IS LOSSLESS OR LOSSY-

 

Problem-01:

 

Consider a relation schema R ( A , B , C , D ) with the functional dependencies A → B and C → D. Determine whether the decomposition of R into R₁ ( A , B ) and R₂ ( C , D ) is lossless or lossy.

 

Solution-

 

To determine whether the decomposition is lossless or lossy,

• We will check all the conditions one by one.
• If any of the conditions fail, then the decomposition is lossy otherwise lossless.

 

Condition-01:

 

According to condition-01, union of both the sub relations must contain all the attributes of relation R.

So, we have-

 R₁ ( A , B ) ∪ R₂ ( C , D )

= R ( A , B , C , D )

Clearly, union of the sub relations contain all the attributes of relation R.

Thus, condition-01 satisfies.

 

Condition-02:

 

According to condition-02, intersection of both the sub relations must not be null.

So, we have-

R₁ ( A , B ) ∩ R₂ ( C , D )

= Φ

Clearly, intersection of the sub relations is null.

So, condition-02 fails.

Thus, we conclude that the decomposition is lossy.

 

Problem-02:

 

Consider a relation schema R ( A , B , C , D ) with the following functional dependencies-

A → B

B → C

C → D

D → B

Determine whether the decomposition of R into R₁ ( A , B ) , R₂ ( B , C ) and R₃ ( B , D ) is lossless or lossy.

 

Solution-

 

Strategy to Solve   When a given relation is decomposed into more than two sub relations, then- Consider any one possible ways in which the relation might have been decomposed into those sub relations. First, divide the given relation into two sub relations. Then, divide the sub relations according to the sub relations given in the question. As a thumb rule, remember- Any relation can be decomposed only into two sub relations at a time.

 

Consider the original relation R was decomposed into the given sub relations as shown-

 

 

Decomposition of R(A, B, C, D) into R'(A, B, C) and R₃(B, D)-

 

To determine whether the decomposition is lossless or lossy,

• We will check all the conditions one by one.
• If any of the conditions fail, then the decomposition is lossy otherwise lossless.

 

Condition-01:

 

According to condition-01, union of both the sub relations must contain all the attributes of relation R.

So, we have-

 R‘ ( A , B , C ) ∪ R₃ ( B , D )

= R ( A , B , C , D )

Clearly, union of the sub relations contain all the attributes of relation R.

Thus, condition-01 satisfies.

 

Condition-02:

 

According to condition-02, intersection of both the sub relations must not be null.

So, we have-

 R‘ ( A , B , C ) ∩ R₃ ( B , D )

= B

Clearly, intersection of the sub relations is not null.

Thus, condition-02 satisfies.

 

Condition-03:

 

According to condition-03, intersection of both the sub relations must be the super key of one of the two sub relations or both.

So, we have-

 R‘ ( A , B , C ) ∩ R₃ ( B , D )

= B

Now, the closure of attribute B is-

B⁺ = { B , C , D }

Now, we see-

• Attribute ‘B’ can not determine attribute ‘A’ of sub relation R’.
• Thus, it is not a super key of the sub relation R’.
• Attribute ‘B’ can determine all the attributes of sub relation R₃.
• Thus, it is a super key of the sub relation R₃.

 

Clearly, intersection of the sub relations is a super key of one of the sub relations.

So, condition-03 satisfies.

Thus, we conclude that the decomposition is lossless.

 

Decomposition of R'(A, B, C) into R₁(A, B) and R₂(B, C)-

 

To determine whether the decomposition is lossless or lossy,

• We will check all the conditions one by one.
• If any of the conditions fail, then the decomposition is lossy otherwise lossless.

 

Condition-01:

 

According to condition-01, union of both the sub relations must contain all the attributes of relation R’.

So, we have-

 R₁ ( A , B ) ∪ R₂ ( B , C )

= R’ ( A , B , C )

Clearly, union of the sub relations contain all the attributes of relation R’.

Thus, condition-01 satisfies.

 

Condition-02:

 

According to condition-02, intersection of both the sub relations must not be null.

So, we have-

 R₁ ( A , B ) ∩ R₂ ( B , C )

= B

Clearly, intersection of the sub relations is not null.

Thus, condition-02 satisfies.

 

Condition-03:

 

According to condition-03, intersection of both the sub relations must be the super key of one of the two sub relations or both.

So, we have-

 R₁ ( A , B ) ∩ R₂ ( B , C )

= B

Now, the closure of attribute B is-

B⁺ = { B , C , D }

Now, we see-

• Attribute ‘B’ can not determine attribute ‘A’ of sub relation R₁.
• Thus, it is not a super key of the sub relation R₁.
• Attribute ‘B’ can determine all the attributes of sub relation R₂.
• Thus, it is a super key of the sub relation R₂.

 

Clearly, intersection of the sub relations is a super key of one of the sub relations.

So, condition-03 satisfies.

Thus, we conclude that the decomposition is lossless.

 

Conclusion-

Overall decomposition of relation R into sub relations R₁, R₂ and R₃ is lossless.

 

Next Article- Introduction to Normal Forms

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Decomposition of a Relation-

 

The process of breaking up or dividing a single relation into two or more sub relations is called as decomposition of a relation.

 

Properties of Decomposition-

 

The following two properties must be followed when decomposing a given relation-

 

1. Lossless decomposition-

 

Lossless decomposition ensures-

• No information is lost from the original relation during decomposition.
• When the sub relations are joined back, the same relation is obtained that was decomposed.

Every decomposition must always be lossless.

 

2. Dependency Preservation-

 

Dependency preservation ensures-

• None of the functional dependencies that holds on the original relation are lost.
• The sub relations still hold or satisfy the functional dependencies of the original relation.

 

Types of Decomposition-

 

Decomposition of a relation can be completed in the following two ways-

 

 

1. Lossless Join Decomposition-

 

• Consider there is a relation R which is decomposed into sub relations R₁ , R₂ , …. , R_n.
• This decomposition is called lossless join decomposition when the join of the sub relations results in the same relation R that was decomposed.
• For lossless join decomposition, we always have-

 

R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn = R

where ⋈ is a natural join operator

 

Example-

 

Consider the following relation R( A , B , C )-

 

A	B	C
1	2	1
2	5	3
3	3	3

R( A , B , C )

 

Consider this relation is decomposed into two sub relations R₁( A , B ) and R₂( B , C )-

 

 

The two sub relations are-

 

A	B
1	2
2	5
3	3

R₁( A , B )

 

B	C
2	1
5	3
3	3

R₂( B , C )

 

Now, let us check whether this decomposition is lossless or not.

For lossless decomposition, we must have-

R₁ ⋈ R₂ = R

 

Now, if we perform the natural join ( ⋈ ) of the sub relations R₁ and R₂ , we get-

 

A	B	C
1	2	1
2	5	3
3	3	3

 

This relation is same as the original relation R.

Thus, we conclude that the above decomposition is lossless join decomposition.

 

NOTE-

 

• Lossless join decomposition is also known as non-additive join decomposition.
• This is because the resultant relation after joining the sub relations is same as the decomposed relation.
• No extraneous tuples appear after joining of the sub-relations.

 

2. Lossy Join Decomposition-

 

• Consider there is a relation R which is decomposed into sub relations R₁ , R₂ , …. , R_n.
• This decomposition is called lossy join decomposition when the join of the sub relations does not result in the same relation R that was decomposed.
• The natural join of the sub relations is always found to have some extraneous tuples.
• For lossy join decomposition, we always have-

 

R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn ⊃ R

where ⋈ is a natural join operator

 

Example-

 

Consider the following relation R( A , B , C )-

 

A	B	C
1	2	1
2	5	3
3	3	3

R( A , B , C )

 

Consider this relation is decomposed into two sub relations as R₁( A , C ) and R₂( B , C )-

 

 

The two sub relations are-

 

A	C
1	1
2	3
3	3

R₁( A , B )

 

B	C
2	1
5	3
3	3

R₂( B , C )

 

Now, let us check whether this decomposition is lossy or not.

For lossy decomposition, we must have-

R₁ ⋈ R₂ ⊃ R

 

Now, if we perform the natural join ( ⋈ ) of the sub relations R₁ and R₂ we get-

 

A	B	C
1	2	1
2	5	3
2	3	3
3	5	3
3	3	3

 

This relation is not same as the original relation R and contains some extraneous tuples.

Clearly, R₁ ⋈ R₂ ⊃ R.

Thus, we conclude that the above decomposition is lossy join decomposition.

 

NOTE-

 

• Lossy join decomposition is also known as careless decomposition.
• This is because extraneous tuples get introduced in the natural join of the sub-relations.
• Extraneous tuples make the identification of the original tuples difficult.

 

Next Article- Rules to Determine Lossless and Lossy Decomposition

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.