Lesson 7: Relationships, Relationship Types and Constraints¶
Degree, cardinality ratio, participation, roles and recursion
About this lesson
Course: Database Management Systems
Unit 2: Entity Relationship Modelling · 7 Lecture Hours
Lesson duration: 2 lectures
Reading: Elmasri & Navathe, Ch. 3.4
Learning Outcomes
- Define relationship, relationship type and relationship set.
- Determine the degree of a relationship type; model recursive relationships with role names.
- Apply the two structural constraints: cardinality ratio (1:1, 1:N, M:N) and participation (total, partial).
- Read and write (min, max) notation, and convert between the two notations.
- Decide correctly when an attribute belongs to a relationship rather than to an entity type.
7.1 Relationships¶
The three terms
Relationship (relationship instance) — an association among entities. One specific fact: student X2019 took admission in course CS01 on 2019-07-15.
Relationship type R among entity types E1, E2, ..., En — the definition of such an association. Drawn as a diamond. This is the intension.
Relationship set — the set of all relationship instances of that type currently in the database. Mathematically it is a subset of the Cartesian product E1 x E2 x ... x En; each instance is an ordered tuple (e1, e2, ..., en). This is the extension.
As with entity types, the type and the set share a name and context disambiguates.
STUDENT set COURSE set
+---------------+ +---------------+
| s1 (X2019) o|--------\ /--------|o c1 (CS01) |
| s2 (X2020) o|---------\-/---------|o c2 (CH01) |
| s3 (Z1188) o|----------X |o c3 (MA02) |
+---------------+ \_________+---------------+
Relationship set TAKES_ADMISSION =
{ (s1,c1), (s2,c1), (s2,c2), (s3,c3) }
-- a SUBSET of STUDENT x COURSE.
Figure 3.1 — A relationship set as a subset of the Cartesian product.
Notation: a diamond joined by plain lines to the participating entity-type rectangles.
+-----------+ /-----------------\ +-----------+
| STUDENT |-------< TAKES_ADMISSION >-------| COURSE |
+-----------+ \-----------------/ +-----------+
|
(Dateofadmission)
7.2 Degree of a Relationship Type¶
Degree
The number of participating entity types. (Not the number of entities.)
| Degree | Name | Example |
|---|---|---|
| 1 | Unary / recursive | EMPLOYEE SUPERVISES EMPLOYEE |
| 2 | Binary | STUDENT TAKES_ADMISSION COURSE |
| 3 | Ternary | SUPPLIER SUPPLIES PART to PROJECT |
| n | n-ary | rare in practice |
Binary relationships are by far the most common and are what the examination concentrates on.
Recursive (unary) relationships and role names¶
The same entity type participates more than once, in different roles.
Role name
A label on the line from an entity type to a relationship diamond, stating the part that entity plays in the relationship. Role names are optional in general but mandatory for recursive relationships, because without them the two lines are indistinguishable.
+--------------+
| EMPLOYEE |
+--+--------+--+
supervisor | | supervisee
(1) | | (N)
| |
/---+--------+---\
< SUPERVISES >
\-----------------/
Read: one employee (as SUPERVISOR) supervises many employees
(as SUPERVISEE); each employee has at most one supervisor.
Cardinality 1:N.
Figure 3.2 — A recursive relationship with role names.
Other examples: COURSE IS_PREREQUISITE_OF COURSE (M:N); PERSON IS_MARRIED_TO PERSON (1:1); PART CONTAINS PART in a bill of materials (M:N).
Ternary relationships¶
+-----------+ +-----------+
| SUPPLIER | | PROJECT |
+-----+-----+ +-----+-----+
| |
| /-------------\ |
+-----< SUPPLIES >------+
\------+------/
|
+-----+-----+ (Quantity)
| PART |
+-----------+
One instance = (supplier s, part p, project j):
"supplier s supplies part p to project j".
A ternary relationship is not three binary ones
SUPPLIES(S, P, J) states a genuine three-way fact. Replacing it with CAN_SUPPLY(S,P), USES(P,J) and WORKS_FOR(S,J) loses information: from the three binaries you can infer that s supplies p, that project j uses p, and that s works for j — but not that s supplies p specifically to j. A supplier may supply bolts to project A and nuts to project B; the binaries cannot distinguish that case from supplying both parts to both projects.
Use a ternary relationship when the fact is genuinely irreducible to pairs; otherwise prefer binaries, which are simpler to understand and to map.
7.3 Constraints on Relationship Types¶
Two independent structural constraints apply to every relationship type. Together they are called structural constraints, and getting them right is the substance of ER design.
Cardinality ratio (mapping cardinality)¶
Cardinality ratio
Specifies the maximum number of relationship instances an entity can participate in. For a binary relationship the possibilities are 1:1, 1:N, N:1 and M:N.
ONE-TO-ONE (1:1) A---o o---1
Each A relates to at most one B, and each B to at most one A.
+--------+ 1 /--------\ 1 +----------+
| TEACHER|-------< HEADS >-----| DEPARTMENT|
+--------+ \--------/ +----------+
A teacher heads at most one department; a department has
at most one head.
ONE-TO-MANY (1:N)
+--------+ 1 /----------\ N +---------+
| COURSE |-------< HAS_SEC >-----| SECTION |
+--------+ \----------/ +---------+
One course has many sections; each section belongs to
exactly one course.
MANY-TO-MANY (M:N)
+--------+ M /----------------\ N +--------+
| STUDENT|-------< TAKES_ADMISSION >---| COURSE |
+--------+ \----------------/ +--------+
A student may take many courses; a course may have
many students.
Figure 3.3 — The three cardinality ratios for binary relationships.
How to determine the ratio — the two-question method
Always ask two questions, one from each side, and always phrase them with "one ... how many ...?"
For STUDENT – COURSE:
- One student can take admission in how many courses? → many (the course outline says "a student may enrol in any number of courses").
- One course can have how many students? → many.
Both "many" → M:N.
For COURSE – SECTION:
- One course has how many sections? → many.
- One section belongs to how many courses? → exactly one.
One "many", one "one" → 1:N (with the "1" on the COURSE side).
Where to write the label: put 1 or N on the line next to the entity type it describes, meaning "an entity of this type participates this many times". Different textbooks differ; state your convention.
Participation constraint (existence dependency)¶
Participation constraint
Specifies the minimum number of relationship instances an entity may participate in.
Total participation (existence dependency) — every entity of the type must participate in at least one relationship instance. Drawn as a double line. Minimum = 1.
Partial participation — an entity may or may not participate. Drawn as a single line. Minimum = 0.
+-----------+ M /----------------\ N +----------+
| STUDENT |======< TAKES_ADMISSION >-----| COURSE |
+-----------+ \----------------/ +----------+
double line single line
= TOTAL participation = PARTIAL
Reading: EVERY student must be admitted to at least one
course (you cannot be a student otherwise), but a
course MAY exist with no students yet enrolled.
Figure 3.4 — Total and partial participation on one relationship.
Cardinality and participation are independent
Cardinality is about the maximum ("at most how many?"); participation is about the minimum ("at least one, or possibly none?"). Every relationship type needs both, decided separately for each side. A relationship can be M:N with total participation on one side and partial on the other, as above.
The (min, max) notation¶
An alternative, more precise notation places a pair (min, max) on each line.
(min, max)
For entity type E participating in relationship R, the pair (min, max) means: each entity of E must participate in at least min and at most max relationship instances of R.
min = 0→ partial participation.min >= 1→ total participation.max = N(or*) → no upper limit.- Necessarily
0 <= min <= maxandmax >= 1.
The notation trap — the labels swap sides
In Chen (1:N) notation the label describes the entity type it sits next to. In (min, max) notation the pair also sits next to its own entity type — but because it constrains that entity's participation, the resulting picture looks reversed compared with the 1/N labels.
Study this example until it is automatic:
Chen: COURSE ---1--- <HAS_SEC> ---N--- SECTION
(min,max): COURSE --(0,N)-- <HAS_SEC> --(1,1)-- SECTION
The "1" in Chen sits on COURSE; the "(1,1)" in min-max sits
on SECTION. Both say the same thing:
one section belongs to exactly one course.
Conversion table¶
| Chen notation | Meaning | (min, max) on left | (min, max) on right |
|---|---|---|---|
A --1-- R --1-- B, both partial |
1:1 | (0,1) | (0,1) |
A ==1== R --N-- B, A total |
1:N | (1,1) on A... | see below |
A --M-- R --N-- B, both partial |
M:N | (0,N) | (0,N) |
A ==M== R --N-- B, A total |
M:N | (1,N) | (0,N) |
Worked: STUDENT ==M== TAKES_ADMISSION --N-- COURSE, student total, course partial.
- On the
STUDENTline: a student participates at least once (total) and possibly many times → (1, N). - On the
COURSEline: a course may have no students (partial) and possibly many → (0, N).
+-----------+ (1,N) /----------------\ (0,N) +----------+
| STUDENT |-------< TAKES_ADMISSION >------| COURSE |
+-----------+ \----------------/ +----------+
Worked: EMPLOYEE MANAGES DEPARTMENT, 1:1, every department must have a manager, but not every employee manages.
EMPLOYEEline: an employee manages 0 or 1 departments → (0, 1).DEPARTMENTline: a department has exactly 1 manager → (1, 1).
7.4 Attributes of Relationship Types¶
Relationship attribute
An attribute that describes the association itself, not either participating entity. Drawn as an ellipse attached to the diamond.
The decisive test
Ask: "Is this fact determined by one entity alone, or only by the combination?"
Dateofadmission is not a property of the student (they have several admission dates, one per course) and not a property of the course (each student joined on a different date). It is determined only by the pair (student, course). Therefore it belongs to the relationship.
+-----------+ M /----------------\ N +----------+
| STUDENT |------< TAKES_ADMISSION >-----| COURSE |
+-----------+ \-------+--------/ +----------+
|
(Dateofadmission) <-- attribute of the
RELATIONSHIP
Where a relationship attribute can be moved¶
| Cardinality | Can the attribute migrate to an entity type? |
|---|---|
| M:N | No. It must stay on the relationship (and becomes a column of the junction table on mapping). |
| 1:N | Yes — it can move to the entity type on the N side, since each such entity has exactly one relationship instance. |
| 1:1 | Yes — it can move to either side (choose the one with total participation, to avoid NULLs). |
Example (1:N). EMPLOYEE WORKS_FOR DEPARTMENT is N:1, with relationship attribute StartDate. Each employee works for exactly one department, so StartDate can equally be an attribute of EMPLOYEE.
Example (M:N). Dateofadmission on the M:N TAKES_ADMISSION cannot move. Putting it on STUDENT would allow only one admission date per student, contradicting the M:N ratio.
7.5 Relationships vs Weak Entities — a comparison¶
Students confuse the identifying relationship of a weak entity type with an ordinary 1:N relationship. The distinction:
| Ordinary 1:N relationship | Identifying relationship | |
|---|---|---|
| Notation | Single diamond | Double diamond |
| Related entity type | Strong | Weak (double rectangle) |
| Purpose | Records an association | Supplies the identification of the weak entity |
| Participation of the N side | May be partial | Always total |
| On mapping | Foreign key column | Foreign key that is part of the primary key |
7.6 Solved Questions¶
Solved Question 1
Q. Define relationship type, relationship set and degree. Give one example each of unary, binary and ternary relationships.
A. A relationship type R among entity types E1, ..., En is the definition of an association among entities of those types; it is drawn as a diamond and is the intension.
A relationship set is the set of all current relationship instances of that type. Formally it is a subset of the Cartesian product E1 x E2 x ... x En, each instance being an ordered tuple (e1, ..., en). It is the extension.
The degree of a relationship type is the number of participating entity types.
| Degree | Name | Example | One instance means |
|---|---|---|---|
| 1 | Unary / recursive | EMPLOYEE SUPERVISES EMPLOYEE |
employee a supervises employee b |
| 2 | Binary | STUDENT TAKES_ADMISSION COURSE |
student s is admitted to course c |
| 3 | Ternary | SUPPLIER SUPPLIES PART PROJECT |
supplier s supplies part p to project j |
In a recursive relationship the same entity type participates twice, in different roles, so role names such as supervisor and supervisee must be written on the lines to distinguish them.
Solved Question 2
Q. Distinguish cardinality ratio from participation constraint. Show that they are independent by giving all four combinations for one relationship.
A.
| Cardinality ratio | Participation constraint | |
|---|---|---|
| Specifies | The maximum number of instances | The minimum number of instances |
| Question | "At most how many?" | "At least one, or possibly none?" |
| Values | 1:1, 1:N, M:N | Total or partial |
| Notation | 1, N, M on the line |
Double line (total) or single line (partial) |
| In (min,max) | The max component |
The min component |
They are independent: cardinality fixes the ceiling, participation the floor, and each side of the relationship is decided separately.
Take STUDENT – COURSE, with all four combinations of participation over an M:N ratio:
| Case | STUDENT side | COURSE side | Business meaning |
|---|---|---|---|
| 1 | Partial (0,N) | Partial (0,N) | A student may be admitted to no course, and a course may have no students. |
| 2 | Total (1,N) | Partial (0,N) | Every student must be admitted to at least one course; a new course may exist with no students. This is our college. |
| 3 | Partial (0,N) | Total (1,N) | A course is only created once someone enrols; a person may be a student without any admission. |
| 4 | Total (1,N) | Total (1,N) | Every student is admitted somewhere and every course has at least one student. |
Case 2 is the realistic one, which demonstrates that a single relationship needs both constraints, chosen independently for each side.
Solved Question 3
Q. Determine the cardinality ratio and participation for each, and express in both notations.
a. PERSON – PASSPORT
b. DEPARTMENT – EMPLOYEE (works for)
c. AUTHOR – BOOK (wrote)
d. EMPLOYEE – EMPLOYEE (manages)
A.
a. PERSON – PASSPORT
One person holds how many passports? At most one. One passport belongs to how many people? Exactly one. → 1:1.
Participation: not every person holds a passport (partial on PERSON); every passport must belong to a person (total on PASSPORT).
Chen: PERSON --1-- <HOLDS> ==1== PASSPORT
(min,max): PERSON (0,1) -- <HOLDS> -- (1,1) PASSPORT
b. DEPARTMENT – EMPLOYEE
One department has how many employees? Many. One employee works for how many departments? Exactly one. → 1:N with the 1 on DEPARTMENT.
Participation: every employee must belong to a department (total on EMPLOYEE); a newly created department may have no employees yet (partial on DEPARTMENT).
Chen: DEPARTMENT --1-- <WORKS_FOR> ==N== EMPLOYEE
(min,max): DEPARTMENT (0,N) -- <WORKS_FOR> -- (1,1) EMPLOYEE
c. AUTHOR – BOOK
One author writes how many books? Many. One book has how many authors? Many. → M:N.
Participation: every book must have at least one author (total on BOOK); a person recorded as an author has written at least one book (total on AUTHOR).
Chen: AUTHOR ==M== <WROTE> ==N== BOOK
(min,max): AUTHOR (1,N) -- <WROTE> -- (1,N) BOOK
d. EMPLOYEE – EMPLOYEE (manages) — recursive, so role names are required.
One manager manages how many employees? Many. One employee has how many managers? At most one. → 1:N.
Participation: not every employee is a manager (partial in the manager role); the chief executive has no manager, so participation in the subordinate role is also partial.
Chen: EMPLOYEE --1(manager)-- <MANAGES> --N(subordinate)-- EMPLOYEE
(min,max): manager role (0,N) ; subordinate role (0,1)
Solved Question 4
Q. Where should Dateofadmission be placed, and why? What would go wrong if it were made an attribute of STUDENT? Of COURSE?
A. It belongs to the relationship type TAKES_ADMISSION, drawn as an ellipse attached to the diamond.
Test: is the fact determined by one entity alone, or only by the combination? A student admitted to three courses has three admission dates, so the date is not a function of the student. A course with 60 students was joined on many different dates, so it is not a function of the course. It is determined only by the pair (student, course), which is precisely the definition of a relationship attribute.
If made an attribute of STUDENT: each student could store only one admission date, so a student admitted to Computer Science in July and to a part-time Mathematics course in September could not record both. This silently contradicts the M:N cardinality, and forces either data loss or a repeating group that violates 1NF.
If made an attribute of COURSE: each course could store only one admission date for all its students — meaningless, since students join on different dates. Recording the correct date for even two students becomes impossible.
General rule. On an M:N relationship the attribute cannot be migrated to either entity type. On a 1:N relationship it may be migrated to the entity type on the N side (each such entity participates exactly once); on a 1:1 relationship it may be migrated to either side, preferably the one with total participation to avoid NULLs.
On mapping (Unit 5) the M:N relationship becomes ADMISSION(Rollno, SID, Dateofadmission) with primary key (Rollno, SID) — and the relationship attribute becomes an ordinary column of that table.
Solved Question 5
Q. What is a recursive relationship? Why are role names essential? Model "a course may have several prerequisite courses".
A. A recursive (unary) relationship is one in which the same entity type participates more than once, each time in a different role.
Role names are essential because the two lines run between the same rectangle and the same diamond, so they are otherwise indistinguishable. Without labels, EMPLOYEE — SUPERVISES — EMPLOYEE does not say which end is the supervisor; the diagram becomes ambiguous, and the cardinality labels cannot be interpreted. Role names also become the column names on mapping, so they carry through to the implementation.
Prerequisites. One course may have how many prerequisites? Many (a course can require several). One course may be a prerequisite for how many courses? Many. → M:N. Participation is partial on both sides: an introductory course has no prerequisites, and an advanced course is a prerequisite for nothing.
+--------------+
| COURSE |
+--+--------+--+
(0,N) has_prereq | | is_prereq_for (0,N)
| |
/---+--------+---\
< PREREQUISITE >
\-----------------/
On mapping this M:N recursive relationship yields a table with two foreign keys to the same table, both named after the roles:
CREATE TABLE PREREQUISITE (
CourseID VARCHAR(6),
PrereqID VARCHAR(6),
PRIMARY KEY (CourseID, PrereqID),
FOREIGN KEY (CourseID) REFERENCES COURSE(SID),
FOREIGN KEY (PrereqID) REFERENCES COURSE(SID),
CHECK (CourseID <> PrereqID)
);
The CHECK prevents a course being its own prerequisite. (Detecting longer cycles requires a recursive query, which is beyond a table constraint.)
Solved Question 6
Q. Explain why a ternary relationship cannot in general be replaced by three binary relationships. Illustrate.
A. Because a ternary relationship records an irreducible three-way fact, whereas three binaries record only three separate two-way facts, and the pairwise facts do not determine the triples.
Consider SUPPLIES(Supplier, Part, Project) with these instances:
| Supplier | Part | Project |
|---|---|---|
| S1 | Bolt | P1 |
| S1 | Nut | P2 |
Now decompose into three binaries:
CAN_SUPPLY(Supplier, Part)= {(S1, Bolt), (S1, Nut)}USES(Part, Project)= {(Bolt, P1), (Nut, P2)}WORKS_FOR(Supplier, Project)= {(S1, P1), (S1, P2)}
Reconstructing by joining the three binaries yields four triples, not two:
| Supplier | Part | Project | Real? |
|---|---|---|---|
| S1 | Bolt | P1 | yes |
| S1 | Bolt | P2 | spurious |
| S1 | Nut | P1 | spurious |
| S1 | Nut | P2 | yes |
The two spurious tuples are indistinguishable from the genuine ones, so information has been lost: the decomposition is not lossless. The binaries can say "S1 can supply bolts", "P1 uses bolts" and "S1 works for P1", but they cannot say "S1 supplies bolts specifically to P1".
When decomposition is safe: if the business rule happens to be that a supplier supplies a given part to every project that uses it, then the ternary fact is genuinely determined by the pairs, and three binaries lose nothing. The general rule: use a ternary relationship when the association is genuinely three-way; prefer binaries otherwise, since they are simpler to read, to constrain and to map.
7.7 Exercises¶
A. Short answer
- Define relationship type and relationship set.
- What is the degree of a relationship type? Give an example of degree 3.
- What is a role name? When is it compulsory?
- Define cardinality ratio and list the possibilities for a binary relationship.
- How is total participation drawn? What does it mean?
- In (min, max) notation, what does
(1, N)mean? - Where is a relationship attribute drawn?
B. Long answer
- Explain the structural constraints on a binary relationship type. Show with examples that cardinality and participation are independent.
- Explain (min, max) notation and convert three examples between it and Chen notation, explaining the apparent reversal of labels.
- What is a recursive relationship? Explain with two examples of different cardinality, showing role names, and describe how each maps to tables.
- When does an attribute belong to a relationship rather than to an entity type? State the test, and explain for which cardinalities the attribute may be migrated.
- Explain why a ternary relationship is not in general equivalent to three binary relationships, with a numeric illustration.
C. Application and analytical
- Determine cardinality and participation, and express in both notations:
a.
CUSTOMER–ACCOUNTin a bank where joint accounts are allowed. b.PATIENT–BEDin a hospital at a given moment. c.DRIVER–LICENCE. d.STUDENT–SOCIETYin our college. e.EMPLOYEE–PROJECTwhere an employee may work on several projects. f.MOTHER–CHILD. - For the college database, draw the fragment for
STUDENT,COURSEandTAKES_ADMISSION, with correct cardinality, participation and the relationship attribute. State every business rule your diagram asserts, in English. - A university insists that every department must have exactly one head, that a head must be a professor of that department, and that a professor may head at most one department. Draw this and give the (min, max) pairs. Which constraint cannot be captured in the ER diagram at all?
- Model a ternary relationship for "a doctor prescribes a drug to a patient on a date". Then argue whether it could be decomposed into binaries.
- For each, state whether the attribute belongs to an entity type or a relationship, and justify:
a.
SalaryinEMPLOYEE–WORKS_FOR–DEPARTMENT(N:1). b.HoursPerWeekinEMPLOYEE–WORKS_ON–PROJECT(M:N). c.DateofenrolmentinSTUDENT–ENROLS_IN–SOCIETY(M:N). d.GradeinSTUDENT–TAKES–EXAM(M:N). - A designer draws
STUDENT ==M== TAKES_ADMISSION ==N== COURSE(both total). What business rule does this assert? Is it realistic for a college? What practical problem arises when the first course of a new session is created?
D. Objective — True or False with reason
- The degree of a relationship is the number of entity instances participating.
- A relationship set is a subset of a Cartesian product.
- In a 1:N relationship the attribute of the relationship can always be moved to the 1 side.
- Total participation is drawn as a double diamond.
(0, 1)indicates total participation.- Role names are compulsory for all relationships.
- A weak entity type's participation in its identifying relationship is always total.
Answers to Section D
- False. It is the number of participating entity types.
- True. Each instance is a tuple
(e1, ..., en)drawn fromE1 x ... x En. - False. It moves to the N side, where each entity participates exactly once. Moving it to the 1 side would allow only one value for many relationship instances.
- False. Total participation is a double line. A double diamond is an identifying relationship.
- False.
min = 0means partial. Total requiresmin >= 1. - False. They are optional in general, but compulsory for recursive relationships, where the lines are otherwise indistinguishable.
- True. Every weak entity must be related to exactly one owner in order to be identified at all.
Lesson Summary
- A relationship set is a subset of the Cartesian product of the participating entity sets; its degree is the number of participating entity types.
- Recursive relationships need role names.
- Cardinality ratio (1:1, 1:N, M:N) sets the maximum; participation (total = double line, partial = single) sets the minimum. They are independent and are decided per side.
- (min, max) notation combines both; the pair sits on its own entity's line, which makes it look reversed relative to Chen labels.
- A relationship attribute is one determined only by the combination of entities. It cannot be migrated on an M:N relationship; it may be migrated to the N side of a 1:N.
- A ternary relationship is generally not decomposable into three binaries without losing information.