Whether decomposion is lossless and dependency preserving. #testseries

Question

Consider a Relation R {A,B,C,D,E,F} with FDs {${A \rightarrow B, AB \rightarrow C, D \rightarrow AC, D \rightarrow E}$} . R is decomposed into R₁ {ABC}, R₂{DE} and R₃{ACD}. What can be said about decomposition.

1. lossless and dependency preserving.
2. lossless but not dependency preserving.
3. lossy and dependency preserving.
4. lossy and not dependency preserving.

Answer 1

Condition for dependency preservation : 

A decomposition is said to be dependency preserving if the FDs of the original relation is preserved in the FDs of the subrelation either directly or indirectly.

So in the given case the FDs : { A --> B  , AB --> C } goes to R1(ABC)

                                           : { D --> E } goes to R2(DE)

                                           : { D --> AC } goes to R3(ACD)

Hence all FDs of the original relation are mapped here directly itself successfully .  Hence the given decomposition is dependency preserving .

Condition for lossless decomposition : 

For decomposition of R into R1 and R2 , it is lossless if R1 intersection R2 is a key of either R1 or R2 else the decomposition is lossy and will lead to some extra records if we remerge R1 and R2(also known as spurious records) and each of the attributes of the original relation will be in some table at least.

So we consider the given decomposition.

If we take R2 intersection R3 w.r.t attributes we get 'D' as a common attribute which is key of both R2 with R3 , although only one of them will do.

Hence we merge R2 and R3 and we get now R'(ADCE) . Taking intersection with R1 , we get  'AC' as a common attribute set which is key for R1 and hence we can remerge them . 

Hence the condition mentioned above is met ..But the second condition is not met as the attribute F is not present in any of the subrelations and hence the decomposition is lossy.

Hence 3) should be the correct answer.

Comments

when we merge relation r1,r2 and r3  then we never get relation r . bcz attribute f is not present in decomposed relation . then how it is lossless????

---

U r right @abhishekmehta4u .. Thanks for rectifying .

---

Sir if we take intersection of R1 AND R2 than we get AC as common so it should be key in any one
But in R1 A is the only key so can we conclude ans with this thing or am i going wrong

---

@Habibkhan sir : when we merge R' with R1,

we get 'AC' as common attribute set but it is not key in R1.

'A' is the key in R1. so if we merge tables, we will get decomposition as lossy. since common attribute set is not common in either of tables (R' or R1).

where am i wrong ?

sry i didnt read your comment @vijay kumar 2 :)

Answer 2

It is dependency preserving as all FD's can be generated by table R1 R2 R3

 

 

It is not lossless hence lossy because  Intersection of common attribute in table should be Key for one table and as we can see there is no F in any of table but there is F in actual table so it is lossy.

 

hence option 3.

Answer 3

Suppose the relation R is decomposed into two relations R1 and R2.

Then $R1\cap R2\rightarrow R1  or  R1\cap R2\rightarrow R2$ that means if the common attributes of both decomposed relations form a superkey of either R1 or R2 then the decomposition is lossless.

Here the common attribute between R2 and R3 is D and D is superkey of R2.Now the common attributes between R1 and R2R3 is AC and AC is also a superkey of R1 as we can determine that A is the candidate key of R1 from the projected functional dependencies.So we can’t say the decomposition is lossy from this observation.

But F attribute is not present in any of the decomposed relations so we loss the information of attribute F.

And R1$R1\ast R2\ast R3!=R$ where * represents natural join