GATE CSE 2002 | Question: 16

Question

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).

• A. Is the above decomposition a lossless-join decomposition? Explain.
• B. Is the above decomposition dependency-preserving? If not, list all the dependencies that are not preserved.
• C. What is the highest normal form satisfied by the above decomposition?

Comments

Apply Chase Algorithm for Lossless Decomposition.

Beautifully explained by Deepak Sir : https://m.youtube.com/watch?v=YNsvuPA_vf0&list=PLIPZ2_p3RNHjweUdD-fgcdD-oMiylqE9t&index=5&pp=iAQB#

---

1.  R1 intersection R2 = M , and M is superkey in R2 hence lossess

2. dependency is not preserving  becz   FD NO---> P is not preserved

3.  the decomposition R1 and R2 both are in BCNF

---

Applied this Rule !!

For lossless   

 must be true

For Lossy

https://www2.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter7/node8.html#SECTION00731200000000000000

Answer 1

• A. Yes as $R_1 ∩ R_2 = M$ and $M → O$
   
• B.  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.
   
• C. BCNF
  $R_1$ keys : $P,L,MN$ hence BCNF
  $R_2$ key : $M$ hence BCNF

Comments

sorry sir, got it where i was wrong

---

In R1 if we do L+ then it will give L,M,N but not P then how it is a superkey ? same with MN as MN cannot derive P & L from R1 then how MN is a key ?

---

Answer is correct. And no edit is necessary, whoever flagged the answer need to clear their concept first. 

@amar100 is not considering other possible CKs in R1, CKs of R1 are L, P, MN. 
And CK is minimal "SUPERKEY" if you be thoughtful enough and consider all FDs you will find that all FD's LHS are SKs this is enough to determine this is BCNF. 
refer this comment to understand your mistake and don't go flagging everything you think is wrong 

Answer 2

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.

Comments

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?

---

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.

---

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?

Answer 3

a)lossless-join decomposition

b)not decomposition dependency-preserving

c) R1-----> 2NF

    R2------>BCNF

Comments

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.

---

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:

• X → Y is a trivial functional dependency (i.e., Y is a subset of X)

• X is a superkey for schema R

so the part c IS BCNF

---

your C part is wrong. try to derive all functional dependency from original FD's

---

I think there is no need to derive all the attribute's closure in the original FD that is surely time taking procedure, it is clear that the only dependency that hold on the R1 is
1. P -> L
2. L -> MN

here we can clearly see P is a candidate key, that is obvious, the problematic fd is the second one, in the first glance we can see it is not candidate key since it couldn't derive P, but that is only when we consider the closure within these two fd, we should rather look into the original fd and find if L can actually derive all the attribute, (i,e is L a candidate key) in this case it is, so it does not violate the 3NF and BCNF, hence both R1 and R2 are in BCNF.

if we blindly take closure for every single attribute that is simply a waste of time.

Answer 4

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.

Answer 5

Those who solving the Part A Refer this link . 

Here There is also second method must to check, 

When You apply the  first method of Lossless join 

1. R1 intersection R2 →  R1 or R2 must have superkey( then it lossless join 

        If not then check for this also ,

2. if (R₁ ∩ R₂)→ (R₁ - R₂) or (R₁ ∩ R₂)→ (R₂ - R₁) holds in F⁺(this should be present in the given Functional Dependencies)  then it’s a lossless-join decomposition

database - Lossless Join Decomposition - Stack Overflow

Answer 6

Given:

R = (L, M, N, O, P)

Functional Dependencies:
F = { M → O, NO → P, P → L, L → MN }

Decomposition:
R1 = (L, M, N, P)
R2 = (M, O)

A. Lossless-Join Decomposition

For a binary decomposition R → R1, R2, the decomposition is lossless if:

(R1 ∩ R2) → R1  OR  (R1 ∩ R2) → R2

Here,

R1 ∩ R2 = {M}

Now calculate M+:

M → O

Therefore,

M+ = {M, O}

Since R2 = (M, O),

M+ contains all attributes of R2.

Hence,

M → R2

Therefore, the decomposition is LOSSLESS-JOIN.

Answer: YES.

B. Dependency Preservation

We check each functional dependency:

1. M → O

Both M and O are present in R2.

Therefore, M → O is preserved.

2. P → L

Both P and L are present in R1.

Therefore, P → L is preserved.

3. L → MN

L, M and N are all present in R1.

Therefore, L → MN is preserved.

4. NO → P

N and P are in R1, but O is in R2.
There is no decomposed relation containing N, O and P together.

Also, NO → P cannot be derived from the projected dependencies of R1 and R2.

Therefore, NO → P is NOT preserved.

Hence, the decomposition is NOT dependency-preserving.

Dependency not preserved: NO → P.

C. Highest Normal Form

Consider R1 = (L, M, N, P).

The dependencies in R1 are:

P → L
L → MN

Find P+:

P+ = {P}
P → L
Therefore, P+ = {P, L}
L → MN
Therefore, P+ = {P, L, M, N}

Thus, P is a candidate key of R1.

Now consider:

L → MN

But L is NOT a superkey because:

L+ = {L, M, N}

P is not obtained.

Therefore, R1 is NOT in 3NF (and hence not in BCNF).

However, the candidate key P contains only one attribute.
Therefore, partial dependency is impossible.

Hence, R1 is in 2NF.

R2 = (M, O) has M → O, where M is a candidate key, so R2 is in BCNF.

Therefore, the highest normal form of the decomposition is:

2NF

FINAL ANSWERS:

A. Lossless-join decomposition: YES

B. Dependency-preserving: NO
   Dependency not preserved: NO → P

C. Highest Normal Form: 2NF