Question

Consider a schema R(A, B, C, D) and following functional dependencies.

A → B

B → C

C → D

D → B

Then decomposition of R into R₁(A, B), R₂(B, C) and R₃(B, D) is _______

1. Dependency preserving and lossless join.
2. Lossless join but not dependency preserving.
3. Dependency preserving but not lossless join.
4. Not dependency preserving and not lossless join.

Answer 1

Correct Answer - Option 1 : Dependency preserving and lossless join.

The correct answer is "option 1".

CONCEPT: 

Lossless join: If there is no loss of information by replacing a relation R with two relation schema R1 & R2, then join can be said as Lossless decomposition.

That means, after natural join R1 & R2, we will get exactly the same relation R.

Some properties of lossless decomposition are:

1. R1 ∩ R2 = R1 or R1 ∩ R2 = R2

2. R1 U R2 = R

3. R1 ∩ R2 = super key of either R1 or R2

Decomposition preservation: Decomposition D = { R1,R2..R_n } of relation R is dependency preserving with respect to Functional dependency F if :

Closure of Union of all functional dependencies with respect to each relation is equivalent to closure of F.

In other words, If relation R has FD F, its decomposed relations R1 & R2 has FD F1 & F2 respectively then, F' = F1 U F2 & F'⁺ = F⁺ .                   

EXPLANATION: 

Lossless: Consider relation R1(A,B) & R2(B,C):

R1 ∩ R2 -> (B)⁺ -> { B,C,D }                      {B is common attribute in both relation so find its closure}

Since B⁺  derives relation R2, Hence, relation R1'(A,B,C) is lossless.

Now consider relation R1'(A,B,C) & R3(B,D):

R1' ∩ R3 -> (B)+ -> { B,C,D }                      {B is common attribute in both relation so find its closure}

Since B+  derives relation R3, Hence relation R(A,B,C,D) is lossless.

Decomposition: 

Here,

R1(A,B) -> { A->B },     --- FD1

R2(B,C) -> { B->C },     --- FD2

R3(B,D) -> { D->B }      --- FD3

F' = FD1 U FD2 U FD3

    = { A->B, B->C, D->B }

Now find closure of F' & F :

F'⁺ = {A,B,C,D} & F⁺ = {A,B,C,D}

Since the closure of F' also preserve dependency C -> D,

Hence, given decomposition of R into R1(A, B), R2(B, C) and R3(B, D) is dependency preserving and lossless join.

1. If any one of the above lossless properties fails then the decomposition will be lossy decomposition.

Lossy decomposition after natural join includes some extra information including the whole relation.

2. Decomposition preservation can also be described as "if all the functional dependencies can be derived or preserved even after decomposition of relations by finding closure of the union of decomposed relation & original relation."