This is Chapter 2 of Database System Concepts — the relational model itself, the data model that your Lesson 1 called "the foundation almost everyone builds on." Where Chapter 1 argued why a DBMS exists, this chapter defines the vocabulary and the algebra of the model that has dominated commercial data processing for half a century. The payoff for interviews: this is the precise terminology behind every "design the schema" question, and the algebra here is the theory underneath the SQL optimizer your storage lesson introduced. algebra expression it can evaluate cheaply (filter early, use an index), rather than executing your literal steps. This is the theoretical justification for everything your storage lesson said about query planners.
The chapter has two halves. The first half is structure: what a relation actually is, and how we identify and link rows (keys). The second half is querying: the relational algebra, the small set of operations that, composed together, express any question you can ask of tabular data. Hold both halves in mind — structure is what you design, algebra is what you ask against it.
A relational database is a collection of tables, each with a unique name. The model borrows its name from math: a relation is a table, a tuple is a row, an attribute is a column. In set-theory terms a tuple is just an ordered list of values, and a relation is a set of tuples — that "set" part matters, because it means the order of rows is irrelevant. Sorting the instructor table by ID, or leaving it scrambled, gives you the same relation; both contain the same set of tuples.
Row order doesn't exist in the model. Any query result is a set, so if you
care about order you must say so explicitly (SQL's ORDER BY). This is the first
place the formal model and a real SQL table diverge — the book flags that commercial
systems permit duplicate rows unless you forbid them, but the formal algebra assumes
duplicates are eliminated.
Three more definitions the book is careful about, because they show up in every exam and interview:
phone_number column holding one number is atomic; one holding a set of
numbers is not, because it has subparts. Note the subtlety: atomicity is about
how you use the value, not what the value "is" — even a phone number stops
being atomic if you start splitting it into country/area/local parts.
The book closes the structure intro with the null value: a special marker meaning "unknown or does not exist." Nulls are a constant source of bugs in real queries, so the book's advice is to eliminate them where possible and handle them explicitly where you can't. (SQL's three-valued logic — true / false / unknown — is the consequence, covered in Chapter 3.)
Lesson 1 gave you the intuition; here is the precise mapping to programming languages, which is the cleanest way to remember it:
| Relational concept | Programming-language analog |
|---|---|
| Relation | A variable. |
| Relation schema | A type declaration (the list of attributes). |
| Relation instance | The value held by that variable at a moment. |
The schema rarely changes; the instance changes constantly as rows go in and out. The book
notes we lazily reuse the same name (instructor) for both the schema and whatever
instance it currently holds — only disambiguating when needed. Keep this straight: when
an interviewer says "the instructor relation," they usually mean the schema (the design), not
today's rows.
A subtle but important design point: the same attribute appears in multiple schemas
on purpose. dept_name lives in both instructor and
department. That shared column is the mechanism that lets you link tuples across
relations — "find instructors in the Watson building" means look up Watson's
dept_name in department, then match it in instructor.
This is the seed of the foreign key, covered next.
A relation must let you tell rows apart, so no two tuples may be identical on every attribute. The machinery for expressing that is the key hierarchy:
| Key type | Definition | Note |
|---|---|---|
| Superkey | A set of attributes that uniquely identifies a tuple collectively. |
ID is one; {ID, name} is also one (redundant). Any superset of a
superkey is also a superkey.
|
| Candidate key | A minimal superkey — no proper subset is also a superkey. |
A relation can have several: {ID} and {name, dept_name} could
both qualify for instructor.
|
| Primary key | The candidate key the designer chooses as the main identifier. | A constraint on the real world; primary-key attributes are underlined and listed first. |
Choosing a primary key is a real design decision, not a formality. Pick attributes whose values never change: a person's name is a bad key (collisions, and people rename); an address is a bad key (people move); a generated ID or SSN is good because it's guaranteed stable. If two enterprises merge and both issued the same ID, you have to reallocate — which is why synthetic keys are safer than borrowed real-world identifiers.
Composite primary keys are common when no single column is unique. The
classroom relation uses {building, room_number} (neither alone
identifies a room), and time_slot uses
{time_slot_id, day, start_time} because a slot can meet multiple times a day. The
rule: the key is the smallest set that's still unique.
The foreign key is how relations reference each other. A foreign-key
constraint from attribute(s) A of relation r1 to the primary key
B of r2 says: every value of A in r1 must
also appear as a B value in some r2 tuple. The book uses
instructor.dept_name → department.dept_name as the canonical example.
r1 is the referencing relation; r2 is the
referenced one. This is exactly the referential integrity constraint
your Lesson 1 DDL section named — the system rejects a row whose foreign key points at
nothing.
Foreign key ⊆ referential integrity, but not equal.
A foreign key must reference a primary key. The broader referential-integrity
constraint relaxes that to "any attribute." The book's example:
section.time_slot_id must exist in time_slot.time_slot_id, but
time_slot_id alone isn't time_slot's primary key — so it's a
referential-integrity constraint, not a foreign key, and most DBMSs won't enforce
it. That distinction is a classic interviewer trap.
A schema diagram draws each relation as a box (name on top, attributes inside), underlines primary keys, and draws arrows from foreign-key attributes to the referenced primary key. It's the one-page picture of the whole database's structure and its links. The book warns not to confuse it with the entity-relationship (E-R) diagram you'll meet in Chapter 6 — same general look, completely different meaning (the E-R diagram is a design sketch before tables exist; the schema diagram is the tables themselves).
Before the algebra, the book classifies query languages by how you tell the system what to do — and notes SQL mixes all three:
| Style | What you specify | Example |
|---|---|---|
| Imperative | A sequence of operations + state you update as you go. | Relational algebra is close; assembly-like query plans. |
| Functional | Evaluation of side-effect-free functions; no state updates. | Relational algebra (formally), Lisp-style map/reduce. |
| Declarative | What you want, in logic; the system finds how. | SQL's SELECT ... WHERE, tuple/domain calculus. |
The book is explicit that the relational algebra is the theoretical basis of SQL. So when you write a SQL query, the optimizer is secretly rewriting it into algebra, hunting for an equivalent expression that's cheaper to run. That bridge is the whole point of studying the algebra: it's the language the optimizer thinks in.
The algebra is a set of operations, each taking one or two relations and returning a relation — so you can compose them into expressions, exactly like arithmetic. Unary ops (one input): select, project, rename. Binary ops (two inputs): union, Cartesian product, set difference, join. The result of every operation is itself a relation, which is why composition works.
| Op | Symbol | Does | Example |
|---|---|---|---|
| Select | σ | Keep rows where a predicate holds. | σdept_name='Physics'(instructor) → Einstein, Gold. |
| Project | Π | Keep listed columns; eliminates duplicate rows. | ΠID,name,salary(instructor). |
| Cartesian product | × | Pair every row of r1 with every row of r2 (n1×n2 rows). | instructor × teaches. |
| Join | ⋈ | Cartesian product + a select that matches columns; links relations. | instructor ⋈ID=ID teaches. |
| Union | ∪ | Rows in either input (set union). | Fall2017 ∪ Spring2018 course ids. |
| Set difference | − | Rows in r1 but not r2. | Fall2017 − Spring2018. |
| Intersection | ∩ | Rows in both inputs. | Fall2017 ∩ Spring2018. |
| Assignment | ← | Store a sub-expression in a temp relation variable. | temp ← σ...(r); ... |
| Rename | ρ | Name a result (or rename attributes) to reuse it, e.g. self-join. | ρi(instructor) for a self-comparison. |
Select (σ) filters rows on a predicate — you can combine
conditions with ∧ (and), ∨ (or), ¬ (not), and compare attributes to each other
(find departments whose name equals their building). Project (Π) keeps
only the named columns. The thing to remember is that projection, being a set operation,
deduplicates: project instructor down to salary and you get one row per distinct
salary. The generalized project even allows expressions (salary/12
for monthly pay). These two are the workhorses — most queries are a select, then a
project, or vice versa.
"Find the names of instructors in Physics" needs both: select Physics rows from
instructor, then project to name. You write it as
Πname(σdept_name='Physics'(instructor)) — the argument to
project is itself an algebra expression, not a stored relation. Because every operation
returns a relation, you can nest them arbitrarily, like building arithmetic expressions. That
closure property is what makes the algebra expressive.
The Cartesian product (×) concatenates every row of r1 with every row
of r2, producing n1×n2 rows — almost always too much, because it links rows that
have nothing to do with each other. The join (⋈) is shorthand for
"Cartesian product, then select on a matching predicate," which keeps only the meaningful
pairings.
instructor ⋈ID=teaches.ID teaches
gives each instructor paired with the courses they actually taught. Instructors who teach
nothing (Gold, Califieri, Singh) drop out — a plain (inner) join loses unmatched rows,
which is exactly why the outer join exists (Chapter 4). When two relations share an attribute
name, you qualify it as instructor.ID vs teaches.ID; the
rename (ρ) operator exists so you can do this even for a relation joined
with itself (e.g. "instructors earning more than Wu" needs two scans of
instructor under different names).
Join = the glue of the relational model. Foreign keys are only metadata until you act on them; the join is the operation that actually follows a foreign key to stitch two relations into one answer. Every "show me X with its Y" question in an interview is a join, and how that join is executed (index lookup vs full scan vs hash join) is the storage/optimizer story from your storage lesson.
Union, intersection, and difference combine two relations
row-wise, but only if they're compatible: same number of attributes
(arity), and matching types per position. You can't union instructor with
section (different shapes), and even two 4-column relations fail if the 4th
column is salary in one and tot_cred in the other. Because relations are sets, union removes
duplicates — CS-101 appears once even though it's taught in both semesters.
These set ops are how you express "either / both / only one" questions without joins.
Assignment (←) lets you break a complex query into temp relation variables — it adds no power, just readability, like introducing local variables. Rename (ρ) gives a name (and optionally new attribute names) to a result, essential for self-joins and for referring to sub-results.
The optimizer's whole job is equivalence. The book's closing point — "find Physics instructors' courses" can be written with the select applied before the join or after it, and both give the same answer — is the crux of query optimization. The optimizer rewrites your declarative query into an equivalent algebra expression it can evaluate cheaply (filter early, use an index), rather than executing your literal steps. This is the theoretical justification for everything your storage lesson said about query planners.
When an interviewer says "design the schema for X" or "write a query for Y," Chapter 2 is your mental toolkit:
1. In the relational model, a relation is a:
Single row (tuple) Set of attributes (columns) Set of tuples (rows)2. Candidate key vs superkey:
Candidate key is a minimal superkey Superkey is minimal, candidate is not Candidate key is the one the designer picks3. A foreign-key constraint must reference:
The primary key of another relation Any attribute of another relation The primary key of the same relation4. The join operation is shorthand for:
Select then project Cartesian product then select Union of two relations5. Why does the book stress that queries can be written multiple equivalent ways?
It justifies query optimization Some ways return extra rows It proves the algebra is imperative6. Two relations can be unioned only if they are:
Named the same Compatible (same arity + types) Linked by a foreign key
tuple ? row ; attribute ? column ; relation =
set of tuples
? row order irrelevant ; duplicate rows eliminated
(formal model)
instance ? rows at a moment (like a value)
domain ? permitted values per attribute
atomic domain ? indivisible ; about how used (? what it "is")
null ? unknown / absent ; causes bugs ? eliminate if possible
relation ? variable ; schema ? type decl ; instance
? value
? schema stable, instance changes
? shared attribute (dept_name) = how relations link
a) Superkey ? set that uniquely IDs a tuple (may be redundant)
b) Candidate key ? minimal superkey (no subset is one)
c) Primary key ? chosen candidate ; underlined, listed first
? pick stable attrs: ID/SSN ? ; name/address ? (change)
Composite PK ? smallest unique set (eg classroom = {building, room})
Foreign key ? A in r1 references PK B in r2 ; r1 referencing, r2 referenced
FK ? referential integrity ; FK must hit a PK ; most DBMS ? enforce non-PK RI
box per relation ; PK underlined ; FK ? referenced PK
? confuse with
E-R diagram (Ch 6 design sketch, not tables)
Imperative (steps+state) / Functional (side-effect-free) / Declarative (what, system finds how)
SQL mixes all 3 ; relational algebra = theory under SQL = optimizer's language
ops take relation(s) ? relation ; compose like arithmetic (closure)
a) Select ? ? keep rows by predicate (? ? ?, attr vs attr)
b) Project ? ? keep columns ; deduplicates (set)
c) ? ? every row paired ; n1?n2 rows (too many)
d) Join ? ? ? then ? on match ; glue of model ; drops unmatched
e) ? ? ? ? row-wise ; need compatible (same arity + types)
f) ?? ? temp relation var (readability only)
g) ?? ? name/ rename result ; needed for self-join
? join follows FK to stitch relations (every "X with its Y" = join)
? equivalent algebra expressions exist ; optimizer picks cheap one = basis of query opt
Primary source: Silberschatz, A., Korth, H. F., & Sudarshan, S. (2020).
Database System Concepts, 7th ed., Chapter 2: “Introduction to the Relational
Model.” McGraw-Hill.
Recommended supplement: Codd, E. F. (1970). “A Relational Model of Data
for Large Shared Data Banks.” Communications of the ACM, 13(6) — the
paper that defined both the model and the original relational algebra.
Questions? Ask your agent — you can follow up on any concept, quiz answer, or how this maps onto a schema-design or SQL translation interview question.