GATE CSE 2019 | Question: 32

Question

Let the set of functional dependencies $F=\{QR \rightarrow S, \: R \rightarrow P, \: S \rightarrow Q \}$ hold on a relation schema $X=(PQRS)$. $X$ is not in BCNF. Suppose $X$ is decomposed into two schemas $Y$ and $Z$, where $Y=(PR)$ and $Z=(QRS)$.

Consider the two statements given below.

1. Both $Y$ and $Z$ are in BCNF
2. Decomposition of $X$ into $Y$ and $Z$ is dependency preserving and lossless

Which of the above statements is/are correct?

• A. Both I and II
• B. I only
• C. II only
• D. Neither I nor II

Comments

I did only one mistake while solving this is not writing the production S->Q under Z.

That made my answer completely wrong and I lost marks in GATE 2019 due to this

---

anyone else getting ans D

---

@indra kumar sahu No , C is right

Answer 1

$Y$ is in BCNF because binary attribute.
$Z$ is not in BCNF because $S\rightarrow Q$ is in $Z$ and $S$ is not Super key.

Dependency Preserving:

• $QR \rightarrow S$ in $Z$
• $R \rightarrow P$ is in $Y$
• $S \rightarrow Q$ is in $Z$

So it is dependency preserving.
Lossless:
$Y \cap Z = R$ which is is key of $Y$.
Lossless it is.
Only $2^{\text{nd}}$ is correct.

So Option C is the answer

Comments

Digvijay Pandey How we can say it is Dependency preserving case ?

from relation Y(PR)

F1 : R → P

from relation Z(QRS)

F2 :

Q -> RS  $(Q)^{+}$ =Q
R -> QS  $(R)^{+}$ =RP
S -> QR  $(S)^{+}$ =SQ
QR -> S   $(QR)^{+}$ =QRS  ---valid
QS -> R   $(QS)^{+}$ = QS
RS -> Q   $(RS)^{+}$ = RSQ  ---valid

 

$F1\cup F2 :$

R → p
QR → S
RS → Q

Now checking dependency preserving for F from $F1\cup F2 $
QR→S   --valid
R→P     --valid
S→Q  $(S)^{+}$ =S

S→ Q is not preserved

Correct me if i ‘m wrong .

Thanks in advance

---

• I guess you did a mistake in finding the FDs of F2( in the 3^rd line)
• You wrote S$^{+}$ = SQ (which is correct), so S→Q and not S→QR.
• P.S. – Even if we consider the wrong FD: S→QR, it can be decomposed to S→Q and S→R, hence S→Q will still hold in F2

@krishna423

---

If only by looking at the FD’s we can place all of them in some or the other decomposed tables, then it’s definitely FD preserving.

If not, only then we need to find closures.

Answer 2

F = {QR → S, R → P, S →Q}

X = (PQRS)

Candidate key: QR & SR    { (QR)+ = QRSP ; (SR)+ = SRQP}

partial dependency : R → P  {Prime attribute: Q,R,S ; Non-Prime Attribute : P} 

so, it is not in 2NF

Making 2NF  

Now it is in 2NF

checking for 3NF of relation Y(RP) and Z(QRS)

for relation Y(RP) it is in 3NF Because Binary relation is always BCFN (which means 1NF,2NF,3NF)

for relation Z(QRS) 

candidate key : QR & SR     { (QR)+ = QRS; (SR)+ = SRQ } 

so, it is in 3NF because  QR→ S { QR is a super key and S is prime attribute}

                                            S → Q { Q is a prime attribute} 

Now, checking for BCNF

Relation Y(RP) it is in 3NF Because Binary relation is always BCFN

Relation Z(QRS) is not in BCNF because S → Q where S is not a super key.

---

Now checking for FD Preserving:

FD(Y) = R → P

FD(Z) = QR → S , S → Q

FD = FD(Y) U FD(Z) = R → P, QR → S , S → Q = FD(X)

so,all function dependencies are preserve.

Now checking for Lossless:

1. Y(RP) U Z(QRS) = X(PQRS)
2. Y(RP) ∩ Z(QRS) = R { R is super key of Y relation)

so, it is lossless decomposition.

Thank you for reading.