CREATE OWN LIBRARY

Lossless or Non-additive Join Decomposition

Concept of Lossless and Lossy Join Decomposition

We may decompose a single table into several tables to reduce redundancy. 

If we join all relations then the result may be a super set of original relation R.

Actually, three cases can occur,

Here case 3 is never possible, only case 1 and case 2 possible.

Why case 3 is not possible let’s see with an example.

Projection partition vertically column-wise. 

Here π doing vertical partitioning. 

Natural Join (⋈) always do at the common point here the common point is B.

First, we will do cross product-

We got the table after selection operation:

Note: 

Two tuples are extra from original relation R. we got these extra tuples because here some false match occurs.

This false match occurs because B (common attribute) neither unique at ${\mathbf{R}}_{\mathbf{1}}$ nor unique at ${\mathbf{R}}_{\mathbf{2}}$. So, B does not hold uniqueness property in both tables.

If B will be unique then a false match not occur. These duplicate values of B create an extra tuple (which is a match). If B would unique at ${\mathbf{R}}_{\mathbf{1}}$ or B would unique at ${\mathbf{R}}_{\mathbf{2}}$ or B would unique at both table ${\mathbf{R}}_{\mathbf{1}}$ and ${\mathbf{R}}_{\mathbf{2}}$ then false match (duplicate value) not occur.

So, 2 X 2 = 4, with 4, two values are matched with the original relation and two values are duplicate entry.

# Here lossy relation means not loss data from the original relation R (ABC) (for example). 

If some extra value comes at R (ABC), then it also calls lossy (decomposition).

# Now we try decomposing original relation by hold uniqueness property.

We decompose by A because A holds uniqueness property.

Why here duplicate entry does not occur because common element (A) is holding uniqueness property.

Note: So, if we want lossless join decomposition, so, the common attribute must be either super key of ${\mathbf{R}}_{\mathbf{1}}$ or super key of ${\mathbf{R}}_{\mathbf{2}}$ or super key of both tables.

At original relation R (ABC), A → B is Functional Dependency (FD) A → C is FD and A → BC is FD.

So, here ‘A’ (common attribute) is the super key of both tables.

#  Lossless join also called non – additive join because no additional tuple should come after joining. Only tuples accepted which exactly matched with original relation R (ABC).

Lossless Join decomposition Test:

Testing Condition

For example:

No common attribute. If at natural join no common attribute present then