Lossless Decomposition in DBMS

Any given decomposition is said to be lossless when the reconstruction of the relation R is easy from the decomposed tables with the help of joints. It is the preferred choice since the data/info will not be lost from the given relation after its decomposition. Here, the join results in the very same, original relation in the beginning.

In this article, we will take a look at the Lossless Join Decomposition in DBMS and its uses according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.

Table of Contents

• What is Lossless Decomposition in DBMS?
• Uses of Lossless Decomposition in DBMS
• Conditions Required for Lossless Decomposition in DBMS
• Lossless Decomposition in DBMS Example
  • Example 1
  • Example 2
• Practice Questions on Lossless Decomposition in DBMS
• FAQs

What is Lossless Decomposition in DBMS?

The decomposition of a given relation X is known as a lossless decomposition when the X decomposes into two relations X1 and X2 in a way that the natural joining of X1 and X2 gives us the original relation X in return.

Uses of Lossless Decomposition in DBMS

There are two types of decompositions in DBMS, lossless and lossy decomposition. The process of lossless decomposition helps in the removal of data redundancy from a database while still preserving the initial/original data.

How is a Decomposition Lossless?

In the case of lossless decomposition, one selects the common attribute. Here, the criteria used for the selection of a common attribute as this attribute has to be a super key or a candidate key in either relation X1, relation X2, or either of them.

In simpler words, the decomposition of the relation X into the relations X1 and X2 will be a lossless join decomposition in DBMS when a minimum of one of these functional dependencies is in F+ (Functional dependency closure).

X1 ∩ X2 → X1

OR

X1 ∩ X2 → X2

Conditions Required for Lossless Decomposition in DBMS

Let us consider a relation X. In case we decompose this relation into relation X1 and relation X2 sub-parts. This decomposition will be referred to as a lossless decomposition in case it satisfies these statements:

• If we union the sub relations X1 and X2, then it should consist of all the attributes available before the decomposition in the original relation X.
• The intersections of X1 and X2 can never be Null. There must be a common attribute in the sub relation. This common attribute must consist of some unique data/information.

Here, the common attribute needs to be the super key of the sub relations, either X1 or X2.

In this case,

X = (P, Q, R)

X1 = (P, Q)

X2 = (Q, W)

The relation X here consists of three attributes P, Q, and R. The relation X here decomposes into two separate relations X1 and X2. Thus, each of these X1 and X2 both have two attributes. The common attribute among each of these is Q.

Remember that the value present in column Q has to be unique. In case it consists of a duplicate value, then a lossless-join decomposition would not be possible here.

Lossless Decomposition in DBMS Example

Example 1

Draw a table with the relation X that has raw data:

X (P, Q, R)

This relation would decompose into the following sub relations, X1 and X2:

X1 (P, Q)

X2 (Q, R)

Let us now check the first condition that satisfies the lossless-join decomposition. Here, the union of the sub relations X1 and X2 generate the same results as the relation X.

X1 ∩ X2 = X

Here, we will get the result as follows:

X (P, Q, R)

This relation is similar to the original relation X. Thus, this decomposition can be considered as the lossless join decomposition in DBMS.

Example 2

Let us take a look at an example:

<Cand_Info>

Let us decompose this table mentioned above into the following tables:

<Cand_Details>

<Sec_Details>

Let us now apply Natural Join in the tables mentioned above. The result generated here would be:

Thus, the relation mentioned above has a lossless decomposition. In simpler words, no information would be lost here.

Practice Problems on Lossless Decomposition in DBMS

1. If X (P, Q, R, S) is a relational schema and it consists of these functional dependencies:

P → Q, Q → R,

R → S and S → Q

If the relation X decomposes into the following

(P, Q), (Q, R), (Q, R)

it would:

A. Generate a lossless join. It is not dependency preserving

B. Generate a lossless join. It is dependency preserving

C. Does not generate a lossless join. It is not dependency preserving

D. Does not generate a lossless join. It is dependency preserving

Answer: B. generate a lossless join. It is dependency preserving

Here, P, Q, R, and S are all key attributes. One can derive all the attributes out of every one of these attributes.

Since the intersection of all of the relations here is Q, and Q derives every other attribute, the relation here is lossless.

2. Let us consider a relation X (P, Q, R, S). Which of these have no lossless join, and is a BCNF decomposition that is dependency-preserving.

A. P -> Q, Q -> RS

B. P -> Q, Q -> R, R -> S

C. PQ -> R, R -> PS

D. P -> QRS

Answer: C. PQ -> R, R -> PS

As we know, in the case of a lossless decomposition, the common attribute has to be a candidate key in any of the relations.

A. P -> Q, Q -> RS

X1 (PQ) and X2 (QRS)

Q acts as the key of the second. Thus, it is a lossless decomposition.

B. P -> Q, Q -> R, R -> S

X1 (PQ) , X2 (QR), X3 (RS)

Q acts as the key of the second. R is the key of the third. Thus, it is a lossless decomposition.

C. PQ -> R, R -> PS

X1 (PQR), X2 (RS)

R acts as the key of the second, but R -> P violates the condition of BCNF in PQR since R does not act as a key. This PQR can be decomposed further into PQ -> R since the dependency would be lost here.

D. P -> QRS

It already is in BCNF.

Thus, Option C. PQ -> R, R -> PS is the correct answer here.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.

Also Explore,

• Introduction to DBMS
• Join Dependency in DBMS
• Lossy Decomposition in DBMS
• Multivalued Dependency in DBMS
• Decomposition in DBMS
• First Normal Form in DBMS
• Functional Dependency in DBMS