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

there will be one more table for  E3 .i think relation for E1 nd E3 will be included in table for E3 itself as it is 1:n..else total =5 ,in the solution provided  by gateforum,they have not taken any table for E3 but decomposed the relation E1 E3 to avoid any transitive dependency between a11 and a32..that way they say ans to be 5..please explain

---

There is no transitive dependency in the above 4 relations rt? I didn't get what you were telling. This is GATE 2015 question and hence we have the official key and answer is 4 only. 

http://gate.iitk.ac.in/GATE2015/AnsKey2015/CS_S05.pdf

---

wont there be any table for E3 like E1 and E2?

---

Yes. But it also includes (a11) and thus R13.

---

Ok got it..thank you.

---

In the table for <a31, a32, a11> for E3 and E1-E3 relationship some a11 will remain null since E3 does not fully participate in the relation ..Right? 

---

"not fully"

where is it mentioned?

---

So , Arjun Sir , for this question we are considering that there is total dependency between E1 and E3 through relation R3 hence we are considering a two relations for E1 and (E3 and R1) , ryt ? if we wouldn't have done that then there would have been 3 relations for E1 , R1 , E3 respectively ryt ?

---

@Arjun sir....what is meaning of "We cannot combine any relation here as it will give rise to partial functional dependency and thus violate 3NF."

Please explain !!!

---

When we say R₁₃ is 1:n from E₁ to E₃, do we imply that for one value of the priary key (a₁₁), we have n entries in E_3? eg. for X11 value of attribute a₁₁ there are tuples in R₁₃ as (X11, P31), (X11,Q31) where P,Q are values of a_31. And also is the participation on E₃ total?

Only in this case will the relation R₁₃ be in 3NF as the primary key shall be a31 alone since FDs are            a31-->a32(given) and a31-->a11(one to many)

---

@Arjun Sir,

For relation R13 can we use primary key as combination of a₃₁ and a11? 

And a₁₁ will be a foriegn key in R₁₃ right?

---

@Arjun Sir, SO we have to assume E1-E3 has total participation ?

---

Here, for 1:N relationship why we need seprate table, plz explain?

---

@Arjun

What is meaning of this statement "We cannot combine any relation here as it will give rise to partial functional dependency and thus violate 3NF." How could we have combined otherwise if the condition of 3NF was not given.

---

http://cisnet.baruch.cuny.edu/holowczak/classes/9440/entityrelationship/

Is this link still active?

---

@Arjun Sir, If the question was asked of 1NF instead of 3NF. Then what would be the answer?

---

@arjun sir, in <a31, a32, a11>  for E3 and E1-E3 relationship what combination of attributes make up the key? I'm not getting the clarity here. we know a31 -> a32 in E3, then now even after combining E3 and E1-E3 relationship  is the key still {a31} i.e. a31 -> a11 as well? Because otherwise there will be partial dependency i think? Please help sir.

---

@  Queenia Agrawal, in $E3$ table, attributes are $A31, A32 $ & $ A11 $ where $A31$ is the primary key & $A11$ is the foreign key

---

@ayush updadyaya

As we know that primary key is the minimal superkey , since in E3 we already have a primary key a31 and since cardinality of E3 is 1 hence it will combine with only 1 tuple of E1

So initially if E3 would have been

A31.       A32.     

A31->A32

And suppose E3 after combining with E1 would have been

A31.        A32.     A11

Since the cardinality of E3 was 1 hence a31 must would have been combined with exactly 1 tuple from E1

Thus here A31 will be all distinct

A11 will be repeating

Hence here also

A31->A32,A11

Hence A31 will be the only primary key that's why this merging is also in 2NF since no partial dependency and also in 3NF since no transitive dependency.

And yes in E3 A11 will be the foreign key referring to A11 in E1

---

Even these 4 relations will be in bcnf also.

Anyone please confirm...

---

Here, we are checking whether 3NF is satisfied or not. How I think of it is : 

PK – primary key , FK – foreign key

R12 can’t be merge with E1 or E2 because… then we will be forming a composite key as say, only a11 won’t be able to identify each of the attributes values of the newly formed relational table which consist of attributes (a11, a21, a12, a22), as a11 can uniquely identify only a12, so a21 also have to be PK, so they combine to be a composite key.

Now, why didn’t we merge them? 

Because as said earlier then a12 can be uniquely identified by a11 i.e. which is:

 a11 -> a12, but a11 and a21 both combined were PK, so it gave rise to Partial Dependency. So, 2NF will be violated, hence 3NF would have been violated too. Yes, there might be the reason for being multivalued i.e. a row of an attribute may contain multiple values, hence violating 1NF .. but the one I mentioned earlier can be one of the reasons too, right?

Further, checking for why we combine R13 with E3?

It was done because here even after R13 was combined with E3, E3 still can uniquely identify each of its tuples using a31 which is PK of E3. And E1 has its own PK and as it’s 2-attributed hence, E1 satisfies all NF forms. Let’s come back to E3 again. Here, a31 will uniquely identify a32 and a11 and as we have only 1 PK in E3, so partial dependency can’t occur. We can also think that even an a11 of E3 can act as PK, but it can’t because a11 of E3 can contain redundant tuples as well as NULL, as it’s an FK.. so it may or may not be referencing E1 for particular tuples. Also, a32 may contain redundant values so it too can’t be PK. Hence, here in E3 only a31 will be uniquely identifying each of the tuples and on the LHS of an FD, only a31 should be present.

If everything makes sense or not, please let me know. And if I am getting something wrong then I am open to discussion. @adad20 @raja11sep

---

@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