Mapping 1:1, 1:N, M:N with participation; minimum number of tables

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Where does a multivalued attribute go when mapping to tables, and what is the new table's PK? from Lesson 2.4.1
2. What is the difference between total and partial participation? from Lesson 1.2.2
3. What does entity integrity forbid? from Lesson 2.3.1

1 · The Hook

This is the most-asked ER question in GATE: "An ER diagram has entity sets E1 and E2 joined by relationship R, which is M:N / 1:N / 1:1 with these participations. What is the minimum number of tables?" The answer depends on one question: can the relationship be stored as a foreign key without breaking 1NF or creating a NULL key?

2 · Predict First

STUDENT and COURSE joined by ENROLLS, M:N. Can ENROLLS be stored as a column course_id inside STUDENT? Why or why not?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

No. A student takes many courses, so one course_id column per student cannot hold them all (cells are atomic). An M:N relationship always needs its own table ENROLL(roll, cid, …). Total: 3 tables.

Rule 4 · M:N relationship

New table with the PKs of both entities as foreign keys, plus the relationship's attributes. PK = both foreign keys together.

ENROLLS(STUDENT M : N COURSE, grade) → ENROLL(roll, cid, grade).

Rule 5 · 1:N relationship

Add the PK of the 1-side entity as a foreign key in the N-side table, plus the relationship's attributes. No new table.

OFFERS(DEPT 1 : N COURSE) → COURSE(cid, title, credits, dname), dname → DEPT.

• If the N side has total participation, declare the FK NOT NULL.
• If the N side has partial participation, the FK can be NULL for courses with no department. (Alternative: a separate table OFFERS(cid, dname); it avoids NULLs but costs a table. For "minimum tables", use the FK.)

Rule 6 · 1:1 relationship

Add the PK of one entity as a foreign key in the other; prefer the side with total participation (no NULLs). Declare the FK unique.

HEADS(FACULTY 1 : 1 DEPT, DEPT total) → DEPT(dname, building, head_fid), head_fid → FACULTY, unique, NOT NULL.

• Both sides total: the two entity types can be merged into one table (every entity of each has exactly one partner). Its PK is either entity's key.
• One side total: FK in the total side, 2 tables.
• Both partial: FK on either side (NULLs allowed), 2 tables.

Rule 7 · Recursive relationships

• Recursive 1:N or 1:1 (MENTORS, each student has at most one mentor): add an FK to the same table: STUDENT(roll, …, mentor_roll).
• Recursive M:N (a course has many prerequisites and is a prerequisite of many): new table PREREQ(cid, prereq_cid).

Minimum number of tables: the summary

Add: +1 per multivalued attribute, +1 per weak entity, +1 per M:N recursive relationship, +0 per 1:N/1:1 recursive relationship.

GATE convention: some questions assume a 1:N relationship with total participation on the 1 side and the N side still needs 2 tables (it does: entities on the N side are many per partner, so they cannot merge). Only 1:1 with both sides total collapses to one table.

4 · Visual

M:N   STUDENT --<ENROLLS>-- COURSE     STUDENT(roll ...)   COURSE(cid ...)   ENROLL(roll, cid, grade)   = 3
1:N   DEPT --<OFFERS>-- COURSE         DEPT(dname ...)     COURSE(cid ..., dname FK)                    = 2
1:1   FACULTY --<HEADS>== DEPT         FACULTY(fid ...)    DEPT(dname ..., head_fid FK unique)          = 2
1:1   both total (==)                  one merged table PERSON_PASSPORT(...)                            = 1

5 · Worked Examples

Example 1 Easy

E1(a key, b), E2(c key, d), R(E1 1 : N E2) with attribute r. Give the minimum relational schema.

Solution

2 tables: E1(a, b); E2(c, d, a, r) with a → E1.a. The relationship attribute r goes to the N side with the FK.

Example 2 Medium

E1 and E2 are joined by a 1:1 relationship R; E1 participates totally and E2 partially. Give the minimum tables and where the FK goes.

Solution

2 tables. Put E2's PK as a NOT NULL, unique FK in E1 (the total side), so it is never NULL.

Example 3 GATE

An ER diagram: E1 —R1— E2 —R2— E3, where R1 is M:N and R2 is 1:N (E2 on the 1 side). E3 has one multivalued attribute. All participations are partial. Minimum number of tables?

Solution

E1, E2, E3: 3. R1 (M:N): +1. R2 (1:N): FK in E3, +0. Multivalued: +1. Total 5.

8 · Connect the Dots

Lesson 2.4.1 mapped entities; this lesson mapped binary and recursive relationships and gave the minimum-tables table. Next: the remaining ER pieces: ternary relationships, specialisation hierarchies and aggregation.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Minimum tables

E1 and E2 joined by an M:N relationship, both participations total, no multivalued attributes. Minimum tables?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Minimum tables

E1 and E2 joined by a 1:1 relationship with total participation on both sides. Minimum tables?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — 1:N

In a 1:N relationship from DEPT to EMPLOYEE, the foreign key goes:

1. (A) in a new table only
2. (B) in EMPLOYEE, referencing DEPT
3. (C) in both tables
4. (D) in DEPT, referencing EMPLOYEE

Q4 · NAT · 2 mark(s) — Minimum tables

Entity sets A, B, C, D. A—R1—B is M:N, B—R2—C is 1:N, C—R3—D is 1:1 with both participations total, and A has one multivalued attribute. Minimum tables?

Numerical answer: ________

Q5 · MCQ · 2 mark(s) — Recursive

COURSE has a recursive M:N relationship PREREQUISITE. How many tables are needed for COURSE and PREREQUISITE together?

1. (A) 2
2. (B) 1
3. (C) 3
4. (D) 4

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

mapping M:N (separate table)mapping 1:N (FK on N side)mapping 1:1 (FK on total side, or merge)merging entity tablesrecursive relationship mappingminimum number of tables