GATE CSE 2015 Set 1 | Question: 41

Question

Consider an Entity-Relationship $(\text{ER})$ model in which entity sets $E_{1}$ and $E_{2}$ are connected by an $m:n$ relationship $R_{12}$. $E_{1}$ and $E_{3}$ are connected by a $1 : n$ ($1$ on the side of $E_{1}$ and $n$ on the side of $E_{3}$) relationship $R_{13}$.

$E_{1}$ has two-singled attributes $a_{11}$ and $a_{12}$ of which $a_{11}$ is the key attribute. $E_{2}$ has two singled-valued attributes $a_{21}$ and $a_{22}$ of which $a_{21}$ is the key attribute. $E_{3}$ has two single-valued attributes $a_{31}$ and $a_{32}$ of which $a_{31}$ is the key attribute. The relationships do not have any attributes.

If a relational model is derived from the above $\text{ER}$ model, then the minimum number of relations that would be generated if all relation are in $\text{3NF}$ is________________.

Comments

What If the question was asked of 1NF instead of 3NF. Then what would be the answer?

---

If it is in 3NF it is automatically in 1NF.

I don’t think that would make any difference .

Someone pls correct me if I am wrong

---

@Mitali gupta you can merge all tables you got in 3NF into 1 table, it would be in 1NF.

Answer 1

Answer is $4$. The relations are as shown:

$\langle a_{11}, a_{12}\rangle$ for $E_1$

$\langle a_{21}, a_{22}\rangle$ for $E_2$

$\langle a_{31}, a_{32}, a_{11}\rangle$ for $E_3$ and $E_1-E_3$ relationship

$\langle a_{11}, a_{21}\rangle$ for $m:n$ relationship $E_1-E_2$

We cannot combine any relation here as it will give rise to partial functional dependency and thus violate $\text{3NF}.$

Reference: MIT notes

Comments

@Arjun sir even if i found the minimum number of tables with the help of general idea that for every relation and entity type how many tables do we want so in that case also i am getting the same ans …. but here i am not able to understand the role of 3nf or (if it would have been bcnf) ...can u plz explain me that is that general idea always works or should we apply the basic intution every time while solving these questions ?

---

I also had the same doubt, but what we see in ER model to find how many tables would be there, and what are the conditions for a relation to be in 3rd NF or any NF. Every NF is the subset of its preceding NF. So in 3^rd NF, we have to see whether the relation is in 2^nd NF that means if the candidate key is composite in the relation table then after merging the tables all the attributes of that particular table must be fully dependent on that composite key, not on only 1 key of the composite key. But in many-many relations after merging the entity table attributes would be only fully dependent on that table's primary key not on another table's primary key, so it violates the rule of 2^nd NF, hence it also violates the 3^rd NF, so this relation can’t be merged.

Now coming to your last question that” is that general idea always works or should we apply the basic intuition every time while solving these questions” I would suggest if your concept is crisp, always go with your concept, it will never betray you. Practice questions using the concepts, in the beginning, it will take time to solve questions, and later you will get the speed.

All the best to you.

And as @ankit3009 said “If everything makes sense or not, please let me know. And if I am getting something wrong then I am open to discussion”

Thank You.

---

@Deepak Poonia   Sir i think yha pr 5 tables ban ni chaiye , aapne bataya the in one to many mapping if both side are optional , so 3 tables bnegi and Many to many always 3 tables so e1 is common in both so 5 Relations hue na 

Answer 2

We have 4 Tables generated from this ER Diagram:

$$\begin{align*} E_1\left(a_{11}, a_{12} \right )\\ E_2\left(a_{21}, a_{12} \right )\\ R_{12}\left(a_{11}, a_{21} \right )\\ R_{13}E_3\left(a_{31}, a_{32}, a_{11}\right ) \end{align*}$$

we have to keep a separate table for $R_{12}$ because if we combine it with any other entity it will violate 1NF, as atomic values won't be there for some attribute. So, to preserve the relationship between $E_1$ and $E_2$ we need to have a separate table $R_{12}$

Comments

we have to keep a separate table for R12 because if we combine it with any other entity it will violate 1NF, as atomic values won't be there for some attribute.

Yes, it is true. if we add $a_{21}$ to $E_{1}$, $a_{21}$ may become multi valued beacuse of many to many participation. LIke wise if we add $a_{11}$ to $E_{2}$, $a_{11}$ may become multi valued. So we create new relation for $R_{12}$.

---

Shouldn’t it be E2(a21, a22)?

---

it won’t violate atomicity but may violate either primary key or single valued attribute condition in a cell

Answer 3

For a relation to be in 3NF all functional dependencies should be fully on candidate key.

If we try to merge relation R₁₂ with either E₁ or E₂ then the new relation will have a compostie key since it is a many-to-many relation. And this will lead to partial dependency. Hence it cannot be merged. 

Relation R₁₃ is one-to-many relationship. Merging it with E₃ will not create a composite key and will not create any partial dependencies, so it can be merged.

Hence answer 4.

Answer 4

Entity E1.
a1  a12
--------
a11 is key

Entity E2
a21  a22
--------
a22 is key

Entity E3
a31  a32
--------
a31 is key

R12 is m:n Relationship between E1 and E2
R12
a11     a22
-------------
(a11, a22) is key.


R13 is 1:n Relationship between E1 and E3
R13
a11   a31
-----------
(a11, a31) is key.


We need minimum no. of tables. 
Can we remove any of the above tables without 
loosing information and keeping the relations in 3NF?


We can combine R13 and R12 into one.  
a11   a31   a22
------------------
(a11, a31, a22) is key.


The relation is still in 3NF as for every functional 
dependency X -> A, one of the following holds
1) X is a superkey or
2) A-X is prime attribute 

Comments

@heena singh
"Entity E2
a21  a22
--------
a22 is key"

Here a21 is key and that is given in the question.

correct it plz.

---

@kuljeet Shan you are right