Part I — Database Fundamentals and Relational Theory

Chapter 2. Relational Data Model

Chapter 1 introduced databases as organized, shared collections of data and the DBMS as the software that manages them. This chapter opens the black box far enough to see the structure that most modern databases share: the relational data model. The model is small — a handful of definitions and properties — but everything else in this book, from SQL to normalization to query optimization, is built on it. If you learn one chapter's definitions perfectly, make it this one.

The relational model is a theory of data, published by E. F. Codd in 1970, and only afterwards turned into products. That order matters: because the model is mathematical, it comes with precise notions of correctness (integrity), a query language with provable power (relational algebra, Chapter 3), and a discipline for designing structures (normalization, Chapter 7). We introduce the model abstractly first, then map it onto the tables, rows, and columns you will actually type into PostgreSQL and MySQL.

After studying this chapter you will be able to:

• State the three parts of the relational model: structure, manipulation, and integrity.
• Define relation, tuple, attribute, and domain precisely, and use the terms interchangeably with table, row, and column where safe.
• Distinguish a relation schema from a relation instance, and use degree and cardinality correctly.
• List the properties every relational table satisfies and explain the deliberate departures SQL takes from the pure model.
• Explain what NULL means, why it is not zero or empty string, and predict which rows a NULL-involved condition keeps.
• Define superkey, candidate key, primary key, and foreign key, and identify each in the university schema.
• Weigh the relational model's advantages against its known limitations.

2.1 Fundamentals of the relational model

A data model is a combination of three things: a set of structural concepts for describing data, a set of manipulative operations for querying and changing it, and a set of integrity rules the data must obey. The relational model's three parts are:

• Structure. All data — application data and metadata alike — are represented as relations: tables whose columns are typed attributes.
• Manipulation. Queries are expressions built from a small algebra of operations on whole relations (Chapter 3); SQL is its practical descendant.
• Integrity. Two model-level rules — entity integrity (rows of a relation are identifiable by primary keys) and referential integrity (references between relations must point at existing rows) — plus application-specific constraints.

Codd's insight was to make the structure trivially simple — just tables — while making the manipulation mathematically rigorous. Pre-relational systems (hierarchic and network databases) stored the navigation paths between records inside the data; the relational model stores only values and declares relationships as column values, so that connections between tables are computed by queries rather than hard-wired in storage. This is also why the model could survive enormous changes in hardware underneath it.

The model is deliberately value-based: a row in enrollment is connected to a row in student not by a pointer but by carrying the value 21100003 in its student_id column. Everything that looks like linking, nesting, or referencing in a relational database is, at bottom, matching values across columns — a fact you will use in every join you ever write.

2.2 Relations, tuples, attributes, and domains

Formally, let D1, D2, ..., Dn be domains: sets of atomic values of the same type (the set of integers; the set of character strings of length ≤ 60; the set of allowed letter grades). The Cartesian product D1 × D2 × ... × Dn is the set of all ordered lists (v1, v2, ..., vn) with vi in Di. A relation R is a subset of that product — a set of tuples, each an ordered list of values drawn from the domains.

The everyday names map directly:

Three properties of tuples deserve emphasis. First, each tuple of a relation is distinct — a relation is a set of tuples, so duplicates cannot occur. Second, attributes are identified by name, and attribute names within one relation must be unique; the ordering of attributes in the pure model is irrelevant, because you always refer to student.gpa, never to "the sixth column." Third, every attribute draws values from one domain, but two different attributes may share a domain: enrollment.student_id and enrollment.section_id are both integers, but they are different attributes with different meanings, and student.student_id shares its domain with enrollment.student_id precisely so the two can be compared and joined.

Domains are not just types; they can carry constraints. The domain of enrollment.grade is not merely "strings of length 2" but "strings of length 2 drawn from {A+, A, A-, B+, B, B-, C+, C, C-, D, F} — or no value at all." SQL approximates this with the type plus a CHECK constraint, as the university schema does.

2.3 Relation schemas and instances

A relation schema is a named header: the relation's name plus a list of attribute–domain pairs, written R(A1: D1, A2: D2, ..., An: Dn). The schema of our running example's relation is:

student(student_id: integer, full_name: varchar(60),
        major_dept_id: integer, admission_year: smallint,
        total_credits: integer, gpa: numeric(3,2))

A relation instance (often just "the relation" in casual speech) is the set of tuples actually present at a given moment. The schema is the intension — the stable meaning; the instance is the extension — the changing content. Today the student instance has 12 tuples; at the end of registration next week it may have 14; the schema is untouched by either change.

Two measures describe an instance. The degree (or arity) of a relation is the number of attributes — student has degree 6, enrollment degree 3. The cardinality is the number of tuples — 12 for student, 28 for enrollment in the canonical dataset. Degree changes rarely (schema evolution, Chapter 9); cardinality changes constantly.

A database schema is the set of all relation schemas, plus constraints, plus other structures (indexes, views). A database instance is the corresponding set of relation instances at a moment in time. When a DBMS answers the query "how many students are enrolled in Fall 2026 sections?", it reads one instance; when it refuses an insert because student_id 999 does not exist, it enforces the schema.

2.4 Tables, rows, and columns

SQL realizes the relational model imperfectly. The mapping is close enough that practitioners use the terms interchangeably, but the differences are real, they appear in interviews and in real bugs, and this book keeps them visible:

The duplicate-row concession is the most famous. When you write SELECT major_dept_id FROM student; you get twelve rows including repeats — four 1s — because SQL tables are multisets (bags) unless you ask for set semantics. The bag semantics is a performance decision: discarding duplicates costs a sort or hash, and SQL leaves that choice to you. Chapter 10 shows DISTINCT; here the lesson is conceptual: SQL is based on the relational model, not identical to it.

Column ordering is the quieter concession. In pure relational algebra, student and student with attributes permuted are the same relation; in SQL, the column list of CREATE TABLE fixes a position for each column, which INSERT INTO student VALUES (...) relies on. Professional practice never exploits ordering — always name your columns — precisely so your SQL stays as relational as the language allows.

2.5 Properties of relational tables

Whether pure or SQL, a well-formed relational table satisfies these properties:

1. Cells hold single, atomic values. No repeating groups, no nested tables inside a cell. This is the structural half of First Normal Form (Chapter 7). If a student has two majors, the pure solution is a second row or a second relation — not a comma-separated list in one cell.
2. Every column has a distinct name and one domain. All values of gpa are drawn from the same domain; comparing gpa to room is nonsense even where the DBMS would permit it.
3. Row order is insignificant. A table is a set; no row is "first." Any order you need — a dean's report by GPA — is imposed at output time by ORDER BY, never by storage. Students are sometimes surprised that the same query can legally return rows in different orders on different days; the surprise dissolves once row order is understood to mean nothing.
4. Column order is insignificant (in the model; SQL fixes one for display).
5. Rows are (ideally) unique — no duplicate tuples. Uniqueness is normally guaranteed by declaring a key.
6. A row's values identify it as a real-world fact. One row of student is one student's current record — not a display artifact, not a copy. This is what makes constraints meaningful: refusing a duplicate student_id protects the one-fact-per-student invariant.

These properties are not stylistic preferences. Each one exists to make the algebra of Chapter 3 closed and predictable: operations accept tables and produce tables, without special cases for "the third cell of this row is secretly a list."

2.6 NULL values and missing information

Real data has holes: a grade not yet awarded, a room not yet assigned. The relational model, and SQL after it, represent a missing value with NULL — not zero, not the empty string, not "N/A", but a marker meaning value unknown or absent. Zara Hossain, admitted in 2026, has gpa NULL: she has completed no credits, so no GPA exists yet.

NULL propagates through arithmetic (NULL + 1 is NULL) and turns comparisons into three-valued logic. The expression gpa > 3.80 evaluates to TRUE, FALSE, or UNKNOWN, and UNKNOWN behaves differently in different clauses:

• In WHERE, a row is kept only when the condition is TRUE. Both FALSE and UNKNOWN rows are discarded — so WHERE gpa > 3.80 correctly returns two students (Sadia Afrin, Arif Mahmud) and silently also discards Zara, whose comparison was UNKNOWN.
• In CHECK constraints, UNKNOWN passes (the constraint is "not violated").
• In NULL-aware contexts, use IS NULL / IS NOT NULL, which are two-valued by design.

SELECT student_id, full_name, gpa
FROM   student
WHERE  gpa IS NULL;

 student_id |  full_name   | gpa
------------+--------------+------
   21600001 | Zara Hossain | (null)

The two counting functions make the NULL semantics vivid and will return in Chapter 11: COUNT(*) counts rows (12), while COUNT(gpa) counts non-NULL values (11). Aggregates like AVG, SUM, MIN, and MAX ignore NULLs entirely — the university's average GPA is computed over 11 students, not 12.

Treat NULL as a design decision, not a default. Declare columns NOT NULL wherever a value is genuinely always known (full_name), and permit NULL only where absence is meaningful (grade before the semester ends). Chapters 7 and 10 return to NULL's traps — the most famous being that NOT IN against a list containing NULL returns no rows at all.

2.7 Keys and relational constraints

A key is a set of attributes whose values identify a tuple. Formally:

• A superkey is any attribute set that uniquely identifies tuples in every legal instance. For student, {student_id} is a superkey; so is {student_id, full_name} — it is a superkey, just a bloated one.
• A candidate key is a minimal superkey: remove any attribute and uniqueness breaks. {student_id} is a candidate key; {student_id, full_name} is not (student_id alone already suffices). Candidate keys are the identity the real world offers; a relation may have several — department has both dept_id and dept_name.
• The primary key is the candidate key the designer designates as the official identifier. PostgreSQL and MySQL enforce its uniqueness and (in practice) require it NOT NULL. department.dept_id is primary; dept_name, also unique, is an alternate key, declared in SQL as UNIQUE.
• A composite key is a candidate key with more than one attribute. enrollment has exactly one: (student_id, section_id) — one row per student per section, which also encodes the business rule "a student takes a section at most once."
• A foreign key is an attribute set in one relation that must equal the primary key (or a candidate key) of some tuple in another (or the same) relation. enrollment.student_id references student.student_id; enrollment.section_id references course_section.section_id.

Two model-level integrity rules follow directly:

• Entity integrity: a primary key must be unique and entirely non-NULL. Half a NULL key would be half an identity — the model forbids it.
• Referential integrity: a foreign-key value must either match an existing referenced key or be NULL (if the reference itself is optional). Insert an enrollment for student 99999 and PostgreSQL rejects it: violates foreign key constraint — the database refusing to record a lie.

A last distinction worth fixing now: natural keys are attributes the world already supplies (a national ID), while surrogate keys are system-generated stand-ins (dept_id 1..5) with no meaning outside the database. The canonical schema uses surrogate integer keys everywhere for determinism; Chapter 6 weighs the trade-offs properly.

2.8 Advantages and limitations of the relational model

Five decades of dominance are not an accident. The model's strengths:

• Simplicity. One structure — the table — represents everything from grades to gene sequences, and the same algebra manipulates them all.
• Mathematical foundation. Relational algebra and calculus give queries precise semantics and enable the optimizer's transformations (Chapter 19): plans are provably equivalent, not "usually the same."
• Data independence. Programs see values and names, not storage and pointers; disks, file formats, and index structures changed radically under the model's feet without breaking applications.
• Declarative, set-at-a-time manipulation. Say what; the engine decides how — and can decide differently as data grows.
• Integrity as a first-class citizen. Keys and constraints move correctness from "every program remembers" to "the DBMS enforces once."

The limitations are equally real, and honest engineers know them:

• Fixed schema. Every relation has a frozen attribute list; evolving it (Chapter 9) is a real cost, and semi-structured data fits awkwardly.
• Impedance mismatch. Application programs live in objects and structures, not tuples; bridging the gap (ORMs, Chapter 24) is a whole industry.
• Joins are not free. Relationships split across tables must be reassembled at query time; deeply nested data pays a join tax that tree- and document-shaped stores avoid (Chapter 27 compares the models fairly).
• Rigidity for specialized workloads. Full-text search, geospatial, graph traversal, and streaming analytics are bolted on (PostgreSQL's extensions) or delegated to other systems.

None of these limitations overturned the model; they carved niches around it. The 2010s "NoSQL" movement, examined in Chapter 27, largely rediscovered this: the strongest of those systems eventually added transactions, schemas, and even SQL dialects. For structured, shared, correctness-critical data — which is most business data — the relational model remains the default answer.

Chapter Summary

• A data model has three parts: structure, manipulation, and integrity; the relational model's are relations, relational algebra, and entity/referential integrity.
• A relation is a subset of a Cartesian product of domains; tuples are rows, attributes are columns, domains are typed value sets with optional business rules.
• The schema (intension) is the stable structure; the instance (extension) is the momentary content; degree counts attributes, cardinality counts tuples.
• SQL approximates the model with deliberate departures: duplicate rows, column order, and NULL.
• Well-formed tables have atomic cells, one domain per column, insignificant row order, and unique tuples.
• NULL means "value absent," forces three-valued logic, and is matched only by IS NULL; aggregates ignore it while COUNT(*) does not.
• Superkey ⊇ candidate key; the primary key is the chosen identifier; foreign keys carry referential integrity; enrollment's composite key is (student_id, section_id).
• The model's advantages — simplicity, foundation, independence, declarativity, integrity — outweigh its costs for most data, but the costs (fixed schema, joins, impedance mismatch) are real and explain the neighboring technologies of Chapter 27.

Key Terms

Laboratory Exercises

1. In psql, inspect the student table's schema with \d student. Identify, in the output, the primary key, the foreign key, and the NOT NULL columns. Expected result: student_id is the primary key; major_dept_id references department(dept_id); full_name and total_credits are NOT NULL.
2. Write a query that lists students whose GPA is above 3.80, and run it. Then change the condition to gpa > 3.80 OR gpa IS NULL and run it again. Expected results: first run — Sadia Afrin (3.88) and Arif Mahmud (3.90); second run — the same two plus Zara Hossain, whose NULL satisfies neither comparison but IS NULL.
3. Demonstrate bag versus set semantics: run SELECT major_dept_id FROM student; and then SELECT DISTINCT major_dept_id FROM student; and count the rows of each. Expected results: 12 rows versus 5 rows.
4. Compare the two counts SELECT COUNT(*), COUNT(gpa) FROM student; in one query and explain the difference in one sentence. Expected result: 12 and 11 — COUNT(gpa) skips Zara Hossain's NULL.
5. Try to insert a duplicate primary key and a dangling foreign key, and record the exact errors: (a) a second row with student_id 21100001; (b) an enrollment with student_id 99999 and section_id 1. Roll back or delete nothing — both inserts should fail. Expected results: a duplicate-key violation for (a); a foreign-key violation for (b).
6. In MySQL, run the same four exercises against your university database and note any message or behavior that differs from PostgreSQL. Expected result: the same results and violations; only the wording of the error messages differs.

Review Questions and Exercises

1. Name the three parts of any data model, and the relational model's answer to each. Structure — relations; manipulation — relational algebra; integrity — entity and referential integrity plus constraints.
2. Distinguish a relation schema from a relation instance, using enrollment concretely. The schema is enrollment(student_id, section_id, grade) plus its constraints; the instance is the 28 tuples currently stored, 8 of which have NULL grades.
3. What are the degree and cardinality of enrollment? Of student? Degree 3, cardinality 28; degree 6, cardinality 12.
4. In what two ways do SQL tables depart from pure relations, and what does each cost? Duplicate rows (SQL is bag-valued; you must ask for DISTINCT) and ordered columns (positional INSERTs are legal but fragile).
5. Why is attribute ordering said to be insignificant in the model, and how does SQL nonetheless fix a column order? Attributes are accessed by name, so permutation does not change meaning; CREATE TABLE's column list assigns each column a position that INSERT ... VALUES depends on.
6. A query returns Zara Hossain for WHERE NOT (gpa > 3.80) in neither PostgreSQL nor MySQL. Explain why she is excluded. gpa > 3.80 is UNKNOWN for a NULL GPA, so its negation is also UNKNOWN; WHERE keeps only TRUE rows, so Zara is discarded by both the condition and its negation.
7. Define superkey, candidate key, primary key, and alternate key, and give all four for department. Superkey: any uniquely-identifying set, e.g. {dept_id, dept_name}; candidate keys: {dept_id} and {dept_name}; primary: dept_id; alternate (UNIQUE): dept_name.
8. Why must a primary key be NOT NULL, while a foreign key may be NULL? A NULL primary key would be a tuple without identity, breaking entity integrity; a NULL foreign key can legitimately mean "no reference yet" — an optional relationship.
9. What real-world rule does the composite primary key of enrollment encode? A student may be enrolled in a given section at most once — (student_id, section_id) identifies the enrollment.
10. Write a query that returns the number of students per major department — you will meet the missing piece (GROUP BY) in Chapter 11 — or, with this chapter's tools, a simple count of students in the CSE department (dept_id 1).

    SELECT COUNT(*) AS cse_students
    FROM   student
    WHERE  major_dept_id = 1;

    Expected output: 4.
11. For each of these, say whether it may legally be NULL in the canonical schema, and why: student.full_name, enrollment.grade, course_section.room, department.dept_name. full_name — no (NOT NULL, name always known); grade — yes (in progress); room — yes (not yet assigned); dept_name — no (NOT NULL and UNIQUE).
12. State two genuine limitations of the relational model and one technology each that mitigates it. Fixed schema — migrations/schema versioning (Chapter 24); impedance mismatch — ORMs (Chapter 24); join cost for nested data — document stores or JSON types (Chapter 27); any two with brief justification are acceptable.

Mini-Project

Design the data model for a small personal movie-collection tracker. Write, on paper first, one relation schema per entity — movie, person (actors and directors), and a connecting relation for cast — with for each: attribute names, domains (types plus rules), a chosen primary key among the candidate keys, foreign keys with their references, and which columns may be NULL and why. Decide whether movie carries a natural key (title + year is almost unique — why "almost" disqualifies it?) or a surrogate identifier. Then implement the three tables in PostgreSQL exactly as designed, and try three illegal inserts (duplicate PK, NULL PK, dangling FK) to confirm the model pushes back. Keep the design — Chapter 5 will redraw it as an ER diagram and Chapter 7 will test it for normalization.