The relational model, keys and ER-to-table mapping
Relation, schema, instance, domain; super/candidate/primary/foreign key; referential integrity and the rules for turning an ER diagram into tables. Both the algebra and the SQL questions rely on these tables.
The ER diagram was the design on paper. The relational model is its counterpart in the computer: everything is a table. This week you learn two things. The first is terminology and keys; relational algebra, SQL and normalization are built on these concepts, and you cannot get through week 9 without knowing what a candidate key is. The second is the rules for converting ER to tables; almost every year the midterm has a “convert this diagram into relation schemas” question.
Golden rules:
- The schema is fixed, the instance varies. Constraints belong to the schema.
- A key must be minimal. If it has an extra attribute, it is a superkey, not a candidate.
- An FK requires that the row it references exists. The value either equals a real PK or is NULL.
- M:N is always a separate table. 1:N becomes a column on the N side.
Terminology
In the relational model, data lives in tables. By its mathematical name a table is a relation, a row is a tuple and a column is an attribute. The student relation we use in the course:
| stu_id | name | dept_name | tot_cred |
|---|---|---|---|
| S1 | Ada | CS | 60 |
| S2 | Bora | CS | 30 |
| S3 | Cem | EE | 45 |
| S4 | Defne | MATH | 90 |
| S5 | Ece | CS | 15 |
| S6 | Firat | EE | 0 |
| S7 | Gizem | NULL | 10 |
- Domain: the set of values an attribute may take. For
tot_cred, non-negative integers. - Atomicity: a single, indivisible value in each cell. Writing “555-0101, 555-0102” in one cell breaks the relational model; this is the basis of 1NF (week 9).
- NULL: the value is unknown or does not exist. S7’s department is not known yet.
- Degree: the number of attributes, here 4. Cardinality: the number of tuples, here 7.
A relation is a set: rows have no order and there cannot be two identical rows. The order of columns is also unimportant in theory, because attributes are referred to by name.
Schema and instance
A relation schema is the structure of the relation: student(stu_id, name, dept_name, tot_cred). A relation instance is the rows at a given moment. The programming counterpart: the schema is the variable type, the instance is the current value of the variable. When Ada graduates, the instance changes and the schema stays the same.
The schemas we use throughout the course:
department (dept_name, building, budget)
instructor (inst_id, name, dept_name -> department, salary)
student (stu_id, name, dept_name -> department, tot_cred)
course (course_id, title, dept_name -> department, credits)
teaches (inst_id -> instructor, course_id -> course)
takes (stu_id -> student, course_id -> course, grade)Since we cannot underline here, the primary key is the first column(s); for teaches and takes the first two columns together. The arrow -> shows what a foreign key points to. In a schema diagram, each table is a box, the PK is underlined, and FKs are connected by arrows to the PK of the table they reference.
Keys
Superkey: a set of attributes whose values identify every row uniquely. For student, {stu_id}, {stu_id, name} and {stu_id, name, dept_name, tot_cred} are all superkeys.
Candidate key: a minimal superkey, that is, one from which no attribute can be removed. {stu_id} is a candidate; {stu_id, name} is not, because it is still a key after dropping name.
Primary key: the one the designer chooses among the candidate keys. A relation may have more than one candidate key (a student number and a national ID number); you pick one as the PK and put UNIQUE on the other.
Foreign key: one or more attributes in a relation that reference the PK of another (or the same) relation. takes.stu_id → student.stu_id. The referencing side is the referencing relation, the other is the referenced relation.
Reading keys from an instance
You can check with SQL whether a set has repeats in the instance:
SELECT stu_id, course_id FROM takes
GROUP BY stu_id, course_id HAVING COUNT(*) > 1; -- empty: no repeats
SELECT stu_id, grade FROM takes
GROUP BY stu_id, grade HAVING COUNT(*) > 1; -- 3 groups repeat(first query: no rows)
S1 | A
S1 | B
S4 | APITFALL · instance data does not prove a key.
namehas no repeats among the current 7 students, but it is not a key: a second “Ada” may register. An instance gives only negative proof:dept_namehas repeats (CS three times), so it is definitely not a key. In the exam, watch the difference between “this instance” and “the schema”.
Counting superkeys
A set of attributes is a superkey if it contains at least one candidate key. For R(A, B, C, D), if the only candidate key is {A}, the other three attributes can be added freely: superkeys. If there are two candidate keys {A} and {B, C}, apply inclusion-exclusion:
The last term is the sets that contain both A and B,C: {A,B,C} and {A,B,C,D}.
Integrity constraints and referential integrity
- Entity integrity: the PK value cannot repeat and cannot be NULL.
- Referential integrity: an FK value is either NULL or a PK value that actually exists in the referenced table.
What we tried on the sample database with PRAGMA foreign_keys = ON:
| Operation | Result | Why |
|---|---|---|
INSERT INTO takes VALUES ('S9','CS101','A') | rejected | there is no student S9 |
INSERT INTO instructor VALUES ('I7','Ozturk','PHYS',65000) | rejected | there is no PHYS department |
INSERT INTO student VALUES ('S8','Hakan',NULL,0) | accepted | an FK may be NULL |
INSERT INTO student VALUES ('S1','Zeynep','CS',0) | rejected | duplicate PK |
DELETE FROM department WHERE dept_name='CS' | rejected | instructors, students and courses reference CS |
| Deleting S5’s takes rows, then deleting S5 | accepted | nothing references it any more |
What happens when a referenced row is deleted is chosen in the FK definition: the default NO ACTION/RESTRICT rejects it, ON DELETE CASCADE deletes the referencing rows too, and ON DELETE SET NULL sets the FK to NULL.
PITFALL · SQLite and NULL primary keys. In standard SQL a PK can never be NULL. Because of a historical bug, SQLite accepts NULL in a
TEXT PRIMARY KEYcolumn (tried in the verification run); if you addNOT NULL, it rejects it. Also, in SQLite FK checking is off by default andPRAGMA foreign_keys = ONis needed. PostgreSQL and MySQL (InnoDB) enforce these on their own.
Rules for converting ER to a relational schema
| ER construct | How it becomes tables |
|---|---|
| Strong entity | Its own table; simple attributes become columns, the key becomes the PK |
| Composite attribute | Only the leaf parts become columns: name → first_name, last_name |
| Multivalued attribute | Separate table: inst_phone(inst_id, phone), PK is both, inst_id is an FK |
| Derived attribute | No column (computed with a view if needed) |
| Weak entity | Table; the owner’s PK is added as an FK, PK = owner PK + discriminator |
| Identifying relationship | No table, it is already in the weak entity’s table |
| 1:N relationship | The PK of the “1” side as an FK column on the N side; the relationship attributes go to the N side too |
| Total participation (N side) | That FK column is NOT NULL |
| 1:1 relationship | FK + UNIQUE on one side (preferably the side with total participation), or a separate table |
| M:N relationship | Separate table: both PKs + relationship attributes, PK = combination of both PKs |
| n-ary (ternary) relationship | Separate table: the PKs of all participants |
Worked example
Scenario: department; instructor (composite name, multivalued phone, N:1 total to department); student (one advisor instructor, 1:N); course; section (weak entity of course); takes (M:N between student and section, grade); dean (1:1 between department and instructor, to be kept in a separate table).
department (dept_name, building)
instructor (inst_id, first_name, last_name, dept_name -> department NOT NULL)
inst_phone (inst_id -> instructor, phone) PK: both
student (stu_id, name, advisor_id -> instructor)
course (course_id, title)
section (course_id -> course, sec_id, semester, year) PK: all four
takes (stu_id -> student, course_id, sec_id, semester, year, grade)
PK: the first five ; FK (course_id, sec_id, semester, year) -> section
dean (dept_name -> department, inst_id -> instructor UNIQUE) PK: dept_nameThat makes 8 tables. We built the schema in SQLite and tried it: a registration for a non-existent section was rejected because of the composite FK, making the same instructor dean of two departments was rejected because of UNIQUE, an instructor without a department was rejected because of NOT NULL, and when a course was deleted its sections went away through CASCADE.
Note: since takes is tied to a section, its FK is a composite key with four columns. An FK must contain all columns of the PK it references; you cannot link only course_id to section.
Three ways for specialization
person(pid, name) → student(tot_cred), employee(salary):
| Method | Tables | When |
|---|---|---|
| 1. Super + sub tables | person(pid, name), student(pid, tot_cred), employee(pid, salary) | Works in every case; the pid of the sub-tables is an FK to person |
| 2. Only sub tables | student(pid, name, tot_cred), employee(pid, name, salary) | Only if total and disjoint |
| 3. Single table | person(pid, name, ptype, tot_cred, salary) | If there are few subsets; unrelated columns are NULL |
Method 2 stores the same person’s name twice when overlapping, and cannot store a person who is in no subset when partial.
Common mistakes
| Wrong idea | The truth |
|---|---|
| Degree = number of rows | Degree is columns, cardinality is the number of rows |
| {stu_id, name} is a candidate key | It is a superkey; not minimal |
| No repeats in the instance, so it is a key | The constraint belongs to the schema; an instance can only refute |
| An FK cannot be NULL | It can; a PK cannot |
| The FK must have the same name | The name is free (advisor_id → inst_id); type and value must match |
| Put the M:N relationship as a column on one side | A separate table is required |
| In 1:N, put the FK on the “1” side | On the N side; otherwise one cell would need many values |
| Write the multivalued phone in one column with commas | Atomicity breaks; use a separate table |
| The PK of a weak entity is just the discriminator | Owner PK + discriminator |
| In 1:1 an FK is enough | FK + UNIQUE; otherwise it becomes 1:N |
Test yourself
Exam-style questions. Solve them on paper first, then reveal the answer.
What are the degree and the cardinality of the student relation in the sample database?
Show answer
Degree = number of attributes: stu_id, name, dept_name, tot_cred → 4. Cardinality = number of rows (tuples): S1 to S7 → 7. Do not mix them up: the degree depends on the schema, the cardinality on the instance.
In student(stu_id, name, dept_name, tot_cred), stu_id is the primary key. Is {stu_id, name} a superkey? Is it a candidate key?
Show answer
stu_id already identifies every row uniquely; whatever you add next to it is still unique: a superkey. A candidate key must be minimal. When you remove name, the remaining {stu_id} is still a key, so {stu_id, name} is not minimal.
In the current student instance no two students have the same name. Can we declare name a candidate key?
Show answer
A key is a constraint of the schema and must hold for all future valid instances. A second "Ada" may register tomorrow. In the verification run name was unique in this instance, but that is a coincidence. Instance data can only show that something is not a key (dept_name has repeats, so it cannot be a key).
What is the primary key of takes(stu_id, course_id, grade)? Explain why neither attribute alone works.
Show answer
stu_id repeats (S1 is in four rows) and course_id repeats (CS101 is in four rows). The pair (stu_id, course_id) is unique in the instance, and the business rule is "a student takes a course once". Adding grade is unnecessary, and (stu_id, grade) repeats (S1 has two A grades).
A relation R(A, B, C, D) has exactly two candidate keys: {A} and {B, C}. How many superkeys does R have?
Show answer
Subsets that contain A: the remaining B, C, D are free → 2^3 = 8. Those that contain {B,C}: A and D are free → 2^2 = 4. Those that contain both ({A,B,C} and {A,B,C,D}) were counted twice → 2. Inclusion-exclusion: 8 + 4 − 2 = 10.
With foreign keys enforced, which statement is rejected?
- INSERT INTO student VALUES ('S8','Hakan',NULL,0)
- INSERT INTO takes VALUES ('S9','CS101','A')
- INSERT INTO takes VALUES ('S6','BI100',NULL)
- UPDATE student SET tot_cred = 20 WHERE stu_id = 'S7'
Show answer
takes.stu_id references student.stu_id (foreign key). There is no student named S9: referential integrity violation. Inserting a student whose dept_name is NULL is allowed, because an FK value may be NULL. S6 and BI100 both exist. tot_cred is not a key.
What happens to DELETE FROM department WHERE dept_name = 'CS'; if foreign keys are enforced with the default action?
Show answer
The default behavior (NO ACTION / RESTRICT) does not allow deleting a referenced row. CS is referenced by I1, I2 (instructor), S1, S2, S5 (student) and CS101, CS201, CS305 (course). If you want to delete it, you must first delete those, or define the FK with ON DELETE CASCADE / SET NULL.
Map the M:N relationship takes between student(stu_id, ...) and course(course_id, ...) with relationship attribute grade to a relation schema. Give the primary key and the foreign keys.
Show answer
An M:N relationship always becomes a separate table. The columns are the primary keys of both sides + the attributes of the relationship. The primary key is the combination of the keys of both sides; each one is an FK to its own table.
Map the weak entity set section (discriminator: sec_id, semester, year; attribute room) owned by course(course_id, ...).
Show answer
The table of a weak entity takes the PK of the owner as an FK. PK = owner PK + discriminator. The identifying relationship (sec_course) does not become a separate table; its information is already in the course_id of section. Since a section is meaningless once its owner is deleted, the FK is usually defined with ON DELETE CASCADE.
An ER design has the strong entities department, instructor (composite name, multivalued phone), student and course; the weak entity section (owner course); the relationships inst_dept (N:1, instructor total), advisor (1:N, instructor to student), takes (M:N between student and section) and dean (1:1 between department and instructor). Fold every 1:N / N:1 relationship into the N side, but keep dean as its own table. How many tables do you get?
Show answer
Entities: department, instructor, student, course, section → 5. The multivalued phone → inst_phone → 6. The M:N takes → 7. dean as its own table → 8. inst_dept goes into instructor as a dept_name NOT NULL column (total participation means NOT NULL). advisor becomes an advisor_id column in student. sec_course is represented by the course_id in section. The composite name is split into columns (first_name, last_name) and adds no table. The schema was built in SQLite and 8 tables were counted.
In the design above, dean is a 1:1 relationship between department and instructor stored as dean(dept_name, inst_id). Which constraints make it truly 1:1?
Show answer
dept_name PK: a department has at most one dean. inst_id UNIQUE: an instructor is the dean of at most one department. If you add only one of them, the relationship becomes 1:N. In the verification run, making the same instructor dean of a second department was rejected because of UNIQUE.
person(pid, name) is specialized into student(tot_cred) and employee(salary), and the specialization is total and disjoint. Which mapping uses the fewest tables without NULL columns, and why is it unsafe if the specialization were overlapping?
Show answer
Method 1: person + one table per subset (3 tables, the sub-tables have pid as an FK to the superset). Method 2: only the subsets, each copying the superset attributes (2 tables). Method 3: a single table + a type column (1 table, but unrelated columns are NULL). If the specialization is total and disjoint, method 2 keeps each person in exactly one table, with no NULLs. If it were overlapping, the name of a person who is both student and employee would repeat in two tables and could become inconsistent; if it were partial, a person in no subset could not be stored anywhere.
Verification: The sample university database was built with node:sqlite. Key claims were checked with GROUP BY ... HAVING COUNT(*) > 1, FK violations with real INSERT/DELETE under PRAGMA foreign_keys=ON, superkey counts with JS subset counting, and the ER mappings by building the schema in SQLite and counting the tables (verify/SEN2104/03.mjs, 32 checks).