Unit 4.1 · about 3 h
257 / 324Relational model, relational algebra and SQL joins
Assume Programming's relational-sql-queries unit. Here the job is the semantic contract an optimizer must preserve, including duplicates, constraints and null-extended rows, not another join tutorial.
- explain
- implement
You can now
- Translate selection, projection and an inner equijoin into an operator tree, preserving SQL multiplicities.
- Specify keys, foreign keys and row constraints for a normalized state schema.
- Prove one filter-pushdown rewrite and give a counterexample to an unsafe outer-join rewrite.
Covers
- Relational tables, tuples, keys and constraints
- Relational algebra and SQL selection, projection and joins
Study, in this order
2 steps
- Lecture 1: Relational Model & AlgebraCMU 15-445/645 - database and storage core
Sections 4-6, Relational Model, DMLs and Relational Algebra, pp. 3-5
Depth · Use the operator definitions. The set-union example on p. 4 uses
UNION ALL, which preserves duplicates; useUNIONfor set union. Keep set and bag semantics separate. - PostgreSQL 18: ConstraintsPostgreSQL - EXPLAIN and transaction isolation lab
Sections 5.5.1-5.5.5:
CHECK,NOT NULL,UNIQUE, primary keys and foreign keys
Focus on
- Classical projection removes duplicates; ordinary SQL
SELECTdoes not. A rewrite must preserve the requested multiplicity, not just the distinct values. - An inner-join filter referring only to one input can move below that join. A
WHEREfilter on an outer join's nullable side can remove unmatched rows. - A foreign key constrains references, not join multiplicity.
CHECK(value > 0)alone permitsNULLin PostgreSQL.
Reproduce closed-book
Section setup: start
docker run -d --rm --name atlas-pg-sys4 -e POSTGRES_PASSWORD=atlas -p 127.0.0.1:55444:5432 postgres:18. Connect to postgresql://postgres:atlas@127.0.0.1:55444/postgres, or use docker exec -i atlas-pg-sys4 psql -X -U postgres. Stop it with docker stop atlas-pg-sys4 after the section. In a fresh database create parent(id int PRIMARY KEY) and child(id int PRIMARY KEY, parent_id int NOT NULL REFERENCES parent(id), value int NOT NULL CHECK(value>0)). Insert parents (1),(2) and children (1,1,10),(2,1,20),(3,2,30). Draw the operator tree for SELECT p.id FROM parent p JOIN child c ON p.id=c.parent_id WHERE c.value>=20; then move the filter into a child subquery and compare ordered results: both return 1,2. Without the value filter, COUNT(*) of the join is 3 but counting parents with EXISTS is 2. Test rejection of a duplicate child id, parent_id=3, NULL parent_id and value=0 in separate statements.Traps
- Adding
DISTINCTto hide a faulty join. It changes semantics and may conceal a missing key predicate. - Moving a right-side predicate from
ONtoWHEREin aLEFT JOINand expecting unmatched left rows to survive.
Practice
The section mini-project covers this: normalized metadata tables, database-enforced constraints, and bag-aware equivalence tests for one join rewrite.
Self-test
-
Why does the unfiltered join have three rows but
EXISTSfind only two parents?Parent 1 has two matching children. The join emits both pairs;EXISTSis a yes/no test for each parent. -
Can projecting away a primary key create duplicate SQL rows?
Yes. Distinct tuples can have the same remaining attributes, andSELECTpreserves both unlessDISTINCTis requested. -
Does
CHECK(value > 0)rejectNULL?No.CHECKaccepts true or unknown. AddNOT NULLif missing values violate the invariant.
Completion criterion
Stop when
Both operator trees return the same ordered multiset, all four invalid inserts fail, and an unmatched-parent fixture demonstrates why the outer-join rewrite is unsafe.
Mark passed, then open 4.2 Only mark this when you can do it without notes.Leads to
- 4.5 Sorting, join algorithms and query plans Choose physical operators for the same logical result.
Resources for this unit
- CMU 15-445/645 - database and storage core Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
- PostgreSQL - EXPLAIN and transaction isolation lab Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
Also in this section
- Designing Data-Intensive Applications, 2nd edition - storage and transactions Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
- Operating Systems: Three Easy Pieces - persistence and integrity Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
- CMU 15-445 - one reduced BusTub project slice If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
- Point-in-time joins Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
- CMU Lecture 19: Timestamp Ordering Concurrency Control Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.
- SQLite Write-Ahead Logging Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.