Cardinality ratios; total vs partial participation; (min,max) notation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is the largest possible size of a relationship set between entity sets of sizes 4 and 5? from Lesson 1.2.1
2. Where does a student's grade in a course belong? from Lesson 1.2.1
3. Negate "every student is enrolled in some course". from Lesson 0.2.3

1 · The Hook

"Every student belongs to exactly one department." "A department may have many students." "Some departments have no students yet." These three sentences fully describe how STUDENT and DEPARTMENT can be linked, and each matters when building tables: they decide whether you need a separate table for the relationship, and whether a column may be NULL. GATE tests these constraints every year, usually through the minimum number of tables (Lesson 2.4.2).

2 · Predict First

Each student belongs to exactly one department; each department has many students. In the BELONGS_TO relationship set, can one student appear twice? Can one department appear many times? Can a department appear zero times?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

A student appears exactly once (one department). A department can appear many times (many students). A department can appear zero times if it has no students; this depends on the participation rule. The first two facts are the cardinality ratio (N:1 from STUDENT to DEPARTMENT). The third is participation.

Cardinality ratio (binary relationships)

The cardinality ratio gives the maximum number of relationships an entity can take part in.

Chen notation: write 1, N or M on the lines. In OFFERS(DEPARTMENT 1 — N COURSE), the 1 is written next to DEPARTMENT and means "each course has at most one department". The number next to an entity tells how many of that entity a single entity on the other side can be linked to.

Participation constraint

The participation of an entity type says whether every entity must take part (the minimum).

• Total participation (existence dependency): every entity takes part at least once. Drawn as a double line. "Every course must be offered by some department."
• Partial participation: some entities may take part zero times. Single line. "A faculty member may or may not head a department."

Cardinality ratio and participation together are the structural constraints of a relationship.

(min, max) notation

An alternative writes a pair (min, max) on the line next to each entity type E: every entity of E takes part in at least min and at most max relationships.

• min = 0 → partial participation; min ≥ 1 → total participation.
• max = 1 → that entity is on the "single" side of its links; max = N → many.

OFFERS in (min, max): DEPARTMENT (0, N) — a department offers zero or many courses. COURSE (1, 1) — each course is offered by exactly one department.

The trap: (min, max) is written next to the entity it describes. In Chen ratio notation, the N for OFFERS sits next to COURSE, while in (min, max) notation the N sits next to DEPARTMENT. The two notations put the "many" on opposite sides. Always ask: "the number next to E describes E, or describes the partner of E?"

Counting with constraints

For R(A, B) with |A| = a and |B| = b:

• 1:1: at most min(a, b) relationships.
• 1:N (A on the 1 side): at most b (each B used at most once).
• M:N: at most a × b.
• If B participates totally in a 1:N with A on the 1 side, the relationship set has exactly b relationships.

Where may a relationship attribute live?

In a 1:N relationship each entity on the N side has at most one partner, so an attribute of the relationship can be moved to the N-side entity (COURSE can hold offered_since). In 1:1 it can move to either side. In M:N it must stay on the relationship.

4 · Visual

The same constraint in the two notations. Note where the N sits.

5 · Worked Examples

Example 1 Easy

Give the cardinality ratio: (a) a passport belongs to one citizen and a citizen has at most one passport; (b) a hostel room houses several students and each student lives in at most one room; (c) students and clubs, where students join many clubs and clubs have many members.

Solution

(a) 1:1. (b) 1:N from ROOM to STUDENT. (c) M:N.

Example 2 Medium

Write OFFERS(DEPARTMENT, COURSE) in (min, max) notation if every department offers at least 2 courses and every course is offered by exactly one department.

Solution

DEPARTMENT (2, N), COURSE (1, 1). Both participations are total (min ≥ 1).

Example 3 GATE

Entity sets: 10 faculty, 6 departments. HEADS(FACULTY, DEPARTMENT) is 1:1, and DEPARTMENT participates totally. How many relationships are in the HEADS relationship set, and how many faculty do not head any department?

Solution

Total participation of DEPARTMENT: every department has a head, and 1:1 means each has exactly one and no faculty heads two. So exactly 6 relationships and 10 − 6 = 4 faculty without a department to head.

8 · Connect the Dots

Lesson 1.2.1 introduced relationships; this lesson put limits on them: the max (ratio) and the min (participation), and the (min, max) notation that writes both. Next: an entity type that cannot be identified on its own, the weak entity, whose existence depends on a total-participation relationship with an owner.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Ratio

Each employee works in exactly one department; a department has many employees. From EMPLOYEE to DEPARTMENT the ratio is:

1. (A) M:N
2. (B) 1:N
3. (C) 1:1
4. (D) N:1

Q2 · MCQ · 1 mark(s) — Participation

A double line between an entity type and a relationship means:

1. (A) the entity type is weak
2. (B) the relationship is M:N
3. (C) the attribute is multivalued
4. (D) every entity of that type participates (total participation)

Q3 · MCQ · 2 mark(s) — (min,max)

In (min, max) notation, R(A, B) shows A (0, N) and B (1, 1). Which is true?

1. (A) Every A is linked to exactly one B.
2. (B) Every B is linked to exactly one A, and some A may have no B.
3. (C) The relationship is M:N.
4. (D) Every A has at least one B.

Q4 · NAT · 2 mark(s) — Counting

STUDENT has 50 entities and HOSTEL_ROOM has 30. LIVES_IN(STUDENT, ROOM) is N:1 (each student in at most one room) and STUDENT participates totally. How many relationships are in LIVES_IN?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Constraints

Which statements are true?

1. (A) Participation constraint limits the minimum participation.
2. (B) A 1:N relationship must have total participation on the N side.
3. (C) Cardinality ratio limits the maximum participation.
4. (D) In a 1:N relationship, a relationship attribute may be moved to the N-side entity.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

cardinality ratio (1:1, 1:N, N:1, M:N)participation constrainttotal participation (double line)partial participationexistence dependencystructural constraints(min, max) notation