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 nor unique at . 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 or B would unique at or B would unique at both table and 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 or super key of 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
Contributed by