Mapping ER Diagrams to Relations: short notes (Database Management Systems)

Revision mode

Introduction

An ER diagram becomes a relational schema by a short list of mechanical rules: one table per strong entity set, one per weak entity set, one per many-to-many relationship, one per multivalued attribute, and foreign keys for everything else. The rules are mechanical, but the choices they leave open (which side of a one-to-one relationship gets the foreign key, whether two tables can be merged) decide how many tables the design needs and where NULLs can appear.

The two quantities to find are the minimum number of tables that a diagram needs and the primary key of a particular table. Both answers follow from the cardinality and participation constraints, so each rule is derived from those constraints instead of being listed as a fact to memorise.

Prerequisites

Entity-Relationship Model: entity sets, attribute kinds, cardinality ratios, participation and weak entity sets.
Relational Model and Keys: candidate key, primary key, foreign key and the meaning of NOT NULL.

Core concepts

Convention. A table is written NAME(attributes) with the primary key underlined in prose as "key (...)". "FK x to T" means column $x$ references the primary key of table $T$ . "Minimum number of tables" means the smallest schema that stores every legal instance of the diagram without losing information, where NULL is allowed in a foreign key column only if the question allows it; a request for the minimum is read as permission to merge a relationship into the table of a participating entity set, NULLs included, unless the question rules it out. An entity-keyed merged table must retain a non-NULL primary key belonging to one side: permit a 1:1 merge if at least one side is total, using the other (possibly partial) side's key when exactly one side is total; keep both-partial entity sets separate under this convention.

ER construct	Relational mapping	Primary key
Strong entity set $E$	Table $E$ with all simple attributes; a composite attribute contributes its leaf components; derived attributes are dropped	Key of $E$
Multivalued attribute $m$ of $E$	New table $E\_M(K_E, m)$ , FK $K_E$ to $E$	$(K_E, m)$
Weak entity set $W$ with owner $O$	Table $W(K_O, \text{partial key}, \ldots)$ , FK $K_O$ to $O$ , usually ON DELETE CASCADE; the identifying relationship gets no table	$(K_O, \text{partial key})$
Binary M:N relationship $R$ between $A$ , $B$	Table $R(K_A, K_B, \text{attributes of } R)$ , two FKs	$(K_A, K_B)$
Binary 1:N relationship, $A$ on the one side	Add $K_A$ and the attributes of $R$ to the table of $B$ (FK); no new table	unchanged
Binary 1:1 relationship	Add one side's key as a complete-tuple UNIQUE foreign key on the other, preferably total-participating, side; require NOT NULL when that side is total. On merging, preserve both entity keys as candidate keys when total-total	unchanged
$n$ -ary relationship	Table with the keys of all participants and the relationship's attributes	Union of keys, reduced when one participant is functionally determined by the others
Recursive relationship on $E$	Same rules, with two copies of $K_E$ renamed by role	as above

How it works: the university example

Applying the rules to the university diagram of Entity-Relationship Model (Figure 1 there) gives six tables:

Six relation schemas from the university ER diagram: DEPARTMENT, STUDENT with foreign key dept_id, STUDENT_PHONE, COURSE with foreign key dept_id, SECTION keyed by course_id and sec_no, and ENROLLS keyed by roll_no, course_id and sec_no, with arrows for every foreign key — Figure 1. The university ER diagram mapped to six tables; each arrow is a foreign key and each key is the one derived from the cardinality constraints.

Table	Columns	Key	Comes from
DEPARTMENT	dept_id, dname	(dept_id)	strong entity set
STUDENT	roll_no, first, last, dob, dept_id	(roll_no)	strong entity set, composite `name` flattened, derived `age` dropped, N:1 `BELONGS_TO` folded in
STUDENT_PHONE	roll_no, phone	(roll_no, phone)	multivalued attribute
COURSE	course_id, title, dept_id	(course_id)	strong entity set, N:1 `OFFERS` folded in
SECTION	course_id, sec_no	(course_id, sec_no)	weak entity set, identifying `HAS_SECTION` absorbed
ENROLLS	roll_no, course_id, sec_no, grade	(roll_no, course_id, sec_no)	M:N relationship with its attribute

STUDENT.dept_id is declared NOT NULL because STUDENT participates totally in BELONGS_TO; total participation of the many side becomes a NOT NULL foreign key. Participation of the one side (every department has a student) cannot be expressed by a foreign key at all; it would need a CHECK across tables or an assertion.

Algorithms and pseudocode

Text

MAP-ER(D)
  for each strong entity set E: create table E(simple and leaf attributes); key K_E
  for each weak entity set W with owner O: create table W(K_O, partial key, attributes);
      key (K_O, partial key); FK K_O -> O on delete cascade
  for each multivalued attribute m of E: create table E_M(K_E, m); key (K_E, m); foreign key K_E -> E(K_E)
  for each binary relationship R between A and B:
      if R is M:N then create table R(K_A, K_B, attrs(R)); key (K_A, K_B)
      else if R is N:1 from A to B then add K_B and attrs(R) to table A as FK
           (NOT NULL if A participates totally)
      else if R is 1:1 then add the key of one side to the other side,
           choosing the total-participating side if one exists; declare the complete FK tuple UNIQUE
           and NOT NULL if that side is total; total-total merge preserves both candidate keys
  for each n-ary relationship R (n >= 3): create table R(all participant keys, attrs(R))

Each loop is linear in the size of the diagram. The decision that matters is which relationships need their own table.

Mathematical explanation

Why can an N:1 relationship from $A$ to $B$ be folded into $A$ ? In every legal instance, each $a$ has at most one partner $b$ . So "partner of $a$ " is a partial function of $a$ and fits in one column of $a$ 's row, NULL when $a$ has no partner. An M:N relationship gives some $a$ several partners, so no single column holds them: a separate table is forced.

A total-total 1:1 relationship is a bijection: one merged row stores each paired entity with both keys non-NULL and UNIQUE. With exactly one total side $A$ , every $A$ has one $B$ partner, but some $B$ entities may be unmatched. Key the merged table by $K_B$ ; unmatched $B$ rows have NULL in the $A$ columns. The non-NULL $K_A$ values remain UNIQUE. This is a one-table mapping when the stated NULL permission applies. If both sides are partial, neither entity key covers every stored entity without NULL; under the entity-keyed convention use two entity tables and a nullable UNIQUE foreign key, not a merged table with a nullable primary key. If NULLs are disallowed, use an appropriate separate relationship table instead of assuming the folded counts.

The minimum table counts for one binary relationship between two strong entity sets without multivalued attributes are therefore:

Relationship	Participation	Minimum tables
M:N	any	3
1:N or N:1	any	2
1:1	both sides partial	2
1:1	exactly one side total, nullable merge permitted	1
1:1	both sides total	1

Worked examples

Example 1: count the tables. E1 (key a1) and E2 (key b1) are related by R1, M:N. E2 and E3 (key c1, multivalued attribute m) are related by R2, 1:1 with total participation on both sides. E1 and E3 are related by R3, 1:N with E1 on the one side.

R1 is M:N: tables E1, R1(a1, b1).
R2 is 1:1 total on both sides: E2 and E3 merge into one table E23(b1, c1, ...).
R3 is 1:N: a1 goes into the merged table as a foreign key.
m is multivalued: table E3_M(c1, m).

Minimum: 4 tables (E1, R1, E23, E3_M). Primary key of R1: (a1, b1). Primary key of E3_M: (c1, m).

Example 2: NULLs when folding a partial relationship. Ten students, seven of whom have a mentor (N:1 MENTORED_BY to FACULTY, partial participation of STUDENT). Folding the relationship into STUDENT as mentor_id gives 10 rows of which 3 have mentor_id NULL. A separate table MENTORED_BY(roll_no, fac_id) would hold 7 rows and no NULL, at the cost of one more table and one more join. Both are correct; the folded version is what "minimum number of tables" counts.

Example 3: recursive 1:N. SUPERVISES on EMPLOYEE (one supervisor, many supervisees). Fold it into EMPLOYEE(emp_id, name, super_id) with FK super_id to EMPLOYEE: still 1 table. If SUPERVISES were M:N (matrix organisation), a second table SUPERVISES(super_id, sub_id) with key (super_id, sub_id) would be needed: 2 tables.

Example 4: key of a ternary table. TEACHES(instructor, course, semester). With no constraint the key is all three. If each (course, semester) pair has exactly one instructor, then (course, semester) determines instructor and the key shrinks to (course, semester).

Example 5: weak entity cascade. With SECTION(course_id, sec_no) referencing COURSE ON DELETE CASCADE and ENROLLS referencing SECTION ON DELETE CASCADE, deleting one course with 2 sections and 5 enrolments in those sections removes 1 + 2 + 5 = 8 rows in total. Without CASCADE the delete of the course is rejected while a section refers to it.

Important properties and observations

Key of a relationship table. M:N gives $(K_A, K_B)$ . If a relationship table is created for a 1:N relationship anyway (some designers do this to avoid NULLs), its key is the key of the N side alone.
Weak entity key. Always the owner's key plus the partial key; the owner key is also a foreign key.
Total participation of the many side becomes NOT NULL on the foreign key. Total participation of the one side has no foreign-key encoding.
Composite attributes become their leaf components; the composite name itself is not a column.
Merging is optional. "Minimum number of tables" counts merges; "number of tables by the standard algorithm" does not merge 1:1 relationships. Read the question.
Multivalued attributes of a relationship also become separate tables keyed by the relationship's key plus the value.

Related material. EER mappings include superclass and subclass tables, with subclass keys referencing the superclass; subclass-only tables, requiring total specialization; and a single table with nullable subclass-specific attributes. Disjointness avoids duplicated superclass values in subclass-only tables. With overlapping subclasses, an entity may occur in multiple subclass tables, requiring consistent copies of its superclass values. A single discriminator column assumes disjoint subclasses; overlap instead needs membership flags or an equivalent multi-membership encoding.

Common misconceptions.

"Every relationship becomes a table." Only M:N and $n$ -ary relationships (and multivalued attributes, weak entity sets) need their own; 1:1 and 1:N fold into an entity table.
"1:1 always means one table." Under this nullable-merge convention, at least one side must be total; both-partial uses two entity tables.
"The partial key is the key of the weak table." The key is the owner key plus the partial key.

GATE examination perspective

Minimum tables. Count strong entity sets, add one per weak entity set, one per M:N or $n$ -ary relationship and one per multivalued attribute, then subtract one for each permitted entity-keyed 1:1 merge (at least one total side, nullable partner columns allowed when only one side is total). Respect other relationships and keys when combining multiple merges.
Key of the relationship table. For binary 1:N and M:N relationships, read the cardinality: the "many" sides form the key. For 1:1 and n-ary relationships, apply the earlier candidate-key/FD rule instead.
Where the foreign key goes in a 1:N relationship. On the N side, never on the 1 side.
NOT NULL and participation. Which constraint enforces total participation: NOT NULL on the foreign key of the many side.
Referential actions on weak entities. Deleting an owner cascades to the weak entities when the foreign key says ON DELETE CASCADE (see Integrity Constraints).

Summary

Strong entity set: one table, leaf attributes only, derived attributes dropped.
Multivalued attribute: separate table keyed by (entity key, value).
Weak entity set: table keyed by (owner key, partial key); the identifying relationship disappears.
M:N relationship: separate table keyed by the union of the participating keys.
1:N relationship: foreign key on the N side, NOT NULL if that side is total.
1:1 relationship: foreign key on either side (prefer the total side); merge if both sides are total, or if exactly one side is total and nullable partner columns are permitted; keep both-partial entity sets separate.
$n$ -ary relationship: separate table; its key shrinks when cardinality constraints make one key determined by the others.
Minimum tables for one binary relationship: 3 for M:N, 2 for 1:N, 2 for both-partial 1:1, 1 for total-total or exactly-one-total 1:1 under the stated nullable-merge convention.

Sources

A. Silberschatz, H. F. Korth, S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019 (2020 copyright), 6.7 Reducing E-R Diagrams to Relational Schemas.
R. Elmasri, S. B. Navathe, Fundamentals of Database Systems, 7th ed., Pearson, 9.1 Relational Database Design Using ER-to-Relational Mapping; 9.2 Mapping EER Model Constructs to Relations.