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

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.

---

this will help !! 

https://gateoverflow.in/1398/gate-cse-2005-question-75?show=549596#c549596

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

@MWR I think it is being assumed here that all the entities participate fully in the relationships. Without total participation on both sides, we'll have a bunch of NULL values.

---

@MWR here the partial participation are there in 1:m side but can't say that null values are not allowed only 3NF(A nullable foreign key does not violate 3NF) and also aksed for min no. of tables so 4 is the corrcet answer if 3nf + null not allowed then 5 

---

sir you solved above question assuming null value are allow. so you got 4 as an answer.
But in question they did not mention "NULL VALUES" are allowed.
So, i solved above question without assuming "null value" and i got 5 as an answer and Realtions are below:

it is also correct or not please confirm.

Answer 2

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.

Comments

Clear explanation Thanks 👍

Answer 3

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

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

---

@amarVashishth how atomicity is violated , if we can spread the tuples violating atomicity in different rows?

Answer 4

answer is 4

Comments

how?

---

please explain this..

Answer 5

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

Answer 6

Three tables would be required for  three entities E1 ,E2,E3 now R12 is many to many relationship so new table will be created with(a11,a21) as key.R13 is one to many relationship so need of extra table

E1(a11,a12)

E2(a21,a22)

E3(a31,a32,a11') a11' is foreign key

R(a11,a21)

Comments

R12 will be R12(a11,a22)...

---

Can u plz explain what is the significance of the cardinality ratio in deciding the number of relations to be formed ?

---

E1 and E3 are connected by a 1 : n (1 on the side of E1 and n on the side of E3) relationship R13. So if you include a31 in E1 relation table then you may have to repeat one value(of a31) multiple no of times for one tupple of E1 table.(as it has 1: n cardinality, one instance of E1 is connected to n no of instance of E3). So we are doing the opposite thing. We are merging a11 to E3.(one instance of E3 is connected to only one instance of E1)