in Databases edited by
9,242 views
44 votes

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?
in Databases edited by
9.2k views

Subscribe to GO Classes for GATE CSE 2022

4 Answers

54 votes
 
Best answer
  1. Yes as $R_1 ∩ R_2 = M$ and $M → O$
     
  2.  NO
    From the Dependencies obtained from $R_1$ and $R_2$, 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.
     
  3. BCNF
    $R_1$ keys : $P,L,MN$ hence BCNF
    $R_2$ key : $M$ hence BCNF
edited by

21 Comments

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. 

14
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 ?
4
edited by
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.
11

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.

0
Thats saying exactly what I told. Words are a bit confusing. You can read it 2-3 times :)
2
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
0
@Danish I was wrong regarding the example you gave. Have corrected it now.
3

@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 ?

1
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.
8
Ohhhhkaay ... finally it fits into my head ... THANKS :)
2
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 ?

4

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.

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

Attribute 'O' is not in relation R1. then how "MN->P (by psuedo transitivity rule(M->O and NO->P => MN->P))"

0
Please check my answer
0

@Arjun

How can R1 be in BCNF since the LHS of all the FDs in R1 are keys and not superkeys

( P → L , L → MN, MN → P, MN → L ) 

 Shouldn’t the highest normal form of R1 be 3NF ?

3
@shetu_raj  P,L,MN  are candidate keys for R1.and

Minimal superkey is candidate key hence they are superkeys also hence in BCNF.
1
9 votes

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

14 Comments

For C part, the question asks for the given decomposition. We cannot decompose further.
2
Arjun Sir :Yes Thanks.Please have a look at the edited portion of the answer.Cannot understand how can R1 be BCNF.
0
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.
10

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 ?

 

0
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
2
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
3
@Arjun sir I think NO is also a candidate key???
0
Yes it is...but for Relation R not for the R1.
1
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?
0
For C part, L+={L,M,N,O,P,L} try to derive it from set of original FDs not from the given sub relation R1, Even if it contains attributes not present sub relation. So, for L->MN, L is a key. Hence, R1 is in BCNF.
0
My Doubt

MN becomes a candidate key only with the help of O which is not present in R1. Therefore MN should not be a candidate key.

Where am I going wrong @Arjun sir?
0
2 votes

a)lossless-join decomposition

b)not decomposition dependency-preserving

c) R1-----> 2NF

    R2------>BCNF

3 Comments

edited by
part c wrong

I find this question important one as it taught me that I was following slightly wrong procedure to calculate FD's for sub relation. (here R1 and R2 are sub relation of R) . This wrong procedure might give correct answer for most of question but not for all

Mistake in your question :

While calculating CK for sub relation(i.e. for R1 and R2) don't go by normal procedure

i.e don't follow this procedure

first find what are attributes not there on right hand side of FD's include them , check if it suffice as CK? If not try to add some other attribute and so on

You followed this procedure and got just P as CK

but follow this procedure

Take each attribute(not just one that is not present in right hand side of FD of sub relation) in relation apply it's closure. In this process even if you derive some attribute (here O)that is not in sub relation  then also there is no problem .Also in this procedure even if have to use some attribute (here O) that is not in sub relation then also there is no problem , provided you have derived that attribute previously.

If you follow this procedure you can derive all CK for R1 not just {P}.

Also for part b , even most of time I also follow same procedure as of yours(i.e just distribute FD's present in R to all it's sub relation) . If any FD remains it is good idea to check (F1 U F2) + =  F .That is take closure of FD's for R1 and R2 and check if we can derive FD's that were unmapped . If we are able to derive it. It dependency preserving else not.
3

part c is wrong 

A relational schema R is considered to be in Boyce–Codd normal form (BCNF) if, for every one of its dependencies X → Y, one of the following conditions holds true:

so the part c IS BCNF

0
edited by
your C part is wrong. try to derive all functional dependency from original FD's
0
0 votes
First of all we have to determine the functional cover of the set of functional dependencies as given to determine all the non-trivial functional dependencies those can be generated from the given set of functional dependencies.

F={M->O,NO->P,P->L,L->MN}

Now F+={M->O,NO->P,P->L,L->MN,L->M,L->N,NO->L,NO->MN,MN->P,OTHER TRIVIAL DEPENDENCIES}

We have two decompositions

R1={L,M,N,P}

Let F1 be the set of functional dependencies which will projected on R1 from F+.

So F1={P->L,L->MN,L->M,L->N,MN->P,OTHER TRIVIAL DEPENDENCIES}

We have R2={M,O}

So F2={M->O,OTHER TRIVIAL DEPENDENCIES}

Now F’=$F1\cup F2={P->L,L->MN,L->M,L->N,MN->P,M->O,OTHER TRIVIAL DEPENDENCIES}$

F’+={P->L,L->MN,L->M,L->N,MN->P,M->O,P->MN,P->M,P->N,OTHER TRIVIAL DEPENDENCIES}

now if we compare F’+ and F+ we can see that NO->P and NO->L dependencies are not present in F’+ which are present in F+.

So this decomposition is not dependency preserving.

But this is lossless join decomposition as common attribute M is the candidate key in relation R2.

Now R2 is BCNF as it is a two attribute relation.

For R1 we have to determine the candidate keys from F1.

And we can easily determine the candidate keys are P,L,MN.

and all the dependencies in the F1 preserve the property of BCNF i.e LHS of all the FDs should be a superkey.

So R1 is also BCNF.

Related questions