The relational model, from the paper that started it

1The paper and the problem it was written for

In June 1970 Communications of the ACM printed an eleven-page paper by E. F. Codd of the IBM Research Laboratory in San Jose. It had been received in September 1969 and revised in February 1970 (Codd 1970, p. 387). It is worth reading the way it was written: as an answer to a specific problem of its time, before the words it introduced became the everyday vocabulary of schemas.

The problem is stated in the first sentence of the abstract. People using a large shared store of data should not have to know how that data is laid out inside the machine, and their programs should keep working when the layout changes (Codd 1970, p. 377). Codd expected the layout to change often, as the mix of queries, updates and reports shifted and as new kinds of information were added.

“Future users of large data banks must be protected from having to know how the data is organized in the machine”

He gives the property a name, data independence: application programs and terminal activity staying unaffected by growth in the types of data and by changes in how data is represented (Codd 1970, p. 377). In the acknowledgment he credits C. T. Davies of IBM Poughkeepsie with convincing him that future systems needed it (Codd 1970, p. 387).

The systems of the day offered users tree-structured files, or the slightly more general network model (Codd 1970, p. 377). The paper argues that a model built on n-ary relations describes data with its natural structure only, adding nothing for the sake of the machine, and that it therefore allows a high-level data language that keeps programs as independent as possible from storage (Codd 1970, p. 377). One sentence is easy to miss and matters for everything after it: the paper does not discuss how to implement such a system (Codd 1970, p. 377). It is a paper about the model the user sees.

2Three ways a program came to depend on storage

Section 1.2 names three kinds of dependence that the data description tables of the time had not removed: on ordering, on indexes and on access paths (Codd 1970, p. 377).

Ordering dependence. If a file of parts is stored in ascending order of part number, a program is usually allowed to assume that records come back in that order. Such a program is likely to break the day the stored order has to change. Codd says that every well-known system then on the market failed to separate the order in which records are presented from the order in which they are stored (Codd 1970, pp. 377 to 378).

Indexing dependence. From the point of view of information, an index is redundant: it speeds up queries and slows down insertions and deletions, and a system whose workload changes needs to create and drop indexes over time. So the question is whether programs can stay the same as indexes come and go (Codd 1970, p. 378). In one system of the time, IDS, a program that used an index had to name it, and stopped working correctly if it was removed (Codd 1970, p. 378).

Access path dependence. This one gets an example that is worth slowing down for. A data bank records parts, projects, and how many of each part are committed to each project. A tree-structured system makes the designer choose a hierarchy, and Codd lists five reasonable ones: projects under parts, parts under projects, the two as peers with the commitments under one of them, or all three as peers (Codd 1970, p. 378).

Now write a program that prints the part number, part name and quantity committed for every part used in project "alpha". Whichever of the five structures the program assumes, it fails on at least three of the other four, either by referring to a file that does not exist or by never reading the file that holds the answer (Codd 1970, p. 379). Keeping every access path alive until no program uses it is no remedy, he adds, because the number of paths would grow without limit (Codd 1970, p. 379).

All three dependencies are still visible in Postgres, as things it deliberately does not promise. Its documentation says SQL makes no guarantee about the order of rows in a table, which come back in an unspecified order unless sorting is asked for (PostgreSQL 18 docs, §5.1). It says indexes can be added to and removed from tables at any time, and that the system decides when to use one (PostgreSQL 18 docs, §11.1). A query never names the index it hopes to use. That is Codd's indexing question answered in the way he hoped.

3What a relation is

Section 1.3 opens by saying the word relation is used in its accepted mathematical sense. Given sets S1, S2, up to Sn, which need not be different, R is a relation on them if it is a set of n-tuples whose first element comes from S1, whose second comes from S2, and so on. Each Sj is the jth domain of R, and n is its degree: unary, binary, ternary, n-ary (Codd 1970, p. 379). A footnote puts it in one line: R is a subset of the Cartesian product S1 × S2 × … × Sn (Codd 1970, p. 379).

A table, then, is not the relation. It is a way of drawing one, and Codd says so: he uses an array for exposition, but it is not an essential part of the relational view (Codd 1970, p. 379). The array has five properties: each row is one n-tuple; the order of the rows does not matter; all rows are distinct; the order of the columns matters, following the order of the domains; and each column is labelled with the name of its domain (Codd 1970, p. 379).

The second and third properties are the ones that follow straight from "set". A set has no first element, so shuffling the rows draws the same relation. A set holds each element once, so a row cannot appear twice. Try both on Figure 1.

Here SQL departs from the paper, and the Postgres documentation is candid about it. SQL does not give rows unique identifiers, so a table can hold several completely identical rows; the documentation adds that this is usually not desirable (PostgreSQL 18 docs, §5.1). The way to get Codd's guarantee back is a primary key, which requires its values to be unique and not null (PostgreSQL 18 docs, §5.5.4). A table without one is a bag of rows, not a relation.

Codd also treats the totality of data in a data bank as a collection of time-varying relations: tuples are inserted, deleted and altered as time passes (Codd 1970, p. 379). The phrase returns later, because it is what makes redundancy and consistency hard. A relation is a value at an instant; a table is the thing that holds a different value tomorrow.

4Names instead of positions

If columns carry the names of their domains, why should their order matter at all? Codd's answer is Figure 2, a relation called component in which two columns are both drawn from the domain part. A tuple (x, y, z) means that part x is an immediate component of part y, and z units of x go into one unit of y (Codd 1970, p. 379). Here the two part columns mean different things, and only their position tells them apart.

He notes that several systems of the time, IMS/360 among them, could not represent a relation with two identical domains at all (Codd 1970, p. 379). And he observes that relations of high degree were common, a degree of 30 being not at all unusual, so asking users to remember the order of thirty columns is unreasonable (Codd 1970, p. 380).

The proposal is that users work with relationships, the domain-unordered counterparts of relations. For that, each domain must be identifiable within its relation without using position, so where a domain appears twice it is qualified by a role name: the two columns of component become sub.part and super.part (Codd 1970, p. 380). Most users would then deal with a collection of time-varying relationships and need to know little more than each one's name and the names of its domains (Codd 1970, p. 380).

This is the SQL column name. When you write CREATE TABLE component (sub_part bigint, super_part bigint, quantity integer), the role names are the column names, and no query has to say "the second column". The paper then drops the distinction and says relation for both, except where it helps to be explicit (Codd 1970, p. 380); this lecture does the same.

5Domains, keys and foreign keys

Before he can define a preferred form, Codd needs four more ideas: active domain, primary key, foreign key and nonsimple domain (Codd 1970, p. 380). His running example is a relation part defined on part number, part name, part colour, part weight, quantity on hand and quantity on order.

Each domain is a pool of values. At any instant only some of them are present in the data bank: plausibly every colour, but hardly every possible weight or part number. The set of values represented at an instant is the active domain (Codd 1970, pp. 380 to 381).

A domain, or combination of domains, whose values uniquely identify each tuple is a primary key. Part number is one; part colour is not. A primary key is nonredundant if it is a single domain, or a combination in which no domain is superfluous. A relation can have more than one nonredundant primary key, as part would if no two parts ever shared a name, and then one of them is chosen arbitrarily and called the primary key (Codd 1970, p. 380).

Postgres keeps the same arrangement. A table can have at most one primary key and any number of unique constraints, which together with not-null constraints are almost the same thing, but only one is identified as the primary key (PostgreSQL 18 docs, §5.5.4). "Chosen arbitrarily" is the decision a schema still makes when a row has two ways to be identified.

A domain or combination in relation R is a foreign key if it is not R's primary key but its values are values of the primary key of some relation S, and S may be R itself (Codd 1970, p. 380). In Figure 1, the combination of supplier, part and project is the primary key of supply, and each of the three taken alone is a foreign key (Codd 1970, p. 380).

“Keys provide a user-oriented means (but not the only means) of expressing such cross-references.”

The cross-reference is a value, not a pointer. A program that wants the supplier of a shipment looks up a supplier number among the suppliers; nothing in the user's model says where that supplier is stored. In Postgres the same idea is a foreign key constraint, which requires the values in a column to match values in some row of another table (PostgreSQL 18 docs, §5.5.5). The REFERENCES you write is Codd's definition with enforcement added.

One more remark in this section is quietly radical. Earlier work, Codd says, tended to split a data bank into descriptions of entities and relations between entities. With foreign keys allowed in any relation, that distinction is hard to maintain, and in the user's model there seems to be no advantage in making it (Codd 1970, p. 380). A supplier and a shipment are both just relations.

6The normal form

So far every domain held atomic values, which cannot be broken down. Codd calls these simple domains, and allows that a domain could instead hold relations as its elements: a nonsimple domain. His example is an employee relation with a domain salary history, each element of which is itself a binary relation on date and salary (Codd 1970, p. 380). The terms attribute and repeating group in the database vocabulary of the time, he says, are roughly analogous to simple and nonsimple domain (Codd 1970, pp. 380 to 381).

A relation whose domains are all simple can be stored as a plain two-dimensional array; one with a nonsimple domain needs something more complicated. That, and reasons that follow, make it worth eliminating nonsimple domains, and he gives a simple procedure for doing it, which he calls normalization (Codd 1970, p. 381).

The procedure works down the tree of nonsimple domains. Take the relation at the top, copy its primary key into each relation directly beneath it, and make each of those relations' primary key its old key plus the copied one. Then strike the nonsimple domains out of the parent, remove the top node, and repeat on each remaining subtree (Codd 1970, p. 381). Applied to Figure 3(a) it gives four relations:

employee' (man#, name, birthdate), jobhistory' (man#, jobdate, title), salaryhistory' (man#, jobdate, salarydate, salary) and children' (man#, childname, birthyear) (Codd 1970, p. 381). The keys grow as they travel down: a salary is identified by the employee, the job and the date together.

Two conditions must hold for the procedure to apply: the nonsimple domains must form a collection of trees, and no primary key may contain a nonsimple domain. Codd writes that he knows of no application that would need either condition relaxed (Codd 1970, p. 381). Then comes a sentence worth remembering:

“Further operations of a normalizing kind are possible. These are not discussed in this paper.”

The single normal form of this paper is the one the level 3 lessons call first normal form, and it is about structure only: no relation inside a relation. The anomalies that second and third normal form deal with appear here only as redundancy, in section 2, below.

Normal form has a second benefit Codd stresses: exchanging bulk data between systems that store it in different ways. A compressed array would carry no pointers, depend on no hashing scheme, and contain no indexes or ordering lists (Codd 1970, p. 381). Anyone who has moved a database through a CSV file has used that argument.

7A language based on predicate calculus

With the model in normal form, Codd proposes a universal data sublanguage based on an applied predicate calculus, and says first-order predicate calculus is enough when the relations are in normal form (Codd 1970, p. 381). It would be a yardstick of linguistic power for other data languages, and a candidate for embedding in host programming languages (Codd 1970, p. 381). He does not define its syntax; the paper describes only its salient features (Codd 1970, p. 381).

Among them: declaring a relation identifies its primary key, and declared relations are added to the system catalog, available to authorised users (Codd 1970, p. 381). Postgres keeps the same idea and takes it one step further. Its documentation describes the system catalogs as where a database stores schema metadata, and says PostgreSQL's system catalogs are regular tables (PostgreSQL 18 docs, ch. 52). The description of your relations is itself a set of relations you can query.

The language's universality, Codd says, lies in what it can describe, not in what it can compute (Codd 1970, p. 382). Insertions add tuples without regard to any order in storage (Codd 1970, p. 382), which is the ordering dependence of section 1.2 removed from the language itself.

He then names a property he calls symmetric exploitation: once users know a relation is stored, they will expect to use any combination of its domains as the knowns and the rest as the unknowns (Codd 1970, p. 382). Performance need not be symmetric, he concedes (Codd 1970, p. 382). In a model built from access paths, supporting this for a relation of degree n takes n factorial named paths, and a notation that nests binary relations needs 2n − 1 names where direct n-ary notation needs n + 1 (Codd 1970, p. 382). For supply, that is 7 names against 5.

Section 1.6 separates the named set, the relations users can identify by a simple name, from the expressible set, every relation that an expression of the language can designate. The named set is usually a very small part of the expressible set (Codd 1970, p. 382). In SQL, CREATE VIEW defines a view of a query, and the query runs every time the view is referenced (PostgreSQL 18 docs, CREATE VIEW): an expression from the expressible set, given a name.

8Operations on relations

Section 2 introduces operations whose job is to derive relations from other relations. Since relations are sets, the usual set operations apply, though the result is not always a relation: the union of a binary and a ternary relation is not one (Codd 1970, p. 383). Codd also says most users would not deal with these operations directly; system designers and the people responsible for data bank control should know them well (Codd 1970, p. 383).

Permutation reorders columns; supply has 4! = 24 permutations, counting the one that changes nothing. For users working with relationships, where columns have names, permutation is irrelevant; it matters only for how relations are stored (Codd 1970, p. 383).

Projection keeps some columns, strikes out the others, and removes any duplicate rows from the result (Codd 1970, p. 383). Codd's Figure 4 projects supply onto project and supplier, and because supplier 1 sends parts to project 5 twice, the projection has fewer tuples than supply had (Codd 1970, p. 383).

Join asks the reverse question: given two binary relations sharing a domain, when can they be combined into a ternary relation that keeps all of the information in both? Codd's definition is exact. R is joinable with S if there is a ternary relation U whose projection on its first two columns is R and whose projection on its last two is S; any such U is a join of R with S (Codd 1970, p. 383). One always exists when the domains line up: the natural join, the set of (a, b, c) such that R(a, b) and S(b, c) both hold (Codd 1970, p. 383).

Note the article. The natural join is one join among possibly several. Figures 5 to 7 show two relations that have two different joins, and the reason is element 1 of the domain part, which has more than one relative under R and more than one under S (Codd 1970, p. 383). Codd calls such an element a point of ambiguity; if R, read backwards, or S is a function, no point of ambiguity can occur and the natural join is the only join (Codd 1970, p. 384).

Composition follows from join: T is a composition of R with S if some join U of R with S gives T when projected onto its first and last columns, and the natural composition is the projection of the natural join (Codd 1970, pp. 384 to 385). The next widget computes all of this from Figure 5, and then shows why it matters.

The widget's second half is the connection trap, named on page 385. Suppose each supplier record points to the parts it supplies, and each part points to the projects that use it. It is tempting to conclude that following every path from a supplier through its parts reaches exactly the projects that supplier supplies. Codd says that conclusion is in general wrong: it holds only when the real supplier and project relation is the natural composition of the other two, and, as path-following claims usually imply, for all time (Codd 1970, p. 385).

The trap has not gone away; it moved into queries. Joining shipments to parts on part number and then to projects says which projects a supplier could reach through a shared part. Whether the supplier actually supplies those projects is a different fact, and the only safe place for it is a relation that records it, which is what supply in Figure 1 does by keeping supplier, part and project in one tuple.

Two operations complete the set. Restriction of R by S keeps the largest subset of R whose projection on chosen columns matches S on chosen columns, a generalisation of restricting a function to part of its domain (Codd 1970, p. 385). And the tie of an n-ary relation keeps the tuples whose first and last elements are equal and drops the last column, which turns a chain of joins into a cycle (Codd 1970, p. 384).

9Redundancy and consistency

Codd separates redundancy in the named set of relations, the ones users see, from redundancy in how they are stored, and is mainly concerned with the first (Codd 1970, p. 385). To talk about it he defines derivability: a relation is derivable from a set of relations if some sequence of operations yields it from them for all time, the phrase that matters because the relations change (Codd 1970, p. 385). For the named set, projection, natural join, tie and restriction are enough (Codd 1970, p. 385).

A set of relations is strongly redundant if one of them has a projection derivable from projections of the others (Codd 1970, p. 385). The first example will look familiar to anyone who has done the level 3 lessons: employee (serial#, name, manager#, managername), with serial# the primary key and manager# a foreign key. If every manager number is a serial number and every manager name is a name, managername is unnecessary: it can be derived by joining the relation to itself (Codd 1970, p. 386).

That is the redundancy the level 3 lessons meet as an update anomaly. Codd does not tell you to delete the column. Strong redundancies exist for real reasons, user convenience among them, including keeping half-obsolete relations named so that old programs still run; knowing they exist lets an administrator choose stored representations more freely (Codd 1970, p. 386).

Weak redundancy has no equation. A relation's projection cannot be derived from the others, yet at all times it is a projection of some join of them. These, he says, are inherent in the logical needs of the users and cannot be removed by an administrator (Codd 1970, p. 386).

Wherever redundancy exists, the named set comes with statements that define it, and a state of the data bank is consistent if its current value satisfies those statements (Codd 1970, p. 386). Codd adds that the system usually cannot work out such statements for itself, because it lacks detailed knowledge of what each relation means (Codd 1970, p. 386). Someone has to declare them.

“consistency as defined above is a property of the instantaneous state of a data bank”

It does not matter how the state came about. An insert that breaks a constraint might be the first half of a correct change, with the matching rows still to come, or it might be a mistake, and the system cannot tell which without asking (Codd 1970, p. 387). He describes two responses: check on every insertion, deletion and key update, which slows them down, or check in a batch, perhaps daily, and trace the cause through a journal of every state-changing transaction (Codd 1970, p. 387).

The first approach is the one Postgres constraints take: a constraint that is not deferrable is checked immediately after every command (PostgreSQL 18 docs, DEFERRABLE). The "first half of a correct change" case has its own answer there too. A deferrable constraint declared INITIALLY DEFERRED is checked only at the end of the transaction (PostgreSQL 18 docs, DEFERRABLE), so an inconsistent moment inside a transaction is allowed and an inconsistent commit is not. Only unique, primary key, exclusion and foreign key constraints accept the clause; CHECK and NOT NULL are never deferrable (PostgreSQL 18 docs, DEFERRABLE).

10What the paper left open

The summary is modest. Section 1 proposed a relational model to protect users from changes in representation and introduced a normal form; section 2 defined operations and two kinds of redundancy, and applied them to keeping data consistent (Codd 1970, p. 387). Codd states that many questions are raised and left unanswered, among them the details of the language and every problem of implementation (Codd 1970, p. 387).

Those are exactly the questions the next lectures in this series take up, each from its own primary sources: the further normal forms the paper deferred, the languages that tried to be its sublanguage, and how systems like Postgres actually store relations and keep them consistent under concurrent use.