Self-checkedTier 1 10 min readdbms.er-model

ER model

The entity-relationship model: entities and entity sets, attribute kinds (simple, composite, multivalued, derived, key), relationship sets and their degree, cardinality ratios (1:1, 1:N, M:N) and participation (total or partial), keys of relationship sets, weak entity sets with identifying relationships and partial keys, specialisation and generalisation (ISA) with disjointness and totality, and counting the relationship sets allowed by a cardinality constraint.

Why it exists

Before tables there is a design question: what are the things the database must describe, and how are they connected? The entity-relationship (ER) model answers it with a diagram: rectangles for kinds of things, diamonds for how they are related, ellipses for their properties. The diagram is then turned into relations mechanically (ER to relational mapping). GATE asks: read an ER diagram, decide cardinalities and keys, count the tables, decide whether a relationship is possible.

Prerequisites

None.

Precise definitions

Entity: a distinguishable object (a student, a course). Entity set: all entities of the same kind, with the same attributes. Drawn as a rectangle.
Attribute: a property of an entity (or of a relationship). Kinds:
- simple (atomic) or composite (made of parts, such as address = street + city);
- single-valued or multivalued (a set of values: several phone numbers; double ellipse);
- derived (computed from others: age from date of birth; dashed ellipse);
- key attribute: values identify the entity within its entity set (underlined).
Relationship: an association among entities; a relationship set is the set of all associations of one kind. Drawn as a diamond. Its degree is the number of participating entity sets (binary, ternary, ...). A relationship set may have attributes of its own (the grade of an enrolment). A role name distinguishes the two occurrences when an entity set takes part twice (recursive relationship, e.g. manager and employee in Supervises).
Cardinality ratio of a binary relationship set between $A$ $A$ and $B$ $B$ :
- one-to-one (1:1): an entity of $A$ is related to at most one entity of $B$ and vice versa;
- one-to-many (1:N): an entity of $A$ may be related to many entities of $B$ , but an entity of $B$ to at most one of $A$ ;
- many-to-one (N:1): the mirror image;
- many-to-many (M:N): no restriction.
Participation: total (every entity of the set takes part in at least one relationship; double line) or partial (some may not).
Weak entity set: an entity set that has no key of its own. Its entities are identified by a partial key (discriminator) together with the key of the owner (identifying) entity set, through an identifying relationship (double diamond). A weak entity set always participates totally in the identifying relationship, which is one-to-many from owner to weak entities. Drawn as a double rectangle; the partial key is underlined with a dashed line.
Specialisation / generalisation (ISA): a subclass inherits all attributes and relationships of its superclass and may add its own. Constraints: disjoint or overlapping (an entity in at most one subclass, or possibly several); total or partial (every superclass entity belongs to some subclass, or not).
Aggregation treats a relationship set as an entity set so that it can take part in another relationship (quoted).

How it works

Reading a diagram

A small university:

An ER diagram of a university: start

Rectangle = entity set (double = weak), diamond = relationship set (double = identifying), ellipse = attribute (underlined = key, dashed underline = partial key, dashed outline = derived, double outline = multivalued). Double line = total participation. The letters beside a line give the cardinality.

Step 0

Entity sets are rectangles: Student, Course and Instructor. An entity is an object that can be told apart from others; an entity set is the collection of all entities of the same kind.

0 / 3

Read each line as a sentence. Student and Course are related by Enrolls with M on the Student side and N on the Course side: a student takes many courses and a course has many students. Instructor and Course are related by Teaches with 1 on the Instructor side and N on the Course side: an instructor teaches many courses, a course has one instructor; the double line to Course means every course has an instructor.

Which side carries the 1? In the notation used here the letter written next to an entity set tells how many entities of THAT set can be related to one entity of the other set. "1" next to Instructor means: at most one instructor per course. Some books (and the "look-here" convention with $(\min, \max)$ pairs) put the numbers on the other end of the line. In any exam question restate the constraint in words before deciding.

Keys of a relationship set

A relationship instance is a pair $(a, b)$ of entities; as a tuple it consists of the keys of the participants (plus attributes of the relationship). Which attributes identify an instance?

relationship set	candidate key of the relationship set
M:N	key of $A$ together with key of $B$
1:N (each $b$ related to at most one $a$ )	key of $B$ (the "many" side)
N:1 (each $a$ related to at most one $b$ )	key of $A$
1:1	key of $A$ or key of $B$ (either)

The reason: if each $b$ is related to at most one $a$ , then $b$ alone determines the pair. This was checked by listing all relationship sets over three entities on each side: for every one-to-many set the key of the many side identifies each pair, while the key of the one side alone fails for some of them.

How many relationship sets does a constraint allow

A relationship set between $A$ with $m$ entities and $B$ with $n$ entities is a subset of the $mn$ pairs. The number of subsets that respect a cardinality constraint is:

constraint	count	reason
M:N	$2^{mn}$	any subset of the pairs
each $b$ related to at most one $a$	$(m + 1)^n$	every $b$ chooses one of the $m$ entities or none
each $a$ related to at most one $b$	$(n + 1)^m$	symmetric
1:1	$\sum_{k} \binom{m}{k} \binom{n}{k} k!$	choose $k$ entities on each side and match them (a partial injection)

How many relationship sets satisfy a cardinality constraint: start

Computed by a script, not typed

entity sets	M:N	1:N (each b related to at most one a)	N:1 (each a related to at most one b)	1:1
\|A\| = 2, \|B\| = 2
\|A\| = 2, \|B\| = 3
\|A\| = 3, \|B\| = 3
\|A\| = 3, \|B\| = 4

Step 0

A relationship set is a set of pairs (a, b). 1:N means every b is related to at most one a (the 'one' is A), and so on. The numbers are found by checking every subset of A × B.

0 / 4

computed by script: relational operators are evaluated by scripts/db_lib.py (and cross-checked against SQLite), one step at a time. python3 scripts/gen-db1-traces.py

With total participation of $B$ in the one-to-many case every $b$ must choose exactly one $a$ : $m^n$ possibilities ( $3^3 = 27$ for $m = n = 3$ ). With total participation on both sides of a one-to-one relationship the sets are exactly the bijections: $n!$ when $m = n$ ( $3! = 6$ ). These numbers were obtained by listing all subsets of pairs and agree with the formulas for sizes up to $3 \times 4$ .

Weak entity sets

A weak entity set: start

Step 0

Employee is an ordinary (strong) entity set with the key eid.

0 / 2

A dependent (a child, a spouse) is identified only through the employee: two employees can each have a dependent called "Mina". The full key of Dependent is the owner key together with the partial key: $(\text{eid}, \text{dname})$ . Deleting an employee deletes the dependents with it.

Specialisation

Specialisation (ISA): start

Step 0

Person is the superclass with attributes pid (key) and name.

0 / 2

Person is specialised into Student and Employee. A subclass has the key of the superclass, so students are identified by pid. Constraints are chosen from the application: total if every person is a student or an employee, overlapping if somebody can be both.

What the model cannot say (quoted)

A ternary relationship (for example, supplier supplies part to project) cannot always be replaced by three binary relationships without losing information: the three binary relationships do not tell which supplier supplies which part to which project. And an ER diagram does not state every constraint: functional dependencies and domain constraints are written separately.

Worked examples

EX 1Identify the elements

Easy

In the university diagram: entity sets Student, Course, Instructor; relationship sets Enrolls (with attribute grade), Teaches; key attributes sid, cid, iid; multivalued attribute phone; the relationship Teaches is one-to-many from Instructor to Course with total participation of Course.

EX 2Key of a relationship set

Easy

$\text{Enrolls}$ (M:N) has the key $(\text{sid}, \text{cid})$ : a student can take many courses and a course has many students, so neither key alone identifies an enrolment. $\text{Teaches}$ (Instructor $1$ , Course $N$ ) has the key cid: each course appears with exactly one instructor.

EX 3Counting relationship sets

Medium

$|A| = 3$ doctors, $|B| = 4$ patients; each patient has at most one doctor: $(3 + 1)^4 = 256$ relationship sets (found by enumeration of the $2^{12}$ subsets). If every patient must have a doctor: $3^4 = 81$ . For a one-to-one relationship between $2$ and $3$ entities: $\sum_k \binom{2}{k}\binom{3}{k}k! = 1 + 6 + 6 = 13$ (the table lists $13$ ).

EX 4Is the weak entity set needed

Medium

Rooms in buildings: room numbers 101, 102 repeat in different buildings, so Room has only a partial key (room number); the key of a room is (building number, room number). Room is a weak entity set with the identifying relationship "Inside" to Building. A student id, on the other hand, is unique university-wide and needs no owner.

EX 5Typical questions

GATE level

(a) "An entity in $A$ can be related to many entities in $B$ and vice versa: the cardinality is" M:N. (b) "Which attributes form the key of a many-to-many relationship set without attributes of its own?" The union of the keys of the participants. (c) "A weak entity set has total participation in its identifying relationship." True. (d) "The primary key of a weak entity set in the relational schema is:" owner key plus partial key. (e) "Total participation of an entity set means:" every entity of the set takes part in at least one relationship instance. (f) "If specialisation is overlapping, an entity of the superclass:" may belong to more than one subclass.

Cheat box

Rectangle entity, double rectangle weak entity, diamond relationship, double diamond identifying relationship, ellipse attribute (underline key, dashed underline partial key, double ellipse multivalued, dashed ellipse derived).
Cardinality 1:1, 1:N, N:1, M:N; participation total (double line) or partial.
Key of a relationship set: M:N both keys; 1:N the key of the many side; 1:1 either key.
Weak entity key = owner key + partial key; always total in the identifying relationship.
Number of relationship sets between $m$ and $n$ entities: $2^{mn}$ (M:N), $(m+1)^n$ and $(n+1)^m$ , partial injections for 1:1.

Traps and GATE patterns

Connections

Builds on

No prerequisites.

Unlocks

ER to relational mappingPrerequisite of ER to relational mappinguses Relational model and keysuses

Across subjects

No cross-subject links yet.

Within this subject

ER to relational mappingimplemented-by Relational model and keysimplemented-by

Every ER diagram has a standard translation to relations (ER to relational mapping); the keys of the relational model are the keys chosen here (relational model and keys).

PYQs

6 previous year questions from your book. I re-solved each one myself (0 by running or simulating, 6 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2024 · Set 2 · MCQ · 1 markQ1 · page 384 of the book

In the context of owner and weak entity sets in the ER
(Entity-Relationship) data model, which one of the
following statements is TRUE?

(a)The weak entity set MUST have total participation in the identifying relationship
(b)The owner entity set MUST have total participation in the identifying relationship
(c)Both weak and owner entity sets MUST have total participation in the identifying relationship
(d)Neither weak entity set nor owner entity set MUST have total participation in the identifying relationship

GATE 2024 · Set 2 · MCQ · 1 markQ2 · page 384 of the book

Let S be the specification: "Instructors teach courses.
Students register for courses. Courses are allocated
classrooms. Instructors guide students." Which one of
the following ER diagrams CORRECTLY represents S?

(a)(i)
(b)(ii)
(c)(iii)
(d)(iv)

GATE 2020 · MCQ · 1 markQ3 · page 384 of the book

Which one of the following is used to represent the
supporting many-one relationships of a weak entity set in
an entity-relationship diagram?

(a)Diamonds with double/bold border
(b)Rectangles with double/bold border
(c)Ovals with double/bold border
(d)Ovals that contain underlined identifiers

GATE 2018 · MCQ · 1 markQ4 · page 384 of the book

In an Entity-Relationship (ER) model, suppose R is a
many-to-one relationship from entity set E1 to entity set
E2. Assume that E1 and E2 participate totally in R and that
the cardinality of E1 is greater than the cardinality of E2.

Which one of the following is true about R?

(a)Every entity in E1 is associated with exactly one entity in E2
(b)Some entity in E1 is associated with more than one entity in E2
(c)Every entity in E2 is associated with exactly one entity in E1
(d)Every entity in E2 is associated with at most one entity in E1

GATE 2012 · MCQ · 1 markQ7 · page 385 of the book

Given the basic ER and relational models, which of the
following is INCORRECT?

(a)An attribute of an entity can have more than one value
(b)An attribute of an entity can be composite
(c)In a row of a relational table, an attribute can have more than one value
(d)In a row of a relational table, an attribute can have exactly one value or a NULL value

GATE 2005 · MCQ · 1 markQ11 · page 385 of the book

Consider the entities 'hotel room', and 'person' with a
many to many relationship 'lodging' as shown below:

If we wish to store information about the rent payment to
be made by person (s) occupying different hotel rooms,
then this information should appear as an attribute of ?

(a)Person
(b)Hotel Room
(c)Lodging
(d)None of these DATABASE MANAGEMENT SYSTEM

Self-check

Question 1

What is the key of a weak entity set?

Show answer

The key of its owner entity set together with its own partial key.

Question 2

A one-to-many relationship set from $A$ ( $m$ entities) to $B$ ( $n$ entities): how many relationship sets exist where every $b$ is related to exactly one $a$ ?

Show answer

$m^n$ : each of the $n$ entities of $B$ picks one of the $m$ entities of $A$ .

Question 3

Which attributes form the key of a relationship set that is many-to-many?

Show answer

The keys of both participating entity sets together.

Question 4

What do the double line and the double diamond mean?

Show answer

Double line: total participation. Double diamond: identifying relationship of a weak entity set.

Revision card

One-screen revision

Entities, attributes (key, multivalued, derived), relationships, cardinality and participation.
Relationship key: M:N both keys, 1:N the many side.
Weak entity: partial key + owner key; identifying relationship total.
ISA: disjoint or overlapping, total or partial.
Counting subsets of pairs: $2^{mn}$ , $(m+1)^n$ .

References

·Silberschatz, Korth, Sudarshan, Database System Concepts (7th edition), Chapter 6 (database design using the E-R model)
·Elmasri, Navathe, Fundamentals of Database Systems (7th edition), Chapter 3 (data modeling using the entity-relationship model)

Verification

scripts/enum-checks/db_algebra.py: the number of relationship sets over entity sets of sizes m and n that satisfy each cardinality constraint was found by listing all subsets of the m n possible pairs and equals 2^(mn) (many-to-many), (m+1)^n and (n+1)^m (one-to-many, many-to-one), the sum over k of C(m,k) C(n,k) k! (one-to-one), 3^3 and 3! with total participation, for sizes up to 3 by 4; for every one-to-many relationship set over 3 by 3 entities the key of the 'many' side alone identifies each pair while the key of the 'one' side alone does not always; the ER diagrams are descriptions of the example schemas (their structure is checked in tests/db-traces.test.ts: every edge joins existing nodes, the weak entity has exactly one identifying relationship and one partial key). The remarks on notation differences between textbooks and on ternary relationships are textbook knowledge, quoted. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and re-derived against the textbook definitions and the sample database. No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

ER to relational mapping