ER relationships: cardinality and participation

A relationship is an association between entities, such as a student enrolling in a course, and all the associations of one kind form a relationship set, which Chen notation draws as a diamond. Two independent constraints describe how entities take part in it. The cardinality ratio sets the maximum: with how many entities on the other side one entity can be associated, written 1:1, 1:N or M:N. Participation sets the minimum: it is total when every entity of a set must take part, and partial when some may stay out. Both come straight from the wording of the requirements. This lesson models binary, recursive and ternary relationships with their roles and attributes, reads both constraints from a brief, converts between the (min,max) notation and crow’s foot without reversing their meaning, the easiest mistake to make in this topic, and shows with a run why a ternary relationship cannot always be split into three binary ones.

Relationship sets, degree and roles

In Chen’s paper a relationship set is a mathematical relation: every relationship in it is a tuple of entities, one taken from each of the entity sets involved. Those entity sets need not be different. The paper’s own example is a marriage between two entities of the set PERSON, where the roles husband and wife say which part each entity plays. The number of entity sets involved is the relationship’s degree:

• recursive (or unary): one entity set takes part twice, in two roles, as when a staff member reports to another;
• binary: two entity sets, as when a student enrols in a course; most relationships are of this kind;
• ternary and higher (n-ary): three or more, as when a supplier supplies a part to a project.

A relationship can have attributes of its own. A grade describes one student in one course, so it belongs to neither STUDENT nor COURSE but to their ENROLS relationship. Chen’s example was the share of an employee’s time given to a project: it depends on the employee and the project together.

Cardinality ratio: 1:1, 1:N and M:N

The ratio of a binary relationship comes from two questions, one for each direction: “one A is associated with at most how many B?” and “one B is associated with at most how many A?”. Each answer is either one or many, and the pair of answers is the ratio.

• WORKS_IN (instructor, department): an instructor has at most one department, a department many instructors, so instructor to department is N:1.
• HEADS (instructor, department): an instructor heads at most one department, and a department has one head: 1:1.
• ENROLS (student, course): a student takes many courses, and a course has many students: M:N.
• ADVISES (instructor, student): an instructor advises many students, and a student has one adviser: 1:N.
• REQUIRES (course, prerequisite): a course can need many prerequisites, and a course can be the prerequisite of many others: M:N.

The ratio belongs to the brief, not to the nouns. In another college a student might have two advisers, and ADVISES would become M:N; the diagram has to follow the requirement you were given. Chen notation writes the ratio on the two lines of the diamond, and M:N uses two letters to say that the two counts are independent.

Participation: total or partial

Participation asks whether an entity can exist without the relationship. Every instructor works in a department, so INSTRUCTOR’s participation in WORKS_IN is total: an instructor without a department breaks the brief. A new department may have no instructors yet, so DEPARTMENT’s participation is partial. Chen notation draws total participation as a double line between the entity set and the diamond. When the design becomes tables, total participation on the many side turns into a foreign key that may not be NULL, which the lesson on mapping ER diagrams to tables does step by step.

The two constraints are independent, and the brief above shows four different combinations:

• WORKS_IN, N:1: total for INSTRUCTOR, partial for DEPARTMENT.
• HEADS, 1:1: total for DEPARTMENT, partial for INSTRUCTOR.
• ENROLS, M:N: partial for both STUDENT and COURSE.
• ADVISES, 1:N: total for STUDENT, partial for INSTRUCTOR.

The words of a brief give them away. “Exactly one”, “at least one”, “every” and “must” set a minimum of one, which is total participation; “may”, “at most”, “can” and “any number, including none” leave the minimum at zero, which is partial participation. Where a brief says nothing, ask: an instructor with no students to advise is a different design from one who must advise at least one.

(min,max) and crow’s foot: the same numbers at opposite ends

The (min,max) notation writes both constraints as one pair for each entity set, next to that entity set: how many times one of its entities takes part in the relationship, at least and at most. Every instructor works in exactly one department, so INSTRUCTOR gets (1,1); a department has any number of instructors, so DEPARTMENT gets (0,N). The minimum is the participation, and the maximum carries the ratio.

Chen’s ratio labels, crow’s foot and UML count the other way. The mark next to an entity says how many of that entity one entity on the other side is related to. So the N of WORKS_IN sits on INSTRUCTOR’s side in Chen notation, the crow’s foot is drawn at the INSTRUCTOR end, and the (min,max) pair that sat next to INSTRUCTOR, (1,1), appears at the DEPARTMENT end as “one and only one”. Each notation is consistent on its own; they disagree only about which end of the line a number belongs to.

Crow’s foot draws two symbols at each end: the one nearer the box is the maximum (a bar for one, the three-pronged foot for many) and the one further out the minimum (a ring for zero, a bar for one). UML writes the same pair as a multiplicity, such as 0..* or 1. The rule for converting is short: take the (min,max) pair written next to one entity set and draw it at the far end of the line. The program below applies that rule to four relationships of the brief:

"""Draws binary relationships of the college brief in three notations from their (min,max) pairs.

A (min,max) pair is written next to the entity it describes: how many times one entity of that set takes part in
the relationship. Chen's ratio labels, crow's-foot symbols and UML multiplicities all count the other way: the mark
next to an entity says how many of THAT entity one entity on the other side is related to. So every mark moves to the
far end of the line, which is the trap this program makes visible.
"""

CROW = {
    (0, 1): "zero or one",
    (1, 1): "one and only one",
    (0, "N"): "zero or many",
    (1, "N"): "one or many",
}
UML = {(0, 1): "0..1", (1, 1): "1", (0, "N"): "0..*", (1, "N"): "1..*"}

# (entity A, its (min,max), relationship, entity B, its (min,max))
RELATIONSHIPS = [
    ("INSTRUCTOR", (1, 1), "WORKS_IN", "DEPARTMENT", (0, "N")),
    ("DEPARTMENT", (1, 1), "HEADED_BY", "INSTRUCTOR", (0, 1)),
    ("STUDENT", (1, 1), "ADVISED_BY", "INSTRUCTOR", (0, "N")),
    ("STUDENT", (0, "N"), "ENROLS", "COURSE", (0, "N")),
]


def pair(p):
    return f"({p[0]},{p[1]})"


def participation(p):
    return "total" if p[0] >= 1 else "partial"


for a, pa, rel, b, pb in RELATIONSHIPS:
    # The ratio label next to A is the maximum of B's pair, and the other way round.
    # Many on both sides is written M:N, two letters for two independent numbers.
    near_a, near_b = pb[1], pa[1]
    if near_a == near_b == "N":
        near_a = "M"
    print(f"{rel}: {a} {pair(pa)} and {b} {pair(pb)}")
    print(f"  Chen ratio      {a} {near_a} : {near_b} {b}")
    print(f"  participation   {a} {participation(pa)}, {b} {participation(pb)}")
    print(f"  crow's foot     at {a}: {CROW[pb]}; at {b}: {CROW[pa]}")
    print(f"  UML             at {a.title()}: {UML[pb]}; at {b.title()}: {UML[pa]}")
    print()

WORKS_IN: INSTRUCTOR (1,1) and DEPARTMENT (0,N)
  Chen ratio      INSTRUCTOR N : 1 DEPARTMENT
  participation   INSTRUCTOR total, DEPARTMENT partial
  crow's foot     at INSTRUCTOR: zero or many; at DEPARTMENT: one and only one
  UML             at Instructor: 0..*; at Department: 1

HEADED_BY: DEPARTMENT (1,1) and INSTRUCTOR (0,1)
  Chen ratio      DEPARTMENT 1 : 1 INSTRUCTOR
  participation   DEPARTMENT total, INSTRUCTOR partial
  crow's foot     at DEPARTMENT: zero or one; at INSTRUCTOR: one and only one
  UML             at Department: 0..1; at Instructor: 1

ADVISED_BY: STUDENT (1,1) and INSTRUCTOR (0,N)
  Chen ratio      STUDENT N : 1 INSTRUCTOR
  participation   STUDENT total, INSTRUCTOR partial
  crow's foot     at STUDENT: zero or many; at INSTRUCTOR: one and only one
  UML             at Student: 0..*; at Instructor: 1

ENROLS: STUDENT (0,N) and COURSE (0,N)
  Chen ratio      STUDENT M : N COURSE
  participation   STUDENT partial, COURSE partial
  crow's foot     at STUDENT: zero or many; at COURSE: zero or many
  UML             at Student: 0..*; at Course: 0..*

HEADED_BY shows the move clearly: the department’s own pair, (1,1), becomes “one and only one” at the INSTRUCTOR end, because each department has exactly one head. Before answering a question that uses pairs, find out which convention it follows; the same pair read with the other convention means the opposite.

Recursive relationships and roles

In a recursive relationship one entity set takes part twice, and only the role names tell the two sides apart: a course and its prerequisite, a manager and a report. They matter as soon as the design becomes tables, where a 1:N recursive relationship turns into a foreign key to the same table, and an M:N one into a table with two foreign keys to the same table, each named after its role. Queries then join the table with itself, once for each role:

-- REPORTS_TO is a recursive relationship on STAFF: one role is the manager, the other the report.
CREATE TABLE staff (
  staff_id   INTEGER PRIMARY KEY,
  name       TEXT NOT NULL,
  manager_id INTEGER REFERENCES staff (staff_id)   -- the manager role; NULL for the person at the top
);
INSERT INTO staff VALUES
  (1, 'Asha', NULL),
  (2, 'Bilal', 1),
  (3, 'Chitra', 1),
  (4, 'Dev', 2),
  (5, 'Esha', 2),
  (6, 'Farhan', 3);

-- Everyone with their manager: the same table twice, once in each role.
-- LEFT JOIN keeps Asha, who takes part in REPORTS_TO only as a manager.
SELECT r.name AS report, coalesce(m.name, '(nobody)') AS manager
FROM staff AS r
LEFT JOIN staff AS m ON m.staff_id = r.manager_id
ORDER BY r.staff_id;

-- Both roles have partial participation: count the people in each.
SELECT count(*) FILTER (WHERE manager_id IS NULL) AS without_manager,
       (SELECT count(*) FROM staff AS s
        WHERE NOT EXISTS (SELECT 1 FROM staff AS r WHERE r.manager_id = s.staff_id)) AS without_reports
FROM staff;

┌────────┬──────────┐
│ report │ manager  │
├────────┼──────────┤
│ Asha   │ (nobody) │
│ Bilal  │ Asha     │
│ Chitra │ Asha     │
│ Dev    │ Bilal    │
│ Esha   │ Bilal    │
│ Farhan │ Chitra   │
└────────┴──────────┘
┌─────────────────┬─────────────────┐
│ without_manager │ without_reports │
├─────────────────┼─────────────────┤
│ 1               │ 3               │
└─────────────────┴─────────────────┘

Both roles of REPORTS_TO have partial participation, and the second query counts them: one person has no manager and three people manage nobody. The LEFT JOIN in the first query is what keeps Asha in the list; an inner join would drop the one person who takes part only in the manager role. The exercise below works with REQUIRES, the recursive relationship of the brief, and its starter query mixes up the two roles.

Ternary relationships and three binary ones

A ternary relationship records triples: this supplier supplied this part to this project. It is tempting to replace it with three binary relationships that record pairs, one between each two of the entity sets. The pairs are all true, but they cannot say which triples happened:

-- Three supplies that really happened: who supplied which part to which project.
CREATE TABLE supplies (
  supplier TEXT NOT NULL,
  part     TEXT NOT NULL,
  project  TEXT NOT NULL,
  PRIMARY KEY (supplier, part, project)
);
INSERT INTO supplies VALUES
  ('Sunrise', 'bolt',  'bridge'),
  ('Sunrise', 'cable', 'metro'),
  ('Kaveri',  'bolt',  'metro');

-- The same facts kept as three binary relationships, one table of pairs each.
CREATE TABLE sells    AS SELECT DISTINCT supplier, part    FROM supplies;  -- supplier sells part
CREATE TABLE uses     AS SELECT DISTINCT part, project     FROM supplies;  -- project uses part
CREATE TABLE serves   AS SELECT DISTINCT supplier, project FROM supplies;  -- supplier serves project

-- Rebuild the triples from the pairs: every combination that all three tables allow.
CREATE VIEW rebuilt AS
SELECT s.supplier, s.part, u.project
FROM sells AS s
JOIN uses AS u ON u.part = s.part
JOIN serves AS v ON v.supplier = s.supplier AND v.project = u.project;

SELECT (SELECT count(*) FROM supplies) AS real_supplies,
       (SELECT count(*) FROM rebuilt)  AS rebuilt_rows;

-- The rebuilt row that never happened.
SELECT * FROM rebuilt
EXCEPT
SELECT * FROM supplies;

┌───────────────┬──────────────┐
│ real_supplies │ rebuilt_rows │
├───────────────┼──────────────┤
│ 3             │ 4            │
└───────────────┴──────────────┘
┌──────────┬──────┬─────────┐
│ supplier │ part │ project │
├──────────┼──────┼─────────┤
│ Sunrise  │ bolt │ metro   │
└──────────┴──────┴─────────┘

Joining the three tables of pairs rebuilt four supplies from three real ones. The invented one, Sunrise supplying bolts to the metro, is consistent with every pair: Sunrise sells bolts (it sent them to the bridge), the metro uses bolts (it got them from Kaveri) and Sunrise serves the metro (with cable). Only the ternary knew that those three facts do not belong to one supply.

The split is safe only when the business guarantees that every combination the pairs allow really happened. Such a rule is called a join dependency, and the module on normal forms returns to it with fifth normal form. Without that guarantee, keep the ternary, or turn it into an entity of its own, SUPPLY with a key and attributes such as a date and a quantity, related to the three entity sets by binary relationships.

Ratios on a ternary are read one entity at a time. A 1 next to SUPPLIER means that each combination of a part and a project has at most one supplier: then the pair (part, project) identifies a supply, which decides its key when the relationship becomes a table.

Interview questions

What is the difference between a relationship’s cardinality ratio and its participation? The cardinality ratio limits the maximum: with how many entities on the other side one entity can be associated, 1:1, 1:N or M:N. Participation sets the minimum: total if every entity of the set must take part, partial if some may stay out. They are independent. Every instructor works in exactly one department while a new department may have none, so WORKS_IN is N:1 with total participation of INSTRUCTOR and partial participation of DEPARTMENT. In (min,max) form they become one pair per entity set, (1,1) for INSTRUCTOR and (0,N) for DEPARTMENT: the minimum is the participation, the maximum the ratio.

Key takeaways

• A relationship set associates entities; its degree is the number of entity sets involved, and roles name the part each plays, which a recursive relationship cannot do without.
• An attribute that describes a pair, such as a grade, belongs to the relationship, not to either entity.
• The cardinality ratio is the maximum and participation the minimum; read both from the brief’s wording and ask when it is silent.
• Total participation is a double line in Chen notation and becomes a NOT NULL foreign key in tables.
• A (min,max) pair describes the entity it is written next to; Chen’s ratio labels, crow’s foot and UML put the same number at the far end. State the convention before you answer.
• Three binary relationships record pairs, not triples: joining them can invent facts, so keep a ternary unless a join dependency guarantees the split.