Molina Exercise-3.3 BCNF decomposition

Question

Decompose into BCNF

R(A, B, C, D, E)

FD: AB->C, C->D, D>B, D->E

Comments

I think 4 table

B is extronious attribute here

---

I'm getting
R1(A, B, C), R2(B, D, E), R3(C, D)

---

how?

if we remove extraneous attribute

$A\rightarrow C$

$C\rightarrow D$

$D\rightarrow B$

$D\rightarrow E$

Now, $AB$ is key , So, is in 1 table

So, tables are

$\left ( ABC \right )$

$\left ( CD \right )$

Now how u merge $\left ( BD \right )$ and $\left ( DE \right )$ ??

(P.S.-BCNF should be lossless, but may or maynot dependency preserving)

---

D can functionally determine both B and E then why do u keep them in separate tables?

---

yes 3 is ans

---

@aditi19

Check this question

$F=\left \{ BCD\rightarrow A,BC\rightarrow E ,A\rightarrow F , F\rightarrow G , C\rightarrow D ,A\rightarrow G\right \}$

Number of tables required to decompose $R$ in $BCNF$ where $R=\left \{ A,B,C,D,E,F,G \right \}$ and $F$ is functional dependencies

Here how much r u getting?

---

i'm getting 4

---

how r u getting 4?

Can u explain the logic a bit?

---

R1(B, C, E)
R2(A, F)
R3(C, D)
R4(F, G)

---

They given R1(B, C, E,A)

Can u tell ur logic plz

---

how does BC alone functionally determines A?
in the relation R1(B, C, E, A) BC is not super key
in BCNF the LHS of the FD must be a super key

---

Sorry, I forgot to give $A\rightarrow G$

Now, check plz

---

Why $BC$ not a superkey?

I think it is a superkey

---

A->G is already implied by A->F and F->G transitively. it doesn't makes any difference. I'm still getting the same answer

---

$BC$ is key for every dependency exists here

$\left ( BC \right )^{+}=\left \{ ABCDEFG \right \}$

right?

---

@srestha

BC is the super key in the original relation. but when you normalize the relation to R1(B, C, E, A) here BC+ cannot functionally determine A. hence, BC is not super key in R1

---

but that is given in ans :(

Another point
$A\rightarrow F$

$A\rightarrow G$

So, $\left ( A,F,G \right )$ can be a relation

rt?

---

answer may be incorrect. I'm not sure
 if u make the relation (A, F, G)
there is transitive dependency too A->F and F->G. It violates 3NF
also F->G is not in BCNF as F+=FG. F cannot determine all attributes. Hence, it violates BCNF

---

And what about $BCD\rightarrow A$ dependency?

---

A->F and F->G. It violates 3NF

yes, right point 

---

And what about BCD→A dependency?

what about this @srestha?

---

It is a superkey

but that dependency not maintained
rt?

where that dependency maintained?

---

BCNF decomposition may not preserve functional dependency
https://gateoverflow.in/156721/when-does-bcnf-not-able-to-preserve-functional-dependency
but BCNF decomposition must be lossless

---

@aditi19

if we take $(BCDAE)$ then every dependency also maintained

right?

Then what is problem , if we take a table like $R_{1}(ABCDE)$

---

$R_{1}\left ( BCEA \right )$

because dependency $BCD\rightarrow A$

This dependency determines that $BC\rightarrow A$ also applicable

---

F={BCD→A,BC→E,A→F,F→G,C→D,A→G}
BC+=BCAD
yes you're correct, D is extraneous attribute. So BCD->A can be reduces to BC->A
then the relation R1(B, C, A, E) will be in BCNF

---

yes, hectic to think such question
How possible to think within 2 minutes in GATE Exam :(

---

I've the same question😂

Answer 1

yes, there will be $3$ tables

$\left ( A,B,C \right )$,$\left ( B,D,E \right )$,$\left ( C,D \right )$

In $\left ( A,B,C \right )$ here $\left ( {\color{Red} {A,B}},C \right )$ $AB$ is the key of the table

In $\left ( B,D,E \right )$ here $\left ( B,{\color{Red} {D}},E \right )$ $D$ is the key attribute

In $\left ( C,D \right )$ here $\left ( {\color{Red} {C}},D \right )$ $C$ is key attribute

In BCNF decomposition, if there are no key present in a relation, break it in a table and make a key attribute for that relation.

So, here $3$ tables will be enough

Ref:http://www.cs.colostate.edu/~cs430dl/yr2019sp/more_examples/Ch8/Decomposition%20into%20BCNF.pdf

Comments

R1(CD),C->D

R2(BDE),D->B,D->E

R3(AC) in BCNF DEPENDENCY PRESERVING ALWAYS NOT POSSIBLE.IS THIS CORRECT ????

---

if you will find closure of C = {B,C,D,E} you will see that there is derived dependency C — >B  

so your (A.B.C) is not in BCNF you have to further devide it into (A,B) (C,B) making it lossy decomposition

Answer 2

We get 3 BCNF Relations(DBE, CD, AC) which is lossless but not fd preserving due to AB→ C

--------------------------------------------------------

From given R(ABCDE) and FD’s : { AB->C, C->D, D>B, D->E} => CK={ AB,AC,AD} and Prime attributes = A,B,C,D .

So, D→ E is not in 2nf and C→ D, D→ B are not in BCNF.

find closure of all these  C+ = CDBE and D+ = DBE

1^st decompose into CDBE and AC.

in R1(CDBE) only C->D, D->B,D->E holds. we get CK ={C} and now again D->B,D->E are not in 3nf. so decompose into DBE(D->BE) and CD(C->D)

Therefore we get total 3 Relations(DBE, CD, AC) which are in BCNF.