GATE CSE 2005 | Question: 75

Question

Let $E_1$ and $E_2$ be two entities in an $E/R$ diagram with simple-valued attributes. $R_1$ and $R_2$ are two relationships between $E_1$ and $E_2$, where $R_1$ is one-to-many and $R_2$ is many-to-many. $R_1$ and $R_2$ do not have any attributes of their own. What is the minimum number of tables required to represent this situation in the relational model?

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

Comments

@Prashant_Dubey

https://gateoverflow.in/blog/16592

---

I think I can explain this concept very easily and in a more intuitive way. Also I will explain this in hindi.

Hamare paas do entities hain E1 and E2, entities matlab tables, halanki ER mein entity kehte and database jab realize hota to wo hi ek table mein badal jati hai.

Ab E1 let's say kehte hain ki GATEOVERFLOW USERS NAME hai and E2 kehte hain ki GATEOVERFLOW USERS ASKED QUESTIONS hai.

E1 (GATEOVERFLOW USERS NAME) aisa dikhta hai:

ID	USERNAME
1	ARJUN
2	DEEPAK POONIA
3	SACHIN MITTAL 1

 

E2 (GATEOVERFLOW USERS ASKED QUESTIONS) aisa dikhta hai:

ID	TOPICS	Ye third column kya ho sakta hai?
1	Pumping Lemma
2	Threading
3	Pipelining
4	Venn Diagrams
5	Paging

 

Abhi dono entities independent hai inke beech mein koi relation nhi hai.

magar abhi mein ek relation laa raha hoon one to many jahan par E1 one side rahegi and E2 many sides, now, 

ye relation main kehta hoon ki kuch aisi hai "A user asked questions" yaani E1 mein user E2 ke diye hue topics puchte hain.

to ye aisa sa ho sakta ki ARJUN asked Pumping lemma, Deepak Poonia asked Threading, Deepak Poonia asked Pipelining, Sachin Mittal 1 asked Venn Diagrams, Sachin Mittal 1 asked Paging, and ye one to many follow kar raha hai.

To aise mein ye relation kaise banaya ja sakta? Kya ek nayi table ka use karna zaruri hai? Well kar sakte magar phir uske koi sense nhi hai kyonki phir to hum cheezein waste karenge space ka use karke, aur optimal designing technique ka bilkul istemal nhi hoga.

Abhi karna kya hoga ki jo E2 mein third column hai hum usmein hi ek foreign key banayenge jo ki E1 ko reference karegi and phir E2 kuch aisa dikhega.

ID	TOPICS	USERNAME (Foreign Key)
1	Pumping Lemma	Arjun
2	Threading	Deepak
3	Pipelining	Deepak
4	Venn Diagrams	Sachin Mittal 1
5	Paging	Sachin Mittal 1

 

To aise mein entity 2 ke andar hi humne relation one to many laga li and isiliye sirf 2 tables ka use hua.

 

 

2nd part mein relation many to many hai yaani ki ya to ek user ek se zyada Topics puch sakta hai ya phir ek hi topic ko alag alag users puch sakte.

Ab sochke dekho ki kya hum is relation ko E1 and E2 ke andar bana sakte well technically yes kyonki jab multivalued attribute ki baat hogi to usko nayi row mein daal denge single attribute banane ke liye magar isse redundancy badhegi. And redundancy controlled way mein badhegi to theek hai magar undefinite amounts mein redundancy ek buri designing technique hai and GATEOVERFLOW USERS ka har din questions asked badhta hi rahega jo redundancy exponentially badhayega. And ismein sabse zyada dikkat dene wali cheez updation anamoly hogi probably. 

Abhi ismein bahut log sochenge nayi table mein bhi to ek hi username ke chalte alag alag topics puchna ya phir ek hi topic ko alag alag users ke dwara puchna bhi to redundancy create karega magar ismein 2 cheezein hain.

1. Ye ek naya table hai ismein redundancy ho bhi jayegi to uska asar directly to original entity mein nhi padega.

2. hum ismein kyonki hamare paas id's hain unka use karenge, to aise mein user names ya Topics na puchke direct unki id use karke hell lot of space bacha sakte also execution bhi fast ho sakega because ab sirf ek number ko padhna hai bajaye ek string ke. 

Isliye many to many mein ek extra table banani padegi kaam 2 mein bhi ho jayega magar wo optimized nhi hai, also question mein minimum number of tables diya hai to minimum ke liye to kam table ka hi use karenge magar that is not how designing works. Minimum tables required hamesha optimization ko dhyan mein rakh kar hi banti hain.

---

I hope this will help !!

Case-01: 1:1 Relationship (Both Side Partial)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |---- 1 ------| R |------ 1 ----|    B    |
        +---------+             +---+             +---------+

Here, two tables will be required-

 

1. A ( a1 , a2 )

2. B ( b1 , b2 , a1 )

Case-02: 1:1 Relationship (1: Partial, 1: Full)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |---- 1 ------| R |====== 1 ====|    B    |
        +---------+             +---+             +---------+

Here, one table will be required-

 

1. AB ( a1 , a2 , b1 , b2 )

Case-03: 1:m Relationship (Both Side Partial)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |---- 1 ------| R |------ m ----|    B    |
        +---------+             +---+             +---------+

Here, two tables will be required-

 

1. A ( a1 , a2 )

2. BR ( b1 , b2 , a1 )

Case-04: 1:m Relationship (1: Full, m: Partial)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |==== 1 ======| R |------ m ----|    B    |
        +---------+             +---+             +---------+

Here, two tables will be required-

 

1. A ( a1 , a2 )

2. BR ( b1 , b2 , a1 )

Case-05: 1:m Relationship (1: Partial, m: Full)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |---- 1 ------| R |====== m ====|    B    |
        +---------+             +---+             +---------+

Here, two tables will be required-

 

1. A ( a1 , a2 )

2. BR ( b1 , b2 , a1 ) (Note: 'a1' becomes a mandatory NOT NULL foreign key here)

Case-06: m:m Relationship (Both Side Partial)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |---- m ------| R |------ m ----|    B    |
        +---------+             +---+             +---------+

Here, three tables will be required-

 

1. A ( a1 , a2 )

2. B ( b1 , b2 )

3. R ( a1 , b1 )

Case-07: m:m Relationship (m: Partial, m: Full)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |---- m ------| R |====== m ====|    B    |
        +---------+             +---+             +---------+

Here, three tables will be required-

 

1. A ( a1 , a2 )

2. B ( b1 , b2 )

3. R ( a1 , b1 )

Case-08: m:m Relationship (Both Side Full)

       (a1)      (a2)                        (b1)      (b2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +---+             +---------+
        |    A    |==== m ======| R |====== m ====|    B    |
        +---------+             +---+             +---------+

Here, three tables will be required-

 

1. A ( a1 , a2 )

2. B ( b1 , b2 )

3. R ( a1 , b1 )

 

Case-09: Weak Entity Set & Identifying Relationship

A Weak Entity (W) cannot exist without its Strong Entity (A). It is connected by an Identifying Relationship (double diamond) and has total participation (double line). It only has a "partial key" (w1).

 

       (a1)      (a2)                        (w1)      (w2)
         \       /                             \       /
          \     /                               \     /
        +---------+             +===+             +=========+
        |    A    |---- 1 ------||R||====== m ====|    W    |
        +---------+             +===+             +=========+

Rules: The weak entity table must include the primary key of the strong entity to form a composite primary key.

Here, two tables will be required:

 

1. A ( a1 , a2 )

2. W ( a1 , w1 , w2 ) (Note: 'a1' is a foreign key referencing A, and combined with 'w1', it becomes the primary key for W)

Case-10: Multivalued Attribute

An attribute that can hold multiple values for a single entity (represented by a double oval). Example: A person having multiple phone numbers.

                     +======+
                    //  a3  \\  <-- Multivalued (e.g., Phone Numbers)
                   //        \\
                  +============+
                        |
       (a1)      (a2)   |
         \       /      |
          \     /       |
        +---------------+
        |       A       |
        +---------------+

Rules: A multivalued attribute must be extracted into its own separate table, linked back to the main entity.

Here, two tables will be required:

 

1. A ( a1 , a2 )

2. A_a3 ( a1 , a3 ) (Both form a composite primary key)

Case-11: Composite Attribute

An attribute composed of multiple smaller sub-parts. Example: An 'Address' (a2) broken down into 'City' (a21) and 'State' (a22).

 

                       (a21)   (a22)
                         \       /
                          \     /
       (a1)                 (a2)
         \                   |
          \                  |
        +--------------------+
        |         A          |
        +--------------------+

Rules: Do not create a column for the main composite attribute (a2). Instead, only create columns for its simple component parts (a21, a22).

Here, one table will be required:

 

1. A ( a1 , a21 , a22 )

Case-12: Unary (Recursive) Relationship (1:m)

An entity relates to itself. Example: An Employee (A) manages other Employees (A).

 

       (a1)      (a2)
         \       /
          \     /
        +---------+    1    +---+
        |    A    |---------| R |
        +---------+         +---+
             |                |
             |_______ m ______|

Rules: Use a single table, but add a foreign key column that references its own primary key.

Here, one table will be required:

 

1. A ( a1 , a2 , Manager_a1 ) (Manager_a1 is a foreign key referencing a1 in the same table)

Case-13: Unary (Recursive) Relationship (m:m)

Example: A Course (A) can have many prerequisite Courses (A), and a Course can be a prerequisite for many other Courses.

 

       (a1)      (a2)
         \       /
          \     /
        +---------+    m    +---+
        |    A    |---------| R |
        +---------+         +---+
             |                |
             |_______ m ______|

Rules: Because it is m:m, you must create a new junction table.

Here, two tables will be required:

 

1. A ( a1 , a2 )

2. R ( a1_id1 , a1_id2 ) (A junction table holding pairs of related primary keys)

Case-14: Ternary Relationship (m:n:p)

Three distinct entities (A, B, C) share a single relationship (R). Example: A Doctor (A) prescribes a Medicine (B) to a Patient (C).

 

       (a1)      (a2)                 (b1)      (b2)
         \       /                      \       /
          \     /                       \     /
        +---------+      +---+        +---------+
        |    A    |------| R |--------|    B    |
        +---------+      +---+        +---------+
                           |
                           |
                      +---------+
                      |    C    |
                      +---------+
                         /   \
                       /       \
                     (c1)     (c2)

Rules: Create a table for each entity, plus one junction table for the relationship containing the primary keys of all three entities.

Here, four tables will be required:

 

1. A ( a1 , a2 )

2. B ( b1 , b2 )

3. C ( c1 , c2 )

4. R ( a1 , b1 , c1 )

 

Case-15: Relationship with its own Attribute

Sometimes, the relationship itself contains data (e.g., in a many-to-many relationship where an Employee (A) works on a Project (B), the relationship Works_On (R) might have an attribute Hours_Worked (r1)).

 

                           (r1)  <-- Attribute on the relationship
                             |
       (a1)      (a2)        |               (b1)      (b2)
         \       /           |                 \       /
          \     /            |                  \     /
        +---------+        +---+              +---------+
        |    A    |----m---| R |----n---------|    B    |
        +---------+        +---+              +---------+

Rules: The attribute belonging to the relationship goes into the junction table alongside the primary keys of the participating entities.

Here, three tables will be required:

 

1. A ( a1 , a2 )

2. B ( b1 , b2 )

3. R ( a1 , b1 , r1 )

Case-16: Generalization / Specialization (ISA Relationship)

This represents inheritance. A superclass entity (A) shares common attributes, while subclass entities (B and C) have specific attributes. Example: Person (A) can be an Employee (B) or a Customer (C).

                         (a1)      (a2)
                           \       /
                            \     /
                          +---------+
                          |    A    |  <-- Superclass
                          +---------+
                               |
                              / \
                            / ISA \
                            -------
                             /   \
                           /       \
                 +---------+       +---------+
                 |    B    |       |    C    |  <-- Subclasses
                 +---------+       +---------+
                    /                 \
                  (b1)                (c1)

Rules: The most standard and flexible way to map this (cross-platform) is to create a table for the superclass and separate tables for each subclass. The subclass tables inherit the primary key of the superclass.

Here, three tables will be required:

 

1. A ( a1 , a2 )

2. B ( a1 , b1 ) (Note: 'a1' is both the Primary Key and a Foreign Key referencing A)

3. C ( a1 , c1 ) (Note: 'a1' is both the Primary Key and a Foreign Key referencing A)

Case-17: Derived Attribute

An attribute whose value is not stored physically but is calculated dynamically from other attributes. Represented by a dashed/dotted oval. Example: Age (a3) can be derived from Date_of_Birth (a2).

                         . . . . .
                       .           .
                     .      a3       .  <-- Derived (e.g., Age)
                       .           .
                         . . . . .
                             |
       (a1)      (a2)        |
         \       /           |
          \     /            |
        +--------------------+
        |         A          |
        +--------------------+

Rules: Derived attributes are never mapped to a physical column in a relational database table. They are calculated on the fly using SQL queries or application logic.

Here, one table will be required:

 

1. A ( a1 , a2 ) (Notice that 'a3' is completely ignored in the schema)

 

Case-18: Aggregation

Aggregation occurs when a relationship itself is treated as an entity so that it can participate in another relationship. Example: An Employee (A) working on a Project (B) creates a Works_On (R1) relationship. A Manager (C) then manages (R2) that specific Employee-Project combination.

 

      +-----------------------------------------+
      |      (a1)                 (b1)          |
      |        \                    /           |
      |      +---+      +----+    +---+         |
      |      | A |------| R1 |----| B |         |
      |      +---+      +----+    +---+         |
      +-------------------|---------------------+
                          |
                        +----+
                        | R2 |
                        +----+
                          |
                        +---+
                        | C |
                        +---+
                          |
                        (c1)

Rules: You map the inside relationship (R1) normally. Then, for the outside relationship (R2), you combine the primary keys of everything involved in R1 along with the primary key of the new entity (C).

Here, five tables will be required (assuming m:n everywhere for worst-case):

 

1. A ( a1 )

2. B ( b1 )

3. C ( c1 )

4. R1 ( a1 , b1 )

5. R2 ( a1 , b1 , c1 ) (a1 and b1 act as a composite foreign key referencing R1)

Case-19: Unary (Recursive) Relationship (1:1)

An entity relates to itself in a strict one-to-one manner. Example: A Person (A) is married to exactly one other Person (A).

 

       (a1)      (a2)
         \       /
          \     /
        +---------+    1    +---+
        |    A    |---------| R |
        +---------+         +---+
             |                |
             |_______ 1 ______|

Rules: Similar to a 1:m unary relationship, this requires only one table. However, the foreign key column that references the table's own primary key must have a UNIQUE constraint to enforce the 1:1 rule.

Here, one table will be required:

 

1. A ( a1 , a2 , Spouse_a1 ) (Spouse_a1 is a UNIQUE foreign key referencing a1)

Case-20: Composite Multivalued Attribute

An attribute that is both multivalued (many exist) AND composite (made of sub-parts). Example: A user has multiple Addresses (a2), and each Address is broken into City (a21) and Pincode (a22).

                       (a21)   (a22)
                         \       /
                          \     /
                        +=========+
                       //   a2    \\  <-- Multivalued & Composite
                      //           \\
                     +===============+
                             |
       (a1)                  |
         \                   |
          \                  |
        +--------------------+
        |         A          |
        +--------------------+

Rules: Combine the rules for multivalued and composite attributes. Extract it into a new table, but only create columns for the simple component parts (a21, a22), omitting the main category name (a2).

Here, two tables will be required:

 

1. A ( a1 )

2. A_Address ( a1 , a21 , a22 ) (All three form a composite primary key)

Answer 1

We need a separate table for many-to-many relation.
one-to-many relation doesn't need a separate table and can be handled using a foreign key.
So, answer is $B$ - $3$ tables.

Reference: MIT notes.

Comments

@arjun sir the link shows “Page not found”.

---

@arjun

according to this source there should be 3 tables (E1, R1, E2) and the 4^th table would be R2. Reasoning for having 3 separate tables for 1:m relation below:

https://www.cs.uct.ac.za/mit_notes/database/htmls/chp06.html#optional-for-both-entities

               1      R1     m

E1                                            E2

               m      R2     n

Please imagine the lines and boxes above

In 1:m relation, because it hasn’t been specified if participation of E2 in R1 is total, we have to ideally assume it to be optional.

And because it is optional, the foreign key of some tuples (if E1 and R2 is combined) will remain null. (check it out with making an example where relation is 1:m and participation is optional).

And generally, we don’t want null values in our tables, therefore we should make 3 tables E1, R1 and E2 instead of just 2 by merging R1 and E2 (sorry for not providing any standard text supporting this null value argument, but if you google you will surely find, and also i remember hearing this in the nptel lecture series of dbms of iit kharagpur Prof. Partha Pratim Chakrabarti)

 

---

@Deepak Poonia sir with merging table of many side and relation, don't we have null value problem for one to many relation 
So when asked for minimum table is good design and normal form secondary??

Answer 2

Minimum no. of table required:

Relationship Type	Participation	# of Tables
1-1	Both Side Partial	2
1-1	1: Partial  1: Full	1
1-m	Both Side Partial	2
1-m	1: Full       m: Partial	1
1-m	1: Partial  m: Full	2
m-m	Both Side Partial	3
m-m	m: Partial m: Full	3
m-m	Both Side Full	3

m-1 relationship behave like 1-m . 

 

This question belongs to the 2 categories:

---

R1 :- it's 1-m(Both side Partial) relationship which need 2 tables 1 table foe E1 and other for E2(combine with R1 ) 

R2:- it's m-m(Both side Partial) relationship which need 3 tables 1 table for E1 , 1 table for R2 & 1 table for E2 . but E1 and E2 is already counted so, only remaining R2 is required .

Min. no. of table :- E1,E2,R2 = 3

Comments

m-m

Both Side Full

3

 

If both sides have total participation, that means each entity from each side is participating in relationship. Why can't we just merge this both tables into one and make both entities primary key as composite primary key for this table? 

---

may i know how did u arrive with this(In mit notes is saying 3),even if i null is okay ...need minimum 2 tables only

how 1?

---

yeah i also think that min 1 table in case of m-n and both side total participation. cuz there won't be any null value and composite primary key can be defined. whats wrong in that?

 

Answer 3

Answer is 3 tables

Comments

3 Table are

1. E1

2.E2

3..R2

---

@VIDYADHAR SHELKE 1

Let E1 has attributes (a , b)  and E2 has (c , d)

So tables will be, for relationship R1 i.e. 1 to m. T1(a , b) and T2(c , d , a).

For relationship R2 i.e. m to n.

We need one extra  table T3(a , c).

So total 3 table required.

Answer 4

Refer : https://gateoverflow.in/?qa=blob&qa_blobid=6323062077382268334

Answer 5

Here the E1 and E2 when connected by R1 needs only two table because it can be easily solved by using concept of foreign key.

When we are connected the same E1 and E2 (E2 having a foreign key through E1), we need a third table which will help in identifying the many-many relationship between E1 and E2 through R2

Answer 6

Answer option B