Entity-Relationship Model: short notes (Database Management Systems)

Revision mode

Introduction

The entity-relationship (ER) model describes the data of an application before any table is designed. It says which things exist (entities), what is recorded about them (attributes) and how they are connected (relationships), together with the counting rules that the real world imposes: a student belongs to exactly one department, a course can have many sections, a section cannot exist without its course.

The ER model is a conceptual model. It has no tables, no foreign keys and no SQL; those appear only when the diagram is mapped to relations (see Mapping ER Diagrams to Relations). Its value is that every later design decision (which table holds which foreign key, which key is composite, whether a column may be NULL) can be read off the diagram's cardinality and participation constraints.

Working with an ER model comes down to reading the constraints on a diagram correctly, counting the minimum number of tables a diagram needs, and recognising weak entity sets and the keys of relationship sets.

Prerequisites

None within the syllabus. Familiarity with sets and ordered pairs helps, since a relationship set is a set of tuples of entities.

Core concepts

Term	Meaning
Entity	A distinguishable object: one student, one course.
Entity set (entity type)	The collection of entities of one kind, with the same attributes. Drawn as a rectangle.
Attribute	A property of an entity or relationship. Drawn as an oval (Chen style).
Domain	The set of allowed values of an attribute.
Key attribute	An attribute (or set) whose value is unique for every entity of the set. Underlined.
Relationship	An association among entities, for example "Asha enrols in section 2 of DBMS".
Relationship set	A set of relationships of one kind; mathematically a subset of $E_1 \times E_2 \times \cdots \times E_n$ . Drawn as a diamond.
Degree	The number $n$ of participating entity sets: binary ( $n = 2$ ), ternary ( $n = 3$ ).
Role	The function an entity plays in a relationship; needed when an entity set participates twice (recursive relationship).

Kinds of attributes

Simple versus composite. A composite attribute has parts, for example name with first and last. Drawn as an oval with child ovals.
Single-valued versus multivalued. A multivalued attribute can hold several values for one entity, for example phone. Drawn as a double oval.
Stored versus derived. A derived attribute is computed from others, for example age from dob. Drawn as a dashed oval and not stored.
NULL. An attribute may be NULL when the value does not apply or is unknown.

Notation convention. These notes draw Chen-style diagrams as in Elmasri and Navathe: rectangles for entity sets, ovals for attributes, diamonds for relationship sets, double rectangles and double diamonds for weak entity sets and their identifying relationships, double lines for total participation. Korth, Silberschatz and Sudarshan list attributes inside the entity rectangle instead and mark "one" with an arrowhead; the meaning of the constraints is the same.

Mapping cardinalities of a binary relationship

For a binary relationship set $R$ between entity sets $A$ and $B$ :

Ratio	Each $a \in A$ is related to	Each $b \in B$ is related to
One-to-one (1:1)	at most one $b$	at most one $a$
One-to-many (1:N), $A$ on the one side	any number of $b$	at most one $a$
Many-to-one (N:1)	at most one $b$	any number of $a$
Many-to-many (M:N)	any number of $b$	any number of $a$

Participation

Total participation of $A$ in $R$ : every entity of $A$ appears in at least one relationship of $R$ (an existence dependency). Double line.
Partial participation: some entities of $A$ may appear in no relationship. Single line.

Cardinality is an upper bound and participation is a lower bound. Together they form the (min, max) pair of each entity set in each relationship.

Weak entity sets

A weak entity set has no key of its own. Its entities are identified only through an identifying (owner) entity set and a partial key (discriminator) that distinguishes the weak entities belonging to one owner. Rules:

The identifying relationship is many-to-one from the weak set to the owner (each weak entity has exactly one owner).
The weak entity set participates totally in the identifying relationship.
The key of a weak entity set is (key of owner, partial key). The partial key is underlined with a dashed line.

Example: SECTION with partial key sec_no is weak, owned by COURSE. Section 1 of course CS301 and section 1 of course CS302 are different sections; sec_no alone is not unique, but (course_id, sec_no) is.

How it works: reading a diagram

ER diagram of a university: STUDENT with key roll_no, composite name, multivalued phone and derived age; DEPARTMENT; COURSE; weak entity SECTION owned by COURSE through HAS_SECTION; ENROLLS many-to-many between STUDENT and SECTION with attribute grade; BELONGS_TO many-to-one from STUDENT to DEPARTMENT with total participation of STUDENT; OFFERS many-to-one from COURSE to DEPARTMENT — Figure 1. A university ER diagram: four entity sets (one weak), four relationship sets, and the cardinality and participation marks on each line.

Read Figure 1 line by line:

STUDENT has key roll_no, composite name (first, last), multivalued phone, stored dob and derived age.
BELONGS_TO is N:1 from STUDENT to DEPARTMENT; the double line on the STUDENT side says every student belongs to a department. A department may have no student (single line).
OFFERS is N:1 from COURSE to DEPARTMENT, with total participation of COURSE.
HAS_SECTION is the identifying relationship of the weak set SECTION (partial key sec_no): 1:N from COURSE to SECTION, total on the SECTION side.
ENROLLS is M:N between STUDENT and SECTION and carries the attribute grade. The grade belongs to the pair (student, section), not to either entity alone.

Where a relationship attribute can live

An attribute of a 1:1 or 1:N relationship can be moved to an entity set: in a 1:N relationship it moves to the entity set on the N side (each such entity takes part in at most one relationship). In an M:N relationship it cannot move, because one student has many grades and one section has many grades. This is the ER-level reason why an M:N relationship always becomes its own table.

The (min, max) notation and its placement trap

Elmasri and Navathe also write a pair $(\min, \max)$ on the line between an entity set $E$ and a relationship $R$ : each entity of $E$ takes part in at least $\min$ and at most $\max$ relationships of $R$ . So $\min = 0$ means partial participation, $\min \geq 1$ means total participation.

Placement versus the 1:N labels. For BELONGS_TO the (min, max) pair next to STUDENT is (1, 1), because each student has exactly one department, and the pair next to DEPARTMENT is (0, N). The Chen ratio labels are written the other way round: "N" next to STUDENT and "1" next to DEPARTMENT. A ratio label says how many entities on that side can be associated with one entity on the other side; a (min, max) pair says how many relationships one entity on its own side takes part in. Mixing the two conventions reverses the cardinality.

Algorithms and pseudocode

Two counting procedures recur.

Key of a binary relationship set. Let $K_A$ and $K_B$ be the primary keys of $A$ and $B$ .

Text

RELATIONSHIP-KEY(R between A and B)
  if R is M:N then return K_A union K_B
  if R is N:1 from A to B then return K_A        // each a has at most one b
  if R is 1:N from A to B then return K_B
  if R is 1:1 then return K_A or K_B (either is a candidate key)

The rule follows from the definition: in an N:1 relationship from $A$ to $B$ , a given $a$ occurs in at most one pair, so $K_A$ alone identifies the pair.

Key of a ternary relationship set. Without cardinality constraints the key is the union of the three keys. If the relationship is "many" on two sides and "one" on the third (each pair $(a, b)$ determines at most one $c$ ), the key is $K_A \cup K_B$ .

Mathematical explanation

A binary relationship set is a relation $R \subseteq A \times B$ . With $|A| = m$ and $|B| = n$ :

M:N allows any subset, so $0 \leq |R| \leq m n$ , and there are $2^{mn}$ possible relationship sets.
N:1 from $A$ to $B$ is a partial function $A \to B$ : $|R| \leq m$ , and there are $(n + 1)^m$ possible relationship sets (each $a$ picks one of $n$ partners or none).
1:1 is a partial injection: $|R| \leq \min(m, n)$ .
Total participation of $A$ adds $|R| \geq m$ for N:1 (every $a$ appears, each at most once, so $|R| = m$ exactly) and $|R| \geq m$ in general for any ratio.

Total participation on both sides of a 1:1 relationship forces $m = n$ : each side needs at least as many partners as entities, and partners are unique.

Worked examples

Example 1: sizes of relationship sets. Let $|A| = 3$ and $|B| = 4$ .

M:N: at most $3 \times 4 = 12$ pairs; $2^{12} = 4096$ possible relationship sets.
N:1 from $A$ to $B$ : at most 3 pairs; $(4 + 1)^3 = 125$ possible sets.
1:N from $A$ to $B$ (each $b$ has at most one $a$ ): at most 4 pairs; $(3 + 1)^4 = 256$ possible sets.
1:1: at most $\min(3, 4) = 3$ pairs. Counting all partial injections from $A$ to $B$ gives $\sum_{k=0}^{3} \binom{3}{k} \binom{4}{k} k! = 1 + 12 + 36 + 24 = 73$ possible sets.
1:N from $A$ to $B$ with total participation of $B$ : exactly 4 pairs (every $b$ has exactly one $a$ ), $3^4 = 81$ possible sets.

Example 2: keys of the relationship sets of Figure 1.

Relationship	Ratio	Key of the relationship set
`BELONGS_TO`	N:1 from `STUDENT`	`roll_no`
`OFFERS`	N:1 from `COURSE`	`course_id`
`HAS_SECTION`	identifying, 1:N from `COURSE`	(`course_id`, `sec_no`)
`ENROLLS`	M:N	(`roll_no`, `course_id`, `sec_no`)

The key of ENROLLS has three attributes because the key of the weak set SECTION is itself (course_id, sec_no).

Example 3: a ternary relationship is not three binaries. SUPPLIES(supplier, part, project) records which supplier supplies which part to which project. Take the instance $\{(s_1, p_1, j_2), (s_1, p_2, j_1), (s_2, p_1, j_1)\}$ . Its three binary projections are $SP = \{(s_1, p_1), (s_1, p_2), (s_2, p_1)\}$ , $SJ = \{(s_1, j_2), (s_1, j_1), (s_2, j_1)\}$ and $PJ = \{(p_1, j_2), (p_2, j_1), (p_1, j_1)\}$ . Joining the three projections gives 4 triples, including $(s_1, p_1, j_1)$ , which never happened. So the ternary relationship carries information that the three binary relationships lose.

Example 4: is it weak? PAYMENT(installment_no, amount) of a LOAN(loan_no). Installment number 3 exists for every loan, so installment_no is not unique by itself. PAYMENT is weak with partial key installment_no, owner LOAN, key (loan_no, installment_no). If payments carried a globally unique payment_id, PAYMENT would be a strong entity set with a 1:N relationship to LOAN.

Important properties and observations

A weak entity set always has total participation in its identifying relationship; the converse is false. STUDENT participates totally in BELONGS_TO but is strong, because roll_no is a key.
The identifying relationship is never M:N from the weak side: one weak entity has exactly one owner.
A relationship set has no duplicate tuples. The same student cannot be enrolled twice in the same section through ENROLLS. To record repeated events (attempts, visits), represent a distinguishable event entity/role, possibly weak and identified by the participants plus an event discriminator; a relationship attribute alone does not distinguish duplicate participant tuples.
Recursive relationships need roles. SUPERVISES between EMPLOYEE and EMPLOYEE has roles supervisor and supervisee; a 1:N recursive relationship maps to one extra foreign key column in the same table.
Derived attributes are not stored; multivalued attributes cannot be stored in one column of a relation in first normal form, which is why they become separate tables.
Attribute or entity? If a property has its own properties or is shared by several entities (a department name with a building and budget), model it as an entity set.

Related material. The extended ER model adds specialisation and generalisation (superclass and subclass entity sets, disjoint or overlapping, total or partial) and aggregation (treating a relationship as an entity so it can take part in another relationship). They map to relations by the options listed in Mapping ER Diagrams to Relations.

Common misconceptions.

"Total participation means one-to-one." No: total participation is a minimum (at least one); the ratio is a maximum.
"The partial key is a key." No: it is unique only among the weak entities of one owner.
"A relationship attribute of a 1:N relationship must stay on the relationship." It may move to the N-side entity set.

GATE examination perspective

Constraint reading. Given an ER diagram with double lines, arrows or (min, max) pairs, state which entity is on the "one" side. Check which convention is used before reading the labels.
Minimum number of tables. This is a count after mapping; the deciding facts are M:N relationships, multivalued attributes and weak entity sets (worked in Mapping ER Diagrams to Relations).
Keys of relationship sets. M:N gives the union of keys; N:1 gives the key of the many side; weak entities contribute the owner key plus the partial key.
Counting instances. Maximum or minimum number of relationship instances from entity-set sizes and constraints, as in Example 1.
Ternary versus binary. Whether three binary relationships can replace a ternary one: in general no.

Summary

Entity sets are rectangles, attributes ovals, relationship sets diamonds; double rectangle and double diamond mark a weak entity set and its identifying relationship.
Attributes are simple or composite, single-valued or multivalued, stored or derived; keys are underlined, partial keys dashed-underlined.
Cardinality ratio (1:1, 1:N, M:N) is a maximum; participation (total or partial) is a minimum.
The (min, max) pair sits next to its own entity set, opposite to the Chen 1 and N labels.
Key of a relationship set: union of keys for M:N, the many-side key for N:1, either key for 1:1.
A weak entity set has key (owner key, partial key), an N:1 identifying relationship and total participation in it.
An attribute of a 1:N relationship can move to the N side; an M:N relationship attribute cannot.
A ternary relationship is in general not recoverable from its three binary projections.

Sources

A. Silberschatz, H. F. Korth, S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019 (2020 copyright), Chapter 6: 6.2 The Entity-Relationship Model, 6.3 Complex Attributes, 6.4 Mapping Cardinalities, 6.5 Primary Key, 6.8 Extended E-R Features.
R. Elmasri, S. B. Navathe, Fundamentals of Database Systems, 7th ed., Pearson, Chapter 3: 3.3 Entity Types, Entity Sets, Attributes, and Keys; 3.4 Relationship Types, Relationship Sets, Roles, and Structural Constraints; 3.5 Weak Entity Types; 3.9 Relationship Types of Degree Higher than Two.