GATE IT 2004 | Question: 73

Question

Consider the following entity relationship diagram $(ERD)$, where two entities $E1$ and $E2$ have a relation $R$ of cardinality 1:m.

The attributes of $E1$ are $A11$, $A12$ and $A13$ where $A11$ is the key attribute. The attributes of $E2$ are $A21$, $A22$ and $A23$ where $A21$ is the key attribute and $A23$ is a multi-valued attribute. Relation $R$ does not have any attribute. A relational database containing minimum number of tables with each table satisfying the requirements of the third normal form ($3NF$) is designed from the above $ERD$. The number of tables in the database is

• A. $2$
• B. $3$
• C. $5$
• D. $4$

Comments

And what will be the minimum number of tables required for this question, Will it be 2??

---

this will help !!

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

Answer 1

We need just two tables for $1NF$.

$\text{T1: {A11, A12, A13}}$

$\text{T2: {A21, A22, A23, A11}}$

$\text{A23}$ being multi-valued, $\text{A21, A23}$ becomes the key for $T2$ as we need to repeat multiple values corresponding to the multi-valued attribute to make it $1NF$. But, this causes partial FD $A21 \to A22$ and makes the table not in $2NF$. In order to make the table in $2NF$, we have to create a separate table for multi-valued attribute. Then we get

$T1: \{A11, A12, A13\} -$ key is $A11$
$T2: \{A21, A22, A11\} -$ key is $A21$
$T3: \{A21, A23\} -$ key is $\{A21, A23\}$

Here, all determinants of all FDs are keys and hence the relation is in $\text{BCNF}$ and so $3NF$ also. So, we need minimum $3$ tables.

Correct Answer: $B$

PS: Even if “3NF” isn't explicitly mentioned in question we should assume it and we cannot add NULL entries during ER to Relational conversion. 

Reference: https://www.cs.uct.ac.za/mit_notes/database/htmls/chp06.html#relationship-participation-condition-membership-class

Comments

@Arjun,

As per Navathe book, while converting ER diagram to Relational Table, we are told to directly create table for multivalued attribute. So by giving example of this 1NF, do you mean this step is wrong ? They are not assuming anything at start of chapter about this algorithm other than ->

"We assume that the mapping will create tables with simple single-valued
attributes. "

Following is step in given algorithm !

 Step 6: Mapping of Multivalued Attributes. For each multivalued attribute A,
create a new relation R. This relation R will include an attribute corresponding to A,
plus the primary key attribute K—as a foreign key in R—of the relation that represents the entity type or relationship type that has A as a multivalued attribute. The
primary key of R is the combination of A and K. If the multivalued attribute is composite, we include its simple components.

So in case if they ask this question without requirement of 3NF, this algo will give incorrect answer right ?
 

---

I think mapping always tries to maintain highest normal form. The algorithm I followed is not standard. I guess without specifying "normal form" question is ambiguous.

---

Why don't we need A11 in T3? Shouldn't we be maintaining referential integrity there too?

---

this decomposition doesn't preserve the FD A21->A23. so how can it be in 3NF?

---

won't A12 and A13 cause transitive dependencies in table T1 violating 3NF condition?

---

no @bhavana, without explicitly given you can't assume it by yourself.

---

@Arjun Sir, In 1NF I think we can manage it with 1 table only even though redundancy will be there. 1NF just says that we need to have atomic or indivisible values for attributes and that can be achieved with 1 table only.

Please confirm.

---

@Arjun sir one more partial FD $A21\rightarrow A11$ isn't there??

---

But the definition of 1NF tells that if a table contains multi-valued attribute or composite attribute then the relation can't be in 1NF. How the given table is initially in 1NF?

---

what will be the answer if requirement of 1NF is given not 3 Nf

is it 2 tables?

---

@Prateek Raghuvanshi, how $A21 $ is partially dependent upon $A11$

$A11$ is the primary key for table $T1$ & in table $T2$ it is the foreign key

---

@rajatmyname, he given table is initially in 1NF because every column holds atomic values

---

@Bipin Jaiswal, if requirement given is $1NF$, then it would be $2$ tables

---

@Subarna Das

Why there will be Only 2 table In 1NF.

In 1NF We have to create a new table for Multiple Attribute.

---

According to the Definition

1NF -------- No Multivalue and No Composite Attribute

2NF ------ No partial Dependencies

3NF ------ No Transitive Dependencies.

---

@ kumar.dilip, in $1NF$ we have to have atomic values in each column

An example of Multi-valued Attribute is phone no.

---

@ Subarna Das when we merge R with E2 then in relation (A21,A22,A23,A11) will be attributes and key will be A21 A23 together. so A21-->A22 and A21-->11 will be partial dependencies there .but when we split the relation into (A21,A22,A11) AND (A21,23). then there is no partial dependency and relation also be in 3NF .

---

@kumar.dilip @Subarna Das

Even if we consider 1NF for E2..where A21 is key attribute and A23 is multivalued attribute .

If we separate multivalued attribute value to separates rows of the table it cause redundancy which has no problem in 1NF ..but it will violating key constraint right ..then A21 will not be able identify each tuple uniquely ..is this fine in 1NF ?

 

---

@jatin khachane 1

yes you're correct.

supppose A23 is phone number & A21 is SSN.

then - 

A21(SSN)	A22	A23(ph. number)	A11
256		(89745,55569)
257		(78842,52289)
258		(12458,25478)

we can't write A23 like this in any relation, now if we want to separate the A23 values then A21 will become have duplicate values,which is also not acceptable as per rules of primary key.

So, we've to create a new table - A23, A21 where A21 is the foreign key referring A21 in E2 table.

Now here I've a doubt. why're we taking the key as {A21,A23}. The key can be A23 itself as it has no duplicate values & NULL values.

---

A21	A23
256	89754
256	55569
257	78842
257	52289
258	12458
258	25478

The new table will be as shown above

here A21 can't be P key since it has duplicate values

A23 also can't be primary key since it may be possible that any 2 persons have added same phone number

But the combination of A21 and A23 will always be unique.

here uniqueness is coming because after making duplicate values in A21 we were not able to make it Pkey but when we add A23 to each A21 values it discards redundancy as each tuple is unique.

---

@Satbir, got it thanks :)

some person may have same ph. number or some person may have not, which is occuring NULL in A23.

---

@Arjun @srestha @Bikram How can we say that "A23 being multi-valued, A21, A23 becomes the key for T2 as we need to repeat multiple values corresponding to the multi-valued attribute to make it 1NF. But, this causes partial FD A21→A22 and makes the table not in 2NF. In order to make the table in 2NF, we have to create a separate table for multi-valued attribute" (Text marked in BOLD)? 

Please Help, as i am not able to get the role of 3NF in question. Although, I am able to get the answer.

---

We can take here an example

Suppose 3 column in a table.

A21	A22	A23
X	Y	Z
M	N	O
P	Q	R

Now, A21 is key and , A23 multivalued attribute.

Suppose Z has two multivalued attribute Z0,Z1

Now, as both Z0,Z1 depend on X, so now, keys will be Z0,X and  Z1,X

But, check again Y depends only on X.

So,

 this causes partial FD A21→A22 and makes the table not in 2NF

---

Thanks @srestha.

Just wanted to confirm that before making a table into 2NF, we have to make a separate table for Multi-valued Attribute coz It is a property in 1NF to make all attributes Atomic. And, therefore, we can remove Partial dependencies (in this case, it is removed by making a separate table for Multi-valued Attribute) way before. 

---

@srestha @Arjun @Satbir @MRINMOY_HALDER

Is this is the Correct approach to understand this question? 

PFA.

PIC-1 https://gateoverflow.in/?qa=blob&qa_blobid=1547559989532837545

PIC-2 https://gateoverflow.in/?qa=blob&qa_blobid=2240489087553170119

---

@ayushsomani

pic is not clearly understandable. Can u plz write it clearly.

---

@srestha

You have a problem in understanding the solution or the quality of pic?

---

clearity of pic.

---

@Arjun sir @Bikram sir @jothee madam

 

By the logic, Arjun sir followed can we say that "If more than 1 multivalued attributes are present in entity E2 , we can combine all multivalued attributes in 1 separate table (3rd table) for 3NF ? " 

---

without explicit mention of FDs how can we answer such question. I mean they have just said that A11 is key, so we know these FDS are there:- A11-->A12  A11-->A13 , But how do we know there arent any other FD like A12-->A13. Because if there is A12-->A13 then 3 tables wont be enough for 3NF.

---

Does relational database by itself does not put the constraint of atomic attributes ?

If yes, then why do we need to check for 1NF because that would not be possible then.

---

@Arjun sir,

Can’t the relation like R1 (A11, A12, A13, A21)  and  R2 (A21, A22, A23) possible? I think it also satisfies 3NF  

---

@rish1602 If you consider this, then A21 will be the Primary Key for R1 relation due to 1:M mapping ( as A11 can repeat ) and thus Partial Participation at E1 side will not be possible.

---

@Arjun sir, the given data doesn’t say anything about dependency between A12 and A13, which could lead to a transitive dependency and would fail the definition of 3NF. Sir, how can we conclude that determinants of all FDs are keys? Request yo to kindly explain. Thank you.

---

T2 is not in 2NF right then how can it be in 3NF

---

@Deepak Poonia @Arjun

In T2,(A21,A22,A11) Can A11 can contain null values as there is no total participation from E2. And It is not given in the question that null values are allowed.

---

@Arjun sir,

But here you are allowing NULL entries.
Since there is no full participation from many side then merging the reationship table with many side can create null entries, then how are we avoiding NULL entries ? 

---

sir are null values allowed or not? if yes no problem otherwise you need 4 relations right??????

---

@ashish gusai 
Very Good Question and a Important one to understand the Concept of Theory of normalization,

---

Yes that's true it is allowing null values

Answer 2

one table for E1 , two tables for E2(A21,A22 and A21,A23) bcoz we need to make a seperate table for multi-valued attribute to satisfy minimum 1NF condition that requires atomic attributes. Now, Relation table can be merged with (A21,A22). So we have following tables.

E1(A11,A12,A13)     E21(A11,A21,A22)     and   E22(A21,A23)

So ans is 3 tables in all.

 

Comments

I am getting min 2 tables

---

I don't understand why it is given as E21(A11,A21,A22) ? Here what is the purpose of including the primary attribute of 1st entity.

---

Here the primary attribute of first entity is included in order to create a relationship between the two tables. To understand well you can take table E21 as Employee table where each employee can participate in only one relationship and table E1 as Department table where each department can participate in multiple relationships.

---

@amkrj,

 For multivalued attributes there will be an additional table like MT(A21, A23). Other 2 tables for each entity and relation is maintained by adding E1's PK as FK in E2's table.

Hence 3 tables.

Answer 3

$E1(\underline{A11},A12,A13)$

$\underline{A11}\rightarrow A12\ A13$

$CK:A11$

$3NF:\checkmark$

 

$E2R(\underline{A21},A22,A23,A11) $

$A21\rightarrow\rightarrow A23=Allowed\ in\ 2NF/3NF/BCNF$

$A21\rightarrow A22\ A11$

$CK:\underline{A21A23}$

$\underbrace{A21\rightarrow A22\ A11}=partial\ dependency$

Therefore Decompose into tables

$(A21,A23)$

$A21\rightarrow\rightarrow A23=Trivial\ MVD$

$CK:\underline{A21A23}$

$(A21,A22,A11)$

$A21\rightarrow A22\ A11$

$CK:A21$

$3NF:\checkmark$

Answer 4

hope you will get an answer from here:

http://db.grussell.org/section006.html

Answer 5

Diagram clearly shows one to many, as well as PARTIAL PARTICIPATION from both side(single lines). That clearly means 3 tables are required.

Answer 6

three tables one for E1  and one for E2 which will also include reationship R and 1 table for multivalued attribute of E2 whose PK wil be (21,23) together .hence 3 tables required.

Comments

Is it correct to say that every tuple in E1 corresponds to m in E2 or is it vice versa?

i am confused. plz clear me

---

each tuple in E1 can be related to none(because E1 is partially participating in the relationship) or 1 or even more than one tuples of entity set E2…but each tuple in E2 will be related to at most 1 tuple in the E1 ….so u can say the it is one to many relationship ...with cardinality of E1 is m  and cardinality of E2 is 1.