ER to relational mapping

Why it exists

An ER diagram is for people; a database stores relations. A fixed set of rules turns one into the other, so a question "how many tables does this diagram give" has a definite answer. GATE asks it constantly: count the relations, name the keys, say where the foreign key goes.

Prerequisites

You need the ER model with its keys and cardinalities (ER model) and the relational vocabulary of keys and foreign keys (relational model and keys).

Precise definitions

The mapping works element by element. For an ER schema with entity sets $E_i$ and relationship sets $R_j$:

1. Strong entity set $E$ with simple attributes $a_1, \ldots, a_n$ and key $k$: a relation $E(a_1, \ldots, a_n)$ with primary key $k$. A composite attribute is replaced by its simple components; a derived attribute is not stored.
2. Weak entity set $W$ with owner $E$ and partial key $p$: a relation $W(\text{key of } E, \text{ attributes of } W)$ with primary key $(\text{key of } E, p)$ and a foreign key (key of $E$) referencing $E$. The identifying relationship needs no relation of its own.
3. Multivalued attribute $m$ of $E$: a relation $E\_m(\text{key of } E, m)$ with primary key (key of $E$, $m$) and a foreign key referencing $E$.
4. Binary one-to-many relationship between $A$ (the "one" side) and $B$ (the "many" side): add the key of $A$ to the relation of $B$ as a foreign key (together with any attributes of the relationship). No new relation.
5. Binary many-to-many relationship: a new relation containing the keys of both participants (each a foreign key) and the attributes of the relationship; its primary key is the union of the two keys.
6. Binary one-to-one relationship: add the key of one side to the other as a foreign key (together with the relationship's attributes). Prefer the side with total participation, so that the foreign key is never NULL; if both sides are total the two entity sets may even be merged into one relation.
7. $n$-ary relationship ($n \ge 3$): a relation containing the keys of all participants; the primary key is the union of the keys of the "many" participants (all of them if all are many).
8. Specialisation: three mappings (below).

How it works

Worked mapping

Take the university diagram of the previous page extended with a weak entity set Dependent of Employee (ER model). Applying the rules one by one:

Result: seven relations. The numbers behind it: five entity sets (Student, Course, Instructor, Employee, and the weak Dependent) give five relations; the multivalued attribute phone gives one more; the many-to-many relationship Enrolls gives one more; the one-to-many Teaches and the identifying Has give none (they became the foreign keys iid in Course and eid in Dependent). So

$\text{number of relations} = \#\text{entity sets} + \#\text{multivalued attributes} + \#\text{M:N (and $n$-ary) relationship sets}$

(counting the weak entity sets among the entity sets and not counting the 1:N and 1:1 relationships, nor identifying relationships).

The mapping was implemented and tested: the schema it produced was loaded into a real database (SQLite) with the PRIMARY KEY and FOREIGN KEY clauses enforced; 100 random ER instances were converted to rows and loaded without a constraint error, and each relationship set was recovered by a query (for example Teaches is $\pi_{\text{iid}, \text{cid}}(\text{Course})$ and Has is $\pi_{\text{eid}, \text{dname}}(\text{Dependent})$). A duplicate key or a dangling foreign key was refused.

Why the foreign key goes to the "many" side

In a one-to-many relationship each course has at most one instructor, so the instructor can be stored in the course tuple as one extra value. The other way round (a list of courses inside the instructor tuple) would violate atomicity. Placing a foreign key on the "one" side is not possible without repeating the instructor's tuple for each course.

For a many-to-many relationship there is no tuple in which a single value can be stored, hence the extra relation.

Minimum number of relations

The standard answers above give the number of relations of the straightforward mapping. If a question asks for the minimum number of relations, merge where it loses nothing:

• a one-to-one relationship with total participation of both entity sets: the two entity sets can be merged into a single relation;
• a one-to-many relationship does not reduce the count (the foreign key already adds no relation);

Merging entities that are not in total one-to-one relationship would force NULLs.

Mapping a specialisation

Person(pid, name) with subclasses Student(gpa) and Employee(salary) (ER model). Three mappings:

The first mapping gives three relations for three entity sets; it is the answer the counting rule above produces when each subclass is counted as an entity set.

Roles and recursive relationships

For a recursive relationship such as Supervises on Employee (one supervisor, many supervisees): the relation Employee gets a foreign key referencing itself, with a new name (supervisor_eid). For a recursive many-to-many relationship (a course requires other courses) a relation with two copies of the key under different role names.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The relations produced here are the input of normalisation, which checks whether the design has redundancy (normal forms); they are created in SQL by CREATE TABLE (SQL basics).

PYQs

An ER model of a database consists of entity types A and
B. These are connected by a relationship R which does not
have its own attribute. Under which one of the following
conditions, can the relational table for R be merged with
that of A?

Consider an Entity-Relationship (ER) model in which
entity sets E1 and E2 are connected by an m:n
relationship R12. E1 and E3 are connected by a 1:n (1
on the side of E1 and n on the side of E3) relationship
R13.

E1 has two-singled attributes a11 and a12 of which a11
is the key attribute. E2 has two singled-valued attributes
a21 and a22 of which a21 is the key attribute. E3 has two
single-valued attributes a31 and a32 of which a31 is the
key attribute. The relationships do not have any
attributes.

If a relational model is derived from the above ER
model, then the minimum number of relations that would
be
generated
if
all
relation
are
in
3NF
is________________.

Consider the following ER diagram

Which of the following is a correct attribute set for one
of the tables for the minimum number of tables needed
to represent M, N, P, R1, R2 ?

Consider the following ER diagram

The minimum number of tables needed to represent
M, N, P, R1, R2 is

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

Self-check

Revision card

References