Core CS · DBMS

How many, and must there be any at all?

One edge of an ER diagram answers two separate questions, in two separate places. Get them the wrong way round and the tables you build are wrong in a way no amount of careful SQL recovers.

Draw the links, and watch a rule refuse one →

Asha is on two projects. Chetan is on none. The first fact is a cardinality question and the second is a participation question, and one edge of the diagram has to carry both answers without mixing them up.

01 The idea

Two questions about the same edge

An entity set is a collection of things of one kind: every student in the college, every final-year project. A relationship set is what connects two of them. Draw a line from STUDENT to a diamond and another from the diamond to PROJECT, and you have said that students and projects can be linked. You have not yet said anything about how many, or about whether the link is optional.

The diagram answers both, with two labels that sit in different places and mean different things. One is a number written beside each edge, and it caps how many entities may be attached. The other is the thickness of the line, and it decides whether an entity is allowed to have nothing attached at all. Interviewers separate the two on purpose, because a student who has memorised the shapes uses one word for both and gets caught in the follow-up.

Everything in this lesson lives in one college. Three students, S1 Asha, S2 Bina and S3 Chetan. Two final-year projects, P1 Solar Tracker and P2 Chat App. One relationship set, WORKS_ON, between them. Every rule you meet is checked against those five entities, by hand, one pair at a time.

Cardinality is the maximum and participation is the minimum. Cardinality caps how many links an entity may have. Participation says whether it may have zero. Changing one of them never changes the other.

Relationship setA named set of relationship instances. One instance is a tuple that picks one entity from each participating entity set: WORKS_ON = {(S1,P1), (S1,P2), (S2,P1)}. It is a set, so the same pair cannot be recorded twice.

Cardinality ratioThe maximum side. How many entities of one set may attach to a single entity of the other, written 1:1, 1:N, N:1 or M:N in the order the two entity sets are named.

Participation constraintThe minimum side. Whether every entity of a set must appear in at least one instance. Total is drawn as a double line and means it must. Partial is a single line and means it need not.

02 Worked example

One relationship set, counted twice

WORKS_ON records which student works on which final-year project. Read the five nodes left to right. Node 3 is highlighted because it is the thing the other four are measuring, and the two counts that follow it are the two questions from section 01.

1 · Two entity setsSTUDENT = S1 Asha, S2 Bina, S3 Chetan. PROJECT = P1 Solar Tracker, P2 Chat App. Five entities, no links yet.

→

2 · One instance(S1, P1): Asha works on Solar Tracker. One tuple, one entity from each set, and the order is fixed by the diagram.

→

3 · The relationship setWORKS_ON = {(S1,P1), (S1,P2), (S2,P1)}. Every pair that holds right now. The set is the relationship; the diamond is only its name.

→

4 · Count appearancesS1 appears twice and P1 appears twice. Neither side is capped at one, so M:N is the only ratio that permits this set.

→

5 · Count absencesS3 appears in no pair at all, and that is allowed. So STUDENT’s participation is partial, not total.

Nodes 4 and 5 count two different things over the same three pairs, and that is the whole difficulty of this module. Node 4 asks how many times one entity is allowed to appear, and answers with a number beside each edge. Node 5 asks whether an entity is allowed to appear zero times, and answers with the thickness of the line. Shrink the set to {(S1,P1), (S2,P1)} and node 4 changes: N:1 is now enough, because every student has one project while Solar Tracker has two students. Node 5 does not change at all: Chetan still appears nowhere, so participation is still partial. One warning about node 4 before you use it in an exam. Counting the rows tells you which ratios a set is consistent with, not which one the college has chosen: that shrunken set is legal under N:1 and equally legal under M:N. The ratio is a rule about what may be recorded tomorrow, so it comes from the college. Counting is how you check that rule, not how you invent it.

There is one more fact hiding in node 3 that neither count picks up. Asha spends 6 hours a week on Solar Tracker and 4 on Chat App, and Bina spends 10 on Solar Tracker. Those numbers do not belong to Asha, who has two of them. They do not belong to Solar Tracker, which also has two of them. They belong to the pair, and section 03 is where they get somewhere to live.

03 Mechanics

Degree, ratio, participation: three labels on one edge

A relationship set carries three independent labels, and you can get any one of them right while getting the others wrong. Degree says how many entity sets take part. The cardinality ratio caps how many entities may appear on each side. Participation says whether an entity may appear zero times. Take them in that order, against the same college.

Degree	In our college	What it needs that a binary does not	Where it lands in tables
Unary, also called recursive one entity set	`MENTORS on STUDENT: (S1, S3), Asha mentors Chetan`	Role names. Both edges leave STUDENT, so nothing in the picture says which end is the mentor and which is the mentee. The pair is ordered; the drawing is not.	One table with two foreign keys into student. The role names become the column names, because that is the only thing telling the two keys apart.
Binary two entity sets	`WORKS_ON between STUDENT and PROJECT`	Nothing. This is the default, and almost every relationship you will ever draw is binary.	A foreign key when the ratio is 1:N or N:1, a table of its own when it is M:N.
Ternary three entity sets	`SUPERVISES(STUDENT, PROJECT, FACULTY): F1 supervises Asha on Solar Tracker`	An argument that three binary relationships would not say the same thing. Usually they would not, and you should be ready to show why.	One table holding three foreign keys, not three tables holding two each.

Now the ratio, checked against the exact set from section 02: W = {(S1,P1), (S1,P2), (S2,P1)}. Four counts decide every row below. S1 appears twice, S2 once, P1 twice, P2 once.

Ratio, STUDENT : PROJECT	What it permits	Where the labels go	Is W legal?
1:1	One project per student and one student per project.	`1 beside STUDENT, 1 beside PROJECT`	`No. S1 appears twice and P1 appears twice. The largest legal subset holds two pairs, for example {(S1,P2), (S2,P1)}`
1:N	Many projects per student, one student per project.	`1 beside STUDENT, N beside PROJECT`	`No. (S1,P1) and (S1,P2) are fine. (S2,P1) is not, because P1 already has S1`
N:1	One project per student, many students per project.	`N beside STUDENT, 1 beside PROJECT`	`No. (S1,P1) and (S2,P1) are fine. (S1,P2) is not, because S1 already has P1`
M:N	Many each way.	`M beside STUDENT, N beside PROJECT`	`Yes. All three pairs stand`

The reading rule. The label beside an entity set counts that entity set. N beside PROJECT means many projects, so one student may hold many. Read the ratio in the order the sets are named, and say it out loud as two sentences before you draw anything: one student has how many projects, and one project has how many students. M and N are two different letters because the two maxima are unrelated, not because they are equal.

Three notations are in circulation and they do not look alike. This lesson uses the Chen and Elmasri convention, which is what Indian university syllabi and placement interviews are set from: a number written beside each edge. Silberschatz writes no numbers and draws an arrowhead into the entity set that is capped at one, so an arrow into PROJECT means one project per student. Crow’s foot draws the three-pronged symbol at the end of the line touching the entity that can be many, which carries the same information as the letter N in the same position. Never read a number off a diagram without first checking which of the three you are looking at.

Participation is the second label and it sits on the same edge. A single line from the entity set to the diamond is partial: an entity of that set may appear in zero relationship instances. A double line is total: every entity of that set must appear in at least one. In W, Chetan appears in none, so STUDENT is partial. Chat App has Asha, and Solar Tracker has Asha and Bina, so PROJECT could be drawn total. Those two facts are independent of each other and independent of the M:N above them.

The question	Cardinality ratio	Participation constraint
What it asks	At most how many?	At least one, or none at all?
What it constrains	The maximum links an entity may have	The minimum links an entity must have, which is 0 or 1
Drawn as	`1, N or M beside each edge`	`single line = partial, double line = total`
On our set W	S1 has 2 links and P1 has 2, so neither maximum is 1	S3 has 0 links, so STUDENT cannot be drawn total
Change it and	you change where the data can be stored at all: a foreign key, or a whole extra table	you change whether a column may be NULL, not whether the table exists. Under 1:1 it also decides which of the two tables holds the key

Both labels turn into DDL, and the M:N case is where the relationship finally gets a place to keep its own attributes. Line 7 is the reason this table has to exist: hours is a fact about the pair, and a pair is the only thing in the schema that has one row per pair. Line 1 declares STUDENT total, and that is a ruling the college has taken rather than something W already satisfies: Chetan is on no project yet. Step 7 of the console is that same ruling being tested against the links that survived.

-- STUDENT M : N PROJECT · STUDENT total · PROJECT partialCREATE TABLE student (sid TEXT PRIMARY KEY, name TEXT NOT NULL);CREATE TABLE project (pid TEXT PRIMARY KEY, title TEXT NOT NULL);CREATE TABLE works_on (                    -- the relationship set, as a table  sid   TEXT NOT NULL REFERENCES student(sid),  pid   TEXT NOT NULL REFERENCES project(pid),  hours INT NOT NULL,                        -- a fact about the PAIR, not about either end  PRIMARY KEY (sid, pid)                     -- a set, not a bag: one link per pair);-- Make the same edge STUDENT 1 : N PROJECT and works_on disappears:--   ALTER TABLE project ADD sid TEXT REFERENCES student(sid);  -- FK on the N side--   ...NOT NULL as well, if PROJECT's participation is total-- STUDENT's own total participation has no column to mark. See section 06.

Line 8 is the line people leave out. A relationship set is a set, so (S1, P1) can hold or not hold, and cannot hold twice. Without that composite key the table is a bag, and a bag is a shape no ER diagram can describe. Lines 11 and 12 are the same edge under a different ratio: one label on a drawing is the difference between two tables and three.

There is a third notation that carries both labels at once. (min, max) writes one pair on each edge, and the pair constrains the entity set it sits beside: STUDENT (1, N) says every student takes part in at least one and at most N relationship instances. min > 0 is total participation, min = 0 is partial. It is compact, and it hides a trap. Take STUDENT 1 : N PROJECT with both sides total. In ratio form that is 1 beside STUDENT and N beside PROJECT. In (min, max) form it is STUDENT (1, N) and PROJECT (1, 1). The two maxima have swapped edges, because the ratio label counts the set it sits beside while the (min, max) label counts the instances that set takes part in. A diagram that mixes the two reads backwards, and so does a candidate who learned one and is shown the other.

Every edge carries three decisions, and an unlabelled edge has made none of them. The ratio decides whether the relationship becomes a foreign key or a table of its own. Participation decides whether that foreign key may be NULL. The role name decides what the column is called. None of the three is decoration you add at the end.

05 Cheat sheet

Every label on one card

Nine rows, and each one is a thing an interviewer can ask you to draw and then ask you to turn into a table. The last column is the half most candidates skip.

Label	What it says	Drawn as	What it becomes in tables
1:1	At most one each way.	`1 beside both edges`	One table, or a foreign key plus UNIQUE. Put the key on whichever side is total.
1:N STUDENT : PROJECT	Many projects per student, one student per project.	`1 beside STUDENT, N beside PROJECT`	A foreign key on PROJECT, the N side. Never on the 1 side.
N:1	One project per student, many students per project.	`N beside STUDENT, 1 beside PROJECT`	The same shape read from the other end, so the key goes on STUDENT.
M:N	Many each way.	`M beside STUDENT, N beside PROJECT`	Its own table holding both keys, with PRIMARY KEY (sid, pid).
Total participation	Every entity of this set appears in at least one instance.	`double line on that edge`	NOT NULL on the foreign key, but only when the key sits on that same table.
Partial participation	An entity may appear in none.	`single line, and it is the default`	Nothing to declare. This is what you get by saying nothing.
(min, max)	Both constraints, on the edge of the set they constrain.	`(1, N) beside STUDENT`	min > 0 is total. The max is the ratio, read from the opposite edge to where you expect it.
Relationship attribute	A fact about the pair, not about either end.	`an oval hanging off the diamond`	A column of the M:N table. Where else it could live depends on the ratio.
Role name	Which end of the edge this is.	`written on the edge itself`	The column name, and the only thing that makes a recursive relationship readable.

Cardinality is the maximum, participation is the minimumIf you keep one sentence from this lesson, keep that one. Every confusion in this module is one of the two answering a question that was asked of the other, and an interviewer will test it by changing one label and asking what else changed. The answer is nothing else.

Degree is an overloaded wordThe degree of a relationship is how many entity sets take part: one for recursive, two for binary, three for ternary. The degree of a relation in the relational model is how many attributes it has. Same word, different chapter. Say which you mean before the interviewer decides for you.

Where the foreign key lands1:N puts it on the N side. M:N gets a table of its own. 1:1 lets you choose, and the choice is not arbitrary: put it on the side whose participation is total, because that is the side where the column can be NOT NULL instead of mostly empty.

06 Where & why

What each label turns into on a real engine

None of these labels stays a drawing. Each one becomes a line of DDL on a system that is running right now, and an interviewer can hear the difference between a candidate who has typed them and one who has only seen the diamond.

PostgreSQL · MySQL

1:N is a column, M:N is a table

STUDENT 1 : N PROJECT becomes one column, project.sid REFERENCES student(sid), on the N side. Change that one label to M:N and the column cannot hold two values any more, so it becomes works_on(sid, pid, hours) with PRIMARY KEY (sid, pid). A single letter on a drawing is the difference between two tables and three.

Oracle · SQL Server

The double line that DDL cannot draw

Total participation is NOT NULL only when the foreign key sits on that same table. “Every student must be on at least one project” is a rule about rows that are not in the student table, and CREATE ASSERTION, the standard SQL feature that would state it directly, is implemented by none of the mainstream engines. It ends up as a trigger, a check run inside the transaction, or a nightly report somebody has to read.

SQLite · MySQL

The composite key is what makes it a set

PRIMARY KEY (sid, pid) on an M:N table is not a performance decision. It is the line that stops Asha being recorded on Solar Tracker twice with two different hour counts. A relationship set is a set; without that key the table is a bag, and a bag is a shape the diagram has no way to describe or to reject.

PostgreSQL · Oracle

Role names are literally column names

A recursive relationship maps to two foreign keys into one table: mentor_sid and mentee_sid, both REFERENCES student(sid). The role names on the diagram are the column names, which is why an unlabelled recursive edge is unreadable rather than merely untidy. Add CHECK (mentor_sid <> mentee_sid) unless a student is allowed to mentor themselves.

An edge with no numbers and no line thickness has not been designed, it has been drawn. Before you move to the next entity set, say the edge out loud in four sentences: one student has how many projects, one project has how many students, must every student have one, must every project have one. Those four answers are the whole of this lesson, and they are what turns into DDL.

07 Interview questions

What they actually ask

ER modelling is where a DBMS interview stops being definitions and starts being design. The two questions almost everyone gets asked are the difference between cardinality and participation, and how an M:N relationship becomes tables. Both are below, and so are the follow-ups that come after a confident answer.

What is a relationship set, and how is it different from a relationship instance?

A relationship instance is one tuple that picks one entity from each participating entity set, like (S1, P1) for Asha works on Solar Tracker. A relationship set is the named collection of all such tuples that hold right now: WORKS_ON = {(S1,P1), (S1,P2), (S2,P1)}. The word “set” is doing work there, because it means the same pair cannot be recorded twice.

What is the degree of a relationship?

The number of entity sets that take part. One is unary, also called recursive; two is binary; three is ternary. Almost everything you will draw is binary. Be careful with the word, because the degree of a relation in the relational model is its number of attributes, so say which one you mean before the interviewer assumes the other.

Why does a recursive relationship need role names?

Because both of its edges leave the same entity set, so nothing in the picture tells you which end is which. MENTORS on STUDENT holds ordered pairs like (S1, S3), and without the labels mentor and mentee on the two edges the diagram cannot say whether Asha mentors Chetan or Chetan mentors Asha. In SQL the role names become the two column names, because both foreign keys point at the same table and nothing else distinguishes them.

In a 1:N relationship, which side is the many side?

The side the letter N is written beside. The label beside an entity set counts that entity set, so STUDENT 1 : N PROJECT means one student and many projects: a student may hold many projects and a project has at most one student. Read the ratio in the order the sets are named, and say it as two sentences before you draw it. The same constraint written from the other end is PROJECT N : 1 STUDENT.

What is the difference between a cardinality ratio and a participation constraint?

Cardinality is the maximum and participation is the minimum. Cardinality caps how many links an entity may have; participation says whether it may have none. In WORKS_ON = {(S1,P1), (S1,P2), (S2,P1)}, Asha holding two projects is a statement about cardinality and Chetan holding none is a statement about participation. Change either label and the other is untouched.

How is total participation drawn, and what does it become in SQL?

A double line between the entity set and the diamond, meaning every entity of that set appears in at least one relationship instance. If the relationship became a foreign key on that same table, total participation is NOT NULL on that column. If the foreign key sits on the other table there is no column to mark, and it needs a trigger or a check inside the transaction, which is why total participation is the label most often drawn and least often enforced.

What is (min, max) notation and why would you use it?

It replaces both labels with one pair on each edge. STUDENT (1, N) says every student takes part in at least one and at most N relationship instances, so min > 0 is total participation and min = 0 is partial. The trap is placement: the pair counts the relationship instances that the entity set beside it takes part in, while a plain 1 or N counts the entities of the set beside it. Those are different things, so the same maximum ends up on opposite edges in the two notations.

When does a relationship need an attribute of its own?

When the fact depends on both ends and on neither one alone. Asha spends 6 hours a week on Solar Tracker and 4 on Chat App, so hours cannot sit on the STUDENT row. Bina spends 10 hours on Solar Tracker, so it cannot sit on the PROJECT row either. Under M:N there is nowhere left, so it hangs off the diamond and becomes a column of the relationship table. The test never changes: name two rows that would clash if you moved it.

Can a ternary relationship always be replaced by three binary ones?

No, and claiming otherwise is a common way to lose the question. Three binary sets record which students are on which projects, which faculty work with which students, and which faculty are attached to which projects. They do not record which of those facts happened together, so once one project has two faculty on it you can no longer tell who supervised whom on it. Replace a ternary with binaries only when you can show nothing is lost.

How does an M:N relationship become tables?

Hard

SUPERVISES is ternary over STUDENT, PROJECT and FACULTY and holds exactly {(S1,P1,F1), (S1,P2,F2), (S2,P1,F2)}. Write out the three binary projections. Then build the set of every triple whose three pairs all appear in those projections. Say how many triples you get, name the ones nobody ever recorded, and state one condition on the data that would have made the decomposition lose nothing.

Follow-up

The extra triple is not a random error. It is the exact statement the three binary diagrams have no way to deny, and it is the same failure that makes a decomposition lossy in normalisation.

Show the hint

Fix a student and a project from the first projection, then test both faculty against the other two. Six candidate triples is all there are.