The relational model and the ER-to-table recipe

A relation is a set of tuples — with names

Page 85 in four lines: the relational model was "Proposed by E. F. Codd in 1970", "Made available in commercial DBMSs in 1981"; "It is based on (a variant of) the mathematical notion of relation"; "Relations are naturally represented by means of tables". The variant adds names, nulls and constraints.

Start with four football games (p. 88): Juve–Lazio 3–1, Lazio–Milan 2–0, Juve–Roma 1–2, Roma–Milan 0–1. Each is an ordered list of four values: string, string, integer, integer.

So games \(\subseteq\) string × string × integer × integer has degree 4 and cardinality 4. Being a set, it has "no ordering between n-tuples", and "the n-tuples are distinct from one another" (p. 87). Inside a tuple, order rules: "the i-th value come from the i-th domain".

The domain string plays two roles here, home team and visitors: "Each of the domains has two roles, distinguished by means of position" — "The structure is positional" (p. 88). Swap the first two values and Juve's home win becomes Lazio's. The relational data model wants "a non-positional structure": it associates "a unique name (attribute) with each domain; it 'describes' the role of the domain" (p. 89).

With names, a tuple is a set of attribute–value pairs and the column order means nothing. In Python terms, ('Juve', 'Lazio', 3, 1) became {'HomeTeam': 'Juve', …}: a tuple became a dict.

References are values, not arrows

Page 90 draws every row of Exams as two arrows, one into Students and one into Courses, and stops there. The relational model stores no arrows: Exams holds the values that identify the student and the course, and a reference is the same value in two tables.

Values beat arrows: 3456 means something on its own, survives a copy to another system, and can be checked by a rule — the subject of section 3.

Schema and instance

Page 91 fixes the words. A relation schema is "a name (of the relation) R with a set of attributes", a database schema "a set of relation schemas with different names"; an instance is the "set r of tuples on X" a schema holds now, one relation per schema for a database:

The schema is stable; the instance changes with every insert.

Nulls, constraints and keys

The structure is rigid (p. 92): "information is represented by means of tuples" and "tuples have to conform to relation schemas". What goes into a cell when there is no value? A null, of "(at least) 3 types" (p. 93):

The line to remember: "DBMSs do not distinguish between the types: they implicitly adopt the no-information value". SQL has one NULL — which is why NULL = NULL is not true there and you write IS NULL.

Constraints are predicates

An integrity constraint is "a property that must be satisfied by all meaningful database instances"; seen "as a predicate", an instance "is legal if it satisfies all integrity constraints" (p. 94). Intrarelational constraints stay in one relation — domain constraints check one value (a grade between 18 and 30), tuple constraints one tuple (honours only with a 30); interrelational ones span several relations. Keys are intrarelational, referential constraints interrelational.

Superkeys and keys

A key is "a set of attributes that uniquely identifies tuples in a relation"; p. 95 makes it precise in two steps.

Page 96 tries it on five students:

"RegNum is a key": five different values, and one attribute is minimal by force. The second claim, "Surname, Firstname, BirthDate is another key", takes four checks:

1. Superkey? The five (Surname, FirstName, BirthDate) triples are all different: no two distinct tuples agree on them.

2. Drop BirthDate. (Black, Lucy) occurs in 934856 and 965536: {Surname, FirstName} is not a superkey.

3. Drop FirstName. (Smith, 29/04/59) occurs in 284328 and 296328: not a superkey.

4. Drop Surname. (Lucy, 01/05/61) occurs in 587614 and 934856: not a superkey.

5. Minimal. Smaller subsets lie inside these pairs, and tuples that agree on a set agree on its subsets. "no proper subset is also a superkey" (p. 96): a key.

The same test on {FirstName, BirthDate, DegreeProg} finds five different triples and only repeated pairs: on this instance, a key nobody would declare. Hence p. 97: constraints "correspond to properties in the real world", so "they are relevant at the schema level", and "individual instances could satisfy ('by chance') other constraints". An instance can refute a key, never prove one.

"The presence of nulls in keys has to be limited", so "for each relation we select a primary key on which nulls are not allowed"; it is underlined, and "References between relations are realized through primary keys" (p. 98). A key with a null could neither tell its tuple apart nor be pointed at.

A key is a minimal set of attributes that never takes the same value twice in a legal instance; the primary key is the one chosen, underlined, never null.

Referential constraints: every value must find its row

Values link the tables — "Pieces of data in different relations are correlated by means of values of (primary) keys" — so nothing physical stops a value from pointing nowhere. "Referential integrity constraints are imposed in order to guarantee that the values refer to actual values in the referenced relation" (p. 99).

The slides' example (p. 100) is a database of traffic offences from 1992: Offences(Code, Date, Officer, Dept, Registration), Officers(RegNum, Surname, FirstName) and Cars(Registration, Dept, Owner). Look at the key of Cars: plate 6544 XY appears twice, with Dept 75 (Cordon Edouard's car) and with Dept 47 (Mimault Bernard's). The plate alone does not identify a car; the pair (Registration, Dept) does.

Two features of the definition are easy to miss. It is directional: every offence must find its officer, but Officers may hold an officer whom no offence names — 638, Larue Jacques, is perfectly legal. And with a composite key it is checked on the pair as a whole: offence 630876 points at (6544 XY, 47), Mimault's car, and (6544 XY, 75) is another car altogether. Note too that the referencing attribute needs neither the key's name (Officer refers to RegNum) nor unique values (456 appears in three offences).

In SQL, which you know, the two constraints of p. 101 are two clauses of one statement; the composite one needs the FOREIGN KEY (…) REFERENCES … form:

-- p. 101 in SQL: Offences must find its officer and its car
CREATE TABLE Offences (
  Code         CHAR(6) PRIMARY KEY,
  Date         DATE,
  Officer      CHAR(3) REFERENCES Officers (RegNum),
  Dept         CHAR(2),
  Registration CHAR(7),
  FOREIGN KEY (Registration, Dept)
    REFERENCES Cars (Registration, Dept)
);

Keep the direction and the "pair as a whole" in mind. Several systems later in this course store such references without checking them, and then your application has to.

From diagram to tables: Step 1 and the two rules

Pages 102–118, "ER to Relational — Quick summary", are a recipe. Step 1 handles the entities (p. 103): "Create a separate table to represent each entity in the conceptual model" — "1A: Each attribute of the entity becomes a column in the relational table", "1B: Each instance of the entity set will become a row in the relational table". The identifier, the filled circle of the diagram, becomes the primary key: Sale(SaleID, Date, Amount).

Entities are the easy part. A relationship can live in two places: in a separate table whose rows are the links, or as a posted foreign key — a column added to one entity's table that holds the key of the other ("post" is the slides' verb; the asterisk marks such a column: Sale(SaleID, Date, Amount, Cust-ID*)). Page 103 names the two criteria that choose:

• "Redundancy = one fact in multiple places or multiple facts in one place";
• "Load = the percentage of non-null values in a column";

and where to read them: "Participation Cardinalities communicate some of the information regarding redundancy and load".

Page 104 turns the criteria into two rules, one per number of the (min,max) pair:

Why two rules of different strength? Read them as questions about the foreign-key cell of each row. The maximum asks how many partners a row can have. If more than one, one cell cannot hold them: you would need a list in a cell, a repeating group — "multiple facts in one place", the second kind of redundancy of p. 103. A list is not an atomic value, so the table stops being a relation: that rule cannot bend. The minimum asks whether every row has a partner. If it is 0, some cells stay empty: nulls, a lower load. That costs space and care, but the table is still a relation, so this rule may bend.

The maximum decides where a foreign key may live; the minimum decides whether its cells can be empty.

Step 2: many-to-many always gets its own table

Step 2 (p. 105) covers the four patterns (0,N)-(0,N), (0,N)-(1,N), (1,N)-(0,N), (1,N)-(1,N): "You must create a separate table to represent the relationship"; "The primary keys of the related entity tables are posted into the relationship table to form its primary key. This kind of primary key is called a composite or concatenated primary key" — and "There are no exceptions to this rule!!!".

Both maxima are N, so the maximum rule closes both entity tables; what is left is a table whose rows are the links. Its key is the pair because the pair identifies the link: a student takes a given course once. Note the crossed-out column: an array of course ids inside the student is exactly how a document database stores this relationship (lesson 13). What the relational model forbids, MongoDB allows on purpose.

Step 3: (1,1)-(1,1), one direction only

For the pattern (1,1)-(1,1), Step 3 (p. 108) first asks a design question: "consider whether the two entities are conceptually separate or whether they should be combined". If they stay separate: "3A: Post the primary key from one entity's table into the other entity's table as a foreign key", "3B: It doesn't matter which entity's primary key is posted into the other entity's table, but DO NOT post both", "DO NOT make a separate table". Page 109 shows Sale (1,1) — yield — (1,1) Cash Receipt both ways, CR-ID* in Sale or S-ID* in Cash Receipt: "Choose ONE of these; DO NOT do both!!!".

Why is the direction free? Both maxima are 1 and both minima are 1, so in either table every cell gets exactly one value: load 100 %, no list. Why not both? Then every link is stored twice — one fact in two places, two copies that can disagree. And a separate table would only repeat the two keys row by row.

Steps 4 and 5: the (1,1) side takes the key, otherwise load decides

Step 4 (p. 110): "For remaining relationships that have (1,1) participation by one entity set, post the related entity's primary key into the (1,1) entity's table as a foreign key" — six patterns: (0,N)-(1,1), (1,N)-(1,1), (1,1)-(0,N), (1,1)-(1,N), (0,1)-(1,1), (1,1)-(0,1). "Do NOT make a separate table". "Post a foreign key INTO the (1,1) entity's table from the other entity's table". And the warning that explains the hook: "If you post the opposite direction, either redundancy [for N maximums] OR load [for 0 minimums] will be a problem".

Page 111 is the hook's case: Sale (1,1) — Is-to — (0,N) or (1,N) Customer. Cust-ID* in Sale holds C1, C2, C1, one value per row. The other way both failures arrive at once: Heather's cell needs "S1, S3", Dave's stays empty. Page 112 isolates the second failure: Sale (1,1) — yields — (0,1) Cash Receipt. CR-ID* in Sale is full; S-ID* in Cash Receipt leaves CR4 empty — a receipt of $1,000 that comes from no sale.

Step 5: when only (0,1) sides are left

Step 5 (p. 113) takes the five remaining patterns: (0,N)-(0,1), (1,N)-(0,1), (0,1)-(0,N), (0,1)-(1,N), (0,1)-(0,1). Now no table satisfies both rules. The maximum rule leaves two options: "posting into a (0,1) or making a separate table; you CANNOT post into the (0,N) or (1,N)". The minimum rule objects to the first, because it "will create null values that waste valuable space in the database" — "However, if a separate table would waste more space, then it is better to follow the maximum rule and break the minimum rule". Load breaks the tie:

• "5A: Post the related entity's primary key into the (0,1) entity's table as a foreign key for any relationships for which that results in a high load";
• "5B: Create a separate table for any relationships for which posting a foreign key results in low load";
• "Note: For (0,1)-(0,1), step 5A, post whichever direction results in highest load; if neither direction yields high load, then follow step 5B".

The worked example (pp. 114–115) has 18 purchases, 26 cash disbursements and a few purchase returns. "pays for" is Purchase (0,1) — (0,1) Cash Disbursement: "Most purchases (14/18) result in cash disbursements", so Check# posted into Purchase is non-null in 14 rows of 18 — "a high load", "Worth breaking the minimum rule" — and the slide concludes: post Check# into Purchase. "allowance for" is Purchase (0,1) — (1,N) Purchase Return: "Few purchases (3/18) result in purchase returns" — "low load"; the other direction is closed by the maximum rule, "because one purchase return slip # can be associated with multiple purchases". "Conclusion: Make a separate table to represent the 'allowance for' relationship". Its rows are the three links; since a purchase has at most one return, Receiving Report# alone is its key (not on the slides; the widget below underlines it).

Relationship attributes travel with the link

Page 116 adds the last piece: "If relationship becomes a separate table, then relationship attributes are placed in that table"; "If relationship can be represented by a posted foreign key, relationship attribute is posted alongside the foreign key". A relationship attribute describes one link, so it lives where the link lives: a grade on TAKES goes into TAKES(Student#, Course#, Grade). In the exam of 12 September 2025, Animal (1,1) — House — (1,N) Farm carries a Housing Date: it goes into Animal next to the posted key, Animal(Tag, Name, Age, AnimalType, Breed, FarmName*, HousingDate). It can never go to the N side: a farm houses many animals, so which animal's housing date would the farm's one cell hold?

One fact in many places: the diagram was wrong

Page 117 ends the section with a diagnosis: an Employee table (EmpID, EmpName, Payrate, Hours Worked, Dept#, DeptName) and five questions: "What facts are in multiple places in this table?", "Reverse engineer to get the ER model that this table must represent", "Is the ER model that results in this table correct?", "What SHOULD the ER model have been instead?", "What is the correct relational model?"

The answers, in order. The facts in multiple places are "D423 is called Audit" (Andy's and Jennifer's rows) and "D821 is called Tax" (Craig's and Steven's) — the first kind of redundancy of p. 103. Reverse engineering the table gives one entity, Employee, with Dept# and DeptName among its attributes. That model is wrong: a department is a thing of its own, with its own identifier, and its name is a fact about the department. The model should have been Employee — Assigned to — Department (p. 118), and Step 4 then posts Dept# into Employee.

Why it matters: rename Audit and you must edit two rows — miss one and the table contradicts itself; a department with no employee cannot be recorded at all; delete Arlie and the fact that D777 is ISAAS disappears with that row. A correct ER gives tables in which every non-key column describes the thing its row stands for, so one fact in many places is the fingerprint of a wrong ER. Lesson 9 gives the same diagnosis a name: DeptName depends on Dept#, which is not the key — a transitive dependency — and the split of p. 118 is the step to third normal form.

Now the hook. Design B is not a relation: Heather's cell holds a list of sales, a repeating group, forbidden because Customer's maximum is N — and Dave's cell is NULL because Customer's minimum is 0. Design C is a legal relation, but Step 4 says "Do NOT make a separate table" when one side is (1,1). Design A is the slides' answer: Sale is (1,1), so Cust-ID* holds exactly one value in every row, load 100 %. Two pairs on the diagram decided it.