FOR FREE MATERIALS

Q: GATE and example Lossless Join Decomposition

Q. Gate 

Let relation R (ABCD) and we decompose the relation into two relations

Which is true?

Prerequisite: Before seeing the answer please follow the previous chapter: Concept of Lossless and Lossy Join Decomposition.

Solution:

We know if decomposition is lossy then R ⊂ S. 

So, here option C is correct.

Now check for another option

a. S ⊂ R here it is not possible because we have two options.

So, the subset is not possible.

b. R ⋃ S = R is false because S is a superset of R, so, subset ⋃ superset = superset i.e. R ⋃ S = S always. 

c. R ⋈ S = S is also false because (Smaller set ⋈ Bigger set) = Smaller set. So, if R⊂ S then R ⋈ S = R is true.

Why follow the example

And R ⊆ S or R ⊂ S then R ⋈ S = R.

We get match tuple and get R.

Q. Check the decomposition is lossy or lossless

1. R (ABCD) 

{AB → C, C → A, C → D}  ,  Decomposition (D) = {AB, ACD}

2. R (ABCDEF)

{A→ B, C → DE, AC → F},  D = {BE, ACDEF}

3. R (ABCDE)

{A → BC, CD → E, B → D, E → A}, D = {ABC, ACDE}

Before seeing the answer to the above questions follow the previous chapter: Concept of Lossless and Lossy Join Decomposition.

To check lossless or lossy we check the following three conditions

Solution for question 1: 

Then,

So, it is lossy decomposition.

Solution for question 2: 

Then, 

So, it is lossy decomposition.

Solution for question 3: 

Then,

and 

So, it is lossless decomposition.

We can check another one but not necessary. 

As if now we are checking lossless or lossy for only two relations. But now we are going to check for more than two relations like we want to decomposed relation R (ABCDE) to {AB, BC, CDE}

At a time three relations can’t check for lossless or lossy.

Between three decompose relations (R1, R2, R3), we check any two which can join by the lossless way, join them, after that again check resultant relation and rest of relation which is possible join with lossless way if, possible join them, if we got all combination of relation pair which make lossless join then the whole decomposition is lossless, if any of pair of relationships fails to join as lossless in this process then it is lossy.

We will not try all possible combinations, we only try one possible pair (relation) way and we try to select relation pair which join as lossless.