edited by
16,409 views
51 votes
51 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?
edited by

5 Answers

Best answer
64 votes
64 votes
  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
13 votes
13 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
3 votes
3 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.
2 votes
2 votes

a)lossless-join decomposition

b)not decomposition dependency-preserving

c) R1-----> 2NF

    R2------>BCNF

Related questions

54 votes
54 votes
6 answers
2
Kathleen asked Sep 15, 2014
16,627 views
From the following instance of a relation schema $R(A,B,C)$, we can conclude that:$$\begin{array}{|l|l|}\hline \textbf{A} & \textbf{B} & \textbf{C} \\\hline \text{1} & \...
33 votes
33 votes
2 answers
4
Kathleen asked Sep 15, 2014
5,599 views
The following table refers to search items for a key in $B$-trees and $B^+$ trees.$$\begin{array}{|ll|ll|} \hline & \textbf {B-tree} & & \textbf {B}^+\text{-tree} \\\hl...