Weekly Paper Notes — Seminal Paper of the Week. Area: Databases.
Author: E. F. Codd (IBM Research Laboratory, San Jose) Published: Communications of the ACM, Vol. 13, No. 6, June 1970, pp. 377–387 DOI: 10.1145/362384.362685
Why the paper still matters
Codd’s paper is eight pages long, contains no system, no benchmark, and no evaluation section. It would very likely struggle to get past a modern program committee. It is also, by a wide margin, the most economically consequential paper in the history of computer science — the entire relational database industry, SQL, the query optimizer as a discipline, and by extension most of what we call “data infrastructure” descend from it.
What makes it worth re-reading in 2026 is not nostalgia. It is that the paper is an unusually clean example of a specific intellectual move: identify the coupling that is quietly costing everyone, and interpose an abstraction that makes it impossible to express. Codd did not make databases faster. He made a category of program-breaking change stop existing. Fifty-six years later, systems people are still making the same move — this week’s digest includes a paper arguing that the OS page cache, not a hand-tuned user-space tier, should own eviction for MoE expert weights, which is the same argument about the same kind of coupling.
The setup: what the world looked like in 1970
Before Codd, the dominant models were hierarchical (IBM’s IMS) and network/navigational (the CODASYL DBTG proposals). In both, a database was a graph of records connected by pointers, and a query was a program: find an owner record, follow a set to its first member, iterate to the next member, descend into a child segment. The access path was written into the application.
Codd’s opening frames this precisely. Existing systems, he writes, fail to shield users from changes to the data representation, and users “must be protected” from having to know how the data is organized in the machine. He names three specific dependencies that application programs of the era carried:
- Ordering dependence — programs break if the stored ordering of records changes.
- Indexing dependence — programs break if an index is added or dropped, because the index is visible in how the query is phrased.
- Access path dependence — programs break if the tree or network structure is reorganized.
These are not performance problems. They are maintenance problems, and they were, at the time, the dominant cost of running a data-processing shop. Every physical tuning decision was a source-code change somewhere.
The move: a relation is a set, and that is all
The technical content is disarmingly small. A relation on domains D₁, D₂, …, Dₙ is a subset of their Cartesian product: a set of n-tuples. Because it is a set:
- There is no ordering among rows. Ordering dependence dies at the definition.
- There are no duplicate rows — each tuple is distinct. (This is the point where SQL later diverged from Codd, and the divergence is still generating papers; see the “read alongside” section below.)
- Column ordering is likewise inessential; Codd introduces the idea of naming domains by role rather than position.
He then defines normal form: a relation whose domains are all simple — no relation-valued attributes, no nested structure. The paper shows how any hierarchical collection of relations can be flattened into normal form by carrying keys down, and demonstrates it on a worked example of parts, projects and suppliers. This is the ancestor of what everyone now knows as first normal form, and, crucially, the flattening step is what makes a uniform algebra possible: if every relation has the same shape of shape, one set of operators works on all of them.
The operators follow: permutation, projection, join, composition, restriction. The essential property — which Codd states but which the field took years to fully exploit — is closure. Every operator takes relations and produces a relation. That is what allows arbitrary composition, which is what allows a query to be a single expression, which is what allows a machine to rewrite that expression into a different but equivalent one.
The consequence Codd only half-anticipated: the optimizer
Here is the part that is easy to miss. By insisting the user state what set they want rather than how to walk to it, Codd created a gap between the query and its execution — and something has to fill that gap. That something is the query optimizer, and it is the single most valuable artifact the relational model produced.
Codd himself gestures at this: he discusses expressible, named and stored sets, and notes that a system can choose which relations to materialize. But the full realization came with System R and Selinger’s 1979 cost-based optimizer paper, which turned “choose an access path” into a search problem over a plan space with a cost model. Once that existed, the physical layer became free to change — add an index, re-sort a table, partition it, move it to columnar storage, distribute it across a hundred nodes — and the applications did not care. Every subsequent leap in database performance, from Selinger through vectorized execution through modern cloud data warehouses, was cashed against the abstraction budget Codd opened in 1970.
This is the deep pattern: declarativeness is not a usability feature, it is an optimization license. You give up the ability to specify the plan, and in exchange the system gains the right to change the plan forever without asking you.
The parts that aged interestingly
Codd’s paper also contains ideas the industry took decades to catch up with, and a few it never did.
Consistency and redundancy. The final sections deal with strong versus weak redundancy and with the problem of detecting inconsistency in a stored collection. Codd’s suggestion — that the system should hold declared constraints and check them, notifying someone when they are violated, rather than trusting applications to maintain invariants — is the germ of integrity constraints, foreign keys, and CHECK. It is also, arguably, the germ of every “declare the desired state and let the system reconcile” system built since, including the whole of GitOps.
The sublanguage idea. Codd argues for a “universal data sublanguage” embeddable in a host programming language and grounded in first-order predicate calculus. That is exactly what SQL became — embedded, declarative, not Turing-complete by design. It is also why the impedance mismatch between SQL and application languages has never gone away: it was a deliberate design choice, not an accident.
Nulls and bags — the road not taken. Codd’s relations are sets of complete tuples. SQL’s are bags with nulls and three-valued logic. This is the single largest deviation of the implemented system from the model, and it is the one that generates the most enduring pain — non-idempotent queries, NULL != NULL, aggregate functions that silently skip rows, optimizer rewrites that are invalid in the presence of nulls. Notably, a paper in this very week’s cs.DB listings — Aref, Libkin and Martens’ “Time to Move on: Querying without Nulls and Bags” — argues from production experience with the Rel language that a fully normalized, null-free, bag-free relational language is not only theoretically cleaner but practically deployable. Fifty-six years on, the field is still relitigating Codd’s original position, and increasingly finding he was right.
Why this design has outlasted everything around it
The navigational databases Codd was arguing against were not bad software. IMS is still running in production somewhere right now. They lost because they made the application depend on decisions that needed to change. The relational model won because it made the smallest possible commitment about representation — a relation is a set of tuples, full stop — and therefore had the largest possible space of implementations underneath.
That is the lesson that transfers. When you are designing an interface, the question is not “what is the most expressive thing I can offer?” but “what is the least I can promise, such that everything I might want to do later remains legal?” Codd promised sets. Everything else — B-trees, hash joins, column stores, LSM trees, distributed consensus, vectorized execution, and every hardware generation since the disk pack — has been an implementation detail hiding behind that promise.
Read it once for the history. Read it a second time as a design document about coupling.
Read alongside
- System R: Relational Approach to Database Management (Astrahan et al., 1976) and Access Path Selection in a Relational Database Management System (Selinger et al., 1979) — the papers that turned the model into a system and invented cost-based optimization.
- A Relational Model of Data for Large Shared Data Banks is best paired with Codd’s own later “Extending the Database Relational Model to Capture More Meaning” (1979) for how he thought about nulls.
- The Ubiquitous B-Tree (Comer, 1979) — the physical structure the abstraction was hiding.
- Are You Sure You Want to Use MMAP in Your DBMS? (Crotty, Leis & Pavlo, 2022) — a modern instance of the same “who owns the physical decision” argument.
- Time to Move on: Querying without Nulls and Bags (arXiv:2608.10863, Aref, Libkin & Martens, this week) — the direct descendant of Codd’s set-purism, argued from a deployed system.
Links
📄 ACM Digital Library — doi:10.1145/362384.362685 · 📄 Freely available scan (University of Texas)
Part of the Weekly CS Paper Digest series. Seminal picks are written from background knowledge and a re-read of the original; diagrams are original work.