1.6k views

For relation R=(L, M, N, O, P), the following dependencies hold:

$M \rightarrow O,$ $NO \rightarrow P,$ $P \rightarrow L$ and $L \rightarrow MN$

R is decomposed into R1 = (L, M, N, P) and R2 = (M, O).

1. Is the above decomposition a lossless-join decomposition? Explain.
2. Is the above decomposition dependency-preserving? If not, list all the dependencies that are not preserved.
3. What is the highest normal form satisfied by the above decomposition?
edited | 1.6k views

a) Yes as R1 ∩ R2 = M and M → O
b) NO

From the Dependencies obtained from R1 and R2, we CANNOT infer NO → P

Mistake That CAN be made: Here we CANNOT apply Pseudo Transitivity Rule using M→O & MN →P to obtain NO → P because the rule says :if M→O and NO→P then NM→P or MN→P , But here we have M→O and MN→P ... SO we CANNOT apply the rule here to obtain NO→P from it.

c) BCNF
R1 keys : P,L,MN hence BCNF
R2 key : M hence BCNF

edited
+2

a) and c) are correct. But if a dependency can be achieved only via a join, that dependency is not considered preserved. So, here NO->P dependency is not preserved on decomposition.

The lost dependency can be retrieved via join, but that is extra overhead on database operations. Thats the reason why dependency preserving is good to have but not strictly needed.

+1
Arjun Sir I read this somewhere:

R(A,B,C) : A->B : B->C : C->A

decomposed into:

R1(A,B) :A->B : B->A

R2(B,C) : B->C : C->B

is dependency preserving for the same reason given above.

Was the solution wrong ?
+3
No. In that case the dependency C->A can be inferred from C->B and B->A. i.e., we don't need a join operation to know that the dependency is preserved or not.
0

Arjun Sir here is an extract from Elmasri, Navathe

"It would be useful if each functional dependency X→Y specified in F either appeared directly in one of the relation schemas Ri in the decomposition D or could be inferred from the dependencies that appear in some Ri. Informally, this is the dependency preservation condition. We want to preserve the dependencies because each dependency in F represents a constraint on the database. If one of the dependencies is not represented in some individual relation Ri of the decomposition, we cannot enforce this constraint by dealing with an individual relation. We may have to join multiple relations so as to include all attributes involved in that dependency.

It is not necessary that the exact dependencies specified in F appear themselves in individual relations of the decomposition D. It is sufficient that the union of the dependencies that hold on the individual relations in D be equivalent to F"

I am so confused now.

+1
Thats saying exactly what I told. Words are a bit confusing. You can read it 2-3 times :)
0
it is not dependancy preserving decomposition
if u have any doubts in checking the DP just apply the algorithm for DP initially u will find dat a lengthy one but it helps alot
+2
@Danish I was wrong regarding the example you gave. Have corrected it now.
+1

@Arjun Sir just like  C->A can be inferred from C->B and B->A. Why cant we infer NO->P from M->O and MN->P ?

By Pseudo Transitivity Rule

if A->B and BC->D then AC->D

so Here we have M->O : MN->P from which we can infer ON->P or NO->P

why do we need a JOIN operation here ?

+4
M->O and MN -> P

We can't apply pseudo transitivity rule here rt?

M->O and NO -> P => MN -> P. This we can say using pseudo transitivity rule, not the other way around.
+1
Ohhhhkaay ... finally it fits into my head ... THANKS :)
0
Editing...
0
M hence bcnf???? what it means.arjun sir please explain,how R2 key is in bcnf
0
In NO--> P , NO is not super key then why decomposition is in BCNF?

Is it because this FD is not in a single relation i.e. R1 or R2?
0

Hi, I cannot understand how it is BCNF

c) BCNF
R1 keys : P,L,MN hence BCNF
R2 key : M hence BCNF

Could anyone explain it ?

+2

R1 holds following dependency-

1)MN->P (by psuedo transitivity rule(M->O and NO->P => MN->P))

2)P->L     3)L-> MN

So according to above dependencies candidate keys are (P,L,MN)

R2 holds following dependency-

1)M->O

So candidate key is only (M).

And according to BCNF definition, Whenever a nontrivial FD (X->A) holds in relation R, Then X is a superkey of R. So above decomposition in BCNF.

0
can anyone explain how keys for $R_1$ is $P,L,M,N$ ? i am getting only $P$ as key
0
@Anand, R1 keys are (P,L,MN) not (P,L,M,N). by the rule of psuedo transitivity R1 holds (MN->P) dependency also.

a.In R1 and R2 the common attribute is M,M+={MO}.We see that M is key for one of the decomposed relation R2,hence the decomposition is lossless.

b,

R1                           R2

P->L,L->MN              M->O

In R1 FD s covered are P →L and L →MN,in R2 M→O,.

We see that NO →P cannot be directly covered by any of the FD s in the decomposed relation.So this demands finding the additional FD s that can be implied in R1(using P →L and L →M,L->N),as well as R2(using M->O).All these FD s fail to cover NO->P ,as no way we can obtain P in the RHS.

So NO->P is not covered.

c)So till now we get.

R1                           R2

P->L,L->MN              M->O

R2 being a binary relation is in BCNF,M is SK and is LHS.

In R1 P is the key,

P+={PLMN}.

P is SK LHS and non trivial dependency.So ok.
L is non prime as well as MN is also non prime.So Transitive dependency is present.So not 3 NF.

Key is single attributed ,so no question of any prime attribute to be present.Hence 2 NF.
Hence highest Normal form in R1 is 2NF.

Colored portion is edited.

edited by
+2
For C part, the question asks for the given decomposition. We cannot decompose further.
0
Arjun Sir :Yes Thanks.Please have a look at the edited portion of the answer.Cannot understand how can R1 be BCNF.
+7
In R1, not only P but L and MN are also candidate keys. We have dependency MN -> P which comes from the given dependencies in question.
0

Hi Arjun Sir ,

Can you please elaborate on how L and MN are candidates for R1 ?

Projecting the FDs to R1 , we have

P->L,
L->MN

how MN -> P comes into picture ?

+2
M->O and NO->P, so MN -> P.
+2
@David

you have to take help from orignal FDs to make L and ML C.K
0
M -> O, NO -> P      implies MN -> P

MN ->P, P-> L           implies  MN -> L

L -> MN, MN->P       implies L -> P

Thus P,L,MN are all candidate keys
0
@Arjun sir I think NO is also a candidate key???
+1
Yes it is...but for Relation R not for the R1.
0
Yeah got it
0
In NO--> P , NO is not super key then why decomposition is in BCNF?

Is it because this FD is not in a single relation i.e. R1 or R2?
0
In R1 there is no O attribute. still you are making use of O to derive FD in R1? We should work with FDs which holds on current relation right?

a)lossless-join decomposition

b)not decomposition dependency-preserving

c) R1-----> 2NF

R2------>BCNF

1
2