A Relational Model of Data for Large Shared Data Banks

In one breath — the whole paper, compressed

Formatted data systems of the late 1960s exposed their users to tree and network structures, so application programs broke whenever the stored ordering, an index, or an access path changed. Codd proposes that the totality of data in a data bank be viewed as a collection of time-varying n-ary relations, presented to users as domain-unordered relationships whose columns are identified by domain and role names rather than by position. He gives a normalization procedure that removes nonsimple (repeating-group) domains by copying the parent primary key down into each subordinate relation, leaving a set of flat arrays that contain no pointers, no hash addressing, and no indices or ordering lists. On top of this he defines operations on relations — permutation, projection, join, composition, tie, restriction — that let relations be derived from other relations, and uses derivability to define strong and weak redundancy and the consistency constraints a system can actually check. Because the normalized model is flat, a first-order predicate calculus suffices as a universal data sublanguage, which Codd offers as a yardstick of linguistic power and as the basis for maximal independence between programs and machine representation.

Before this paper — the world it landed in

By 1970 the commercially available formatted data systems — IMS/360, IDS, TDMS, GIS — gave users either hierarchic files or slightly more general network models, and data description tables were regarded as the major recent advance toward data independence. In those systems the records of a parts file might be stored in ascending order by part serial number, and application programs were permitted to assume that the order of presentation was identical to the stored ordering. Indexing policy varied wildly: TDMS unconditionally indexed all attributes, the released IMS offered either no indexing or indexing on the primary key only, while IDS let file designers weave indices into the file as extra chains that programs had to refer to by name and that broke those programs when removed. Codd notes that several existing systems, IMS/360 among them, could not even represent a relation with two or more identical domains, such as a part/subpart bill of materials. The remedy on offer — never retiring a user access path until every program using it is obsolete — was impractical because the number of access paths in the total model for a community of users would eventually become excessively large.

The problem — what was actually breaking

Ordering dependence: systems store elements in at least one total ordering closely associated with the hardware-determined ordering of addresses, and programs that exploit it are likely to fail to operate correctly once that ordering has to be replaced.
Indexing dependence: an index is informationally redundant and purely performance-oriented, so it must be created and destroyed as activity patterns change, yet in IDS a program that names an indexing chain stops working when the chain is later removed.
Access path dependence: the same parts, projects, and commitment data admits at least five different tree structurings, and a program written for one of them fails on at least three of the other four, because it references a nonexistent file or fails to reference a file holding needed information.
Nonsimple domains — repeating groups such as an employee salary history — cannot be held in a two-dimensional column-homogeneous array and force a more complicated stored data structure.
Systems designers fall into the connection trap: they follow every pointer path from a supplier via the parts he supplies to the projects using those parts and wrongly conclude they have obtained the true supplier-to-project relation.
Redundancy among the named relations is nowhere characterized, so a system has no basis for saying whether an insertion, deletion, or key update has left the data bank in a consistent state, and path-based views additionally force users to coin far more names than necessary because names attach to paths rather than to relations.

Core ideas — the contributions, and why they work

Data as time-varying n-ary relations

Codd takes relation in its accepted mathematical sense: given sets S1 through Sn, R is a set of n-tuples whose jth element comes from the jth domain, equivalently a subset of the Cartesian product, and n is its degree. The totality of data in a data bank is then a collection of such relations of assorted degrees, each subject over time to insertion, deletion, and alteration of tuples. This works because a relation carries the natural structure of the data and nothing else: no ordering, no pointers, no access paths are smuggled in as part of the description. Everything a stored representation needs is thereby pushed below the user model, where the system is free to change it.

Relationships: dropping column order

A relation of degree 30 is said to be not at all uncommon, and no user should have to remember the domain ordering of such a thing. Codd therefore proposes that users deal not with relations but with relationships, their domain-unordered counterparts, formally equivalence classes of relations under permutation of domains. This requires only that domains be uniquely identifiable within a relation without using position, which is achieved by qualifying a repeated domain with a distinctive role name: the two part columns of the relation component become sub.part and super.part. A user then needs to know nothing about a relationship beyond its name and the names of its domains, and even that can be served up in menu style by the system.

Normal form by normalization

Some domains may have relations as elements, and those relations may in turn be defined on nonsimple domains, giving a tree of nesting such as employee containing jobhistory containing salaryhistory. Codd gives a mechanical elimination procedure, normalization, that flattens this tree by copying each parent primary key down into its subordinate relations and then striking the nonsimple domains out of the parent. The payoff is that every relation becomes storable as a plain two-dimensional column-homogeneous array, which is why a first-order predicate calculus then suffices as the query language and why a compressed array becomes a viable interchange format between systems. The procedure is valid whenever the graph of interrelationships among nonsimple domains is a collection of trees and no primary key has a nonsimple component domain.

Primary and foreign keys instead of pointers

A domain or combination of domains whose values uniquely identify each tuple is a primary key; it is nonredundant if none of its participating simple domains is superfluous, and when a relation has several nonredundant keys one is arbitrarily chosen as the primary key. A domain combination of R that is not R's primary key but whose elements are values of the primary key of some relation S is a foreign key, and S may be R itself. Cross-references between tuples are therefore expressed in values that the user can see and write, rather than in machine addresses the user must traverse. Codd draws the consequence that the traditional split between entity descriptions and relations between entities becomes untenable and, in the user model, pointless: everything is just a relation.

A universal data sublanguage on predicate calculus

Because normalized relations are flat, an applied first-order predicate calculus suffices to describe any subset of the data bank, and Codd proposes such a sublanguage R embeddable in any host language H. R declares relations and their primary keys into a system catalog subject to authorization, and specifies retrievals, insertions, and deletions without regard to any ordering present in the machine representation; H supplies the storage-representation declarations and any arithmetic functions R needs to invoke. The universality claimed is descriptive, not computational: the class of qualification expressions must have the power of the well-formed formulas of the calculus, though a subset such as prenex normal form is enough to preserve it. Codd offers this language as a yardstick of linguistic power against which any other proposed data language can be measured.

Symmetric exploitation of relations

Once a user knows a relation is stored, he will expect to exploit it — query, update, delete — using any combination of its arguments as knowns and the rest as unknowns, because the information is there. Codd names this logically symmetric exploitation and points out that path-based systems cannot deliver it at reasonable cost: a single binary relation already needs two directed paths, and a relation of degree n needs n factorial paths to be named and controlled. He is careful to concede that symmetry in performance is not to be expected, which quietly hands the whole problem of access-path selection to the system. Nesting binary relations instead of using direct n-ary notation makes it worse, costing 2n-1 names instead of n+1 and making some bases of interrogation very awkward to express.

Derivability, redundancy, and consistency

Codd defines a relation R to be O-derivable from a set S if some sequence of operations from a collection O yields R from members of S for all time, admitting only operations that produce a unique result — natural join qualifies, join does not. A set of relations is strongly redundant when a projection of one of them is derivable from projections of the others, which can be written as an equation, and weakly redundant when such a projection is not derivable but is at all times a projection of some join of other projections. Strong redundancy is useful and removable — it buys user convenience and lets semi-obsolete relationships stay in the named set so old programs keep running — whereas weak redundancy is inherent in the logical needs of the user community and cannot be removed. Since the system lacks the semantics to deduce these facts, the redundancies must be declared as constraint statements, and consistency is then defined as the instantaneous value satisfying that constraint set.

How it works — the mechanism, concretely

The array representation and its five rules

A relation is exhibited as a two-dimensional array in which each row is an n-tuple, the ordering of rows is immaterial, all rows are distinct, the ordering of columns is significant because it corresponds to the ordering of the domains, and each column is labeled with the name of its domain. Codd is explicit that the array is expository only and not an essential part of the relational view, which is exactly the line separating the logical model from any stored representation. Column order matters at this level because two columns may carry identical headings and still have distinct meanings: in the ternary relation component(part, part, quantity), the meaning of component(x, y, z) is that part x is an immediate component of part y and z units of x are needed per unit of y. Role names sub and super qualify the repeated domain so that users can address the columns by name and forget position entirely.

The normalization procedure

Start at the top of the tree of nonsimple-domain interrelationships. Take the parent relation's primary key and expand each immediately subordinate relation by inserting that primary key domain or combination; the expanded relation's primary key is its old key augmented by the key copied down from the parent. Then strike all nonsimple domains out of the parent, remove the top node of the tree, and repeat the same sequence on each remaining subtree. Applied to employee(man#, name, birthdate, jobhistory, children) with jobhistory(jobdate, title, salaryhistory), the result is employee'(man#, name, birthdate), jobhistory'(man#, jobdate, title), salaryhistory'(man#, jobdate, salarydate, salary), and children'(man#, childname, birthyear) — every relation flat, and every descendant now carrying explicitly the ancestor keys that physical containment used to imply.

The selection operator: permutation and projection

For an index list L = i1 through ik and an n-ary relation R with n at least k, πL(R) is the k-ary relation whose jth column is column ij of R, with duplicate rows removed. Pure permutation is the case where L reorders all n indices; the degree-4 relation supply has 4 factorial, that is 24, permutations counting the identity. Pure projection strikes columns out, and because duplicates are then removed a projection may have strictly fewer tuples than the relation it came from, as the permuted projection π31(supply) does. Permutation is irrelevant to the user model of relationships considered in isolation, but it matters for stored representations, since in a system with symmetric exploitation the set of queries answerable by a stored relation is identical to the set answerable by any permutation of it — storing both is logically unnecessary but may be advisable for performance.

Join, natural join, and points of ambiguity

Binary R is joinable with binary S if there exists a ternary U with π12(U) = R and π23(U) = S, and any such U is called a join of R with S. A sufficient condition is π2(R) = π1(S), and in that case the natural join R*S = {(a,b,c) : R(a,b) and S(b,c)} always exists and satisfies π12(R*S) = R and π23(R*S) = S. Joins are not unique in general: an element of the joining domain that has more than one relative under R and also more than one under S is a point of ambiguity, and it is precisely such an element that gives rise to a plurality of joins. If π1(R) or S is a function — one-one or many-one but not one-many — no point of ambiguity can occur and the natural join is the only join of R with S; note that S being joinable with R is an entirely separate question.

Cyclic joins and the tie operator

Three binary relations R on supplier and part, S on part and project, T on project and supplier can be joined into a cyclic 3-join, a ternary U with π12(U) = R, π23(U) = S, π31(U) = T, provided five projection and implication conditions hold among them; a linear 3-join instead yields a quaternary V with π12(V) = R, π23(V) = S, π34(V) = T. To derive cyclic joins from linear ones Codd introduces the tie operator γ, which takes an n-ary relation to a degree n-1 relation by keeping only the tuples whose first and last components are equal, so the natural cyclic 3-join is γ(R*S*T); parentheses are unnecessary in R*S*T because natural join is associative. A plurality of cyclic 3-joins requires far more severe conditions than a plurality of 2-joins: each of the three pairings must have a point of ambiguity, and those three points must chain around the cycle. Relations of arbitrary degree are handled by taking Cartesian products of their domains into groups A, B, C so that each can be treated as if it were binary.

Composition, restriction, and the derivation set

T is a composition of R with S if there is a join U of R with S such that T = π13(U), so two relations are composable exactly when they are joinable; the natural composition is R·S = π13(R*S). Several distinct joins can collapse to a single composition when unambiguous associations through other points pin the answer down, so the number of distinct compositions ranges from one up to the number of distinct joins. The restriction of R by S, written with equal-length index lists L and M, is the maximal subset R' of R such that πL(R') = πM(S), a generalization of restricting a function to a subset of its domain, defined only where the compared elements admit equality. For the named set in noninferential systems Codd claims an adequate derivation collection is projection, natural join, tie, and restriction; permutation is irrelevant there and natural composition is omitted because it is just a natural join followed by a projection.

Declaring redundancy and checking consistency

Strong redundancy is exhibited by an equation: in employee(serial#, name, manager#, managername), with the active domain of manager# contained in that of serial# and of managername in that of name for all time, the projection π14(employee) is written as a composition of the projections π12(employee) and π13(employee), so the managername domain is unnecessary. Weak redundancy has no such equation, only a statement such as: for all time, π12(P) is some composition of π12(Q) with π21(R), where the composition in question might be the natural one at one instant and a nonnatural one at another. Since the system lacks detailed semantic information it cannot deduce these constraints and may only fallibly induce them, so a set Z of constraint statements is declared alongside the collection C of relations, and the state (C, Z, V) is consistent exactly when the instantaneous value V satisfies Z. Checking a composition constraint on R, S, T reduces to three tests: π1(T) = π1(R), π2(T) = π2(S), and for every pair (a,c) in π12(T) there is a b with (a,b) in π12(R) and (b,c) in π12(S). Checking on every insertion, deletion, or key update slows those operations; the alternative is a daily batch check, with offending inputs tracked down through a journal of all state-changing transactions.

What the paper showed — measurements and proofs

With five plausible tree structurings of the same parts, projects, and commitment data, a program P that assumes one structure and makes no test fails on at least three of the remaining four: if P succeeds with structure 5 it fails with all the others, if with structure 3 or 4 it fails with at least 1, 2, and 5, and if with 1 or 2 it fails with at least 3, 4, and 5.
Symmetric exploitation is combinatorially hopeless under path-based models: a single binary relation needs two directed paths, a relation of degree n needs n factorial paths to be named and controlled, and relations of degree 30 are stated to be not at all uncommon in commercial, governmental, and scientific data banks.
Expressing an n-ary relation as nested binary relations costs 2n-1 coined names instead of n+1; the 4-ary relation supply, which entails 5 names in n-ary notation, needs 7 in the nested form P(supplier, Q(part, R(project, quantity))).
Normalization is stated to be applicable whenever the graph of interrelationships of the nonsimple domains is a collection of trees and no primary key has a nonsimple component domain, and Codd reports knowing of no application that would require relaxing these two conditions.
The natural join always exists when π2(R) = π1(S) and provably satisfies π12(R*S) = R and π23(R*S) = S; moreover, if π1(R) or S is a function, no point of ambiguity can occur and the natural join is the unique join of R with S.
A normalized set of relations admits a compressed array communication form that is devoid of pointers, address-valued or displacement-valued, avoids all dependence on hash addressing schemes, and contains no indices or ordering lists — making it usable for bulk data exchange between systems with widely different internal representations.

Limits and trade-offs — conceded and discovered

The paper concedes that implementations of systems to support the relational model are not discussed at all, and that translating requests in a high level data language into corresponding and efficient actions on the current stored representation is a challenging and unsolved design problem. (conceded by the paper; closed only later by System R and INGRES)
Only projection, natural join, tie, and restriction are offered as an adequate derivation collection, and Codd writes that further operations of a normalizing kind are possible but are not discussed in this paper — the gap his own later normal forms and Boyce-Codd normal form filled. (conceded, then addressed by later work)
Symmetric exploitation is promised only logically, with the explicit caveat that symmetry in performance is not to be expected; choosing an efficient plan for an arbitrary declarative request became the cost-based query optimization problem, which this paper does not attempt. (conceded; exposed by later work)
Consistency is defined purely as a property of the instantaneous state, independent of how that state came about, so the system cannot distinguish a user error from a half-finished multi-relation update and normally has no way to resolve the question without interrogating its environment; the paper also admits practical problems in taking an instantaneous snapshot of relations that may be very large and highly variable, and says nothing about concurrency control or recovery. (conceded)
Weak redundancies are declared inherent in the logical needs of the community of users and not removable by the system or data base administrator, so some cross-relation constraints must be carried and checked indefinitely rather than designed away. (conceded)

What it became — the systems that inherited it

IBM's System R turned this paper into a running system: SEQUEL, later SQL, is a concrete syntax for Codd's universal data sublanguage, and System R's cost-based optimizer is the answer to the efficiency question Codd deliberately left open. Berkeley's INGRES built a second, independent implementation with QUEL, and that lineage runs through Postgres to PostgreSQL, while Oracle, DB2, Informix, and Sybase commercialized the same model; Codd received the 1981 Turing Award for it. The operations defined in Section 2 — projection, restriction, natural join, composition — became the physical operator vocabulary of essentially every query engine since, from System R's nested-loop and sort-merge joins to modern vectorized and distributed engines such as Spark SQL, Presto, and BigQuery. What this paper calls normal form is what later became first normal form; the copy-the-parent-key procedure of Figure 3 is the direct ancestor of Codd's second and third normal forms, of Boyce-Codd normal form, and of the fourth and fifth normal forms, while the primary and foreign key pair became SQL's referential integrity constraints. The connection trap has aged remarkably well: it is precisely the argument against assuming that pointer traversal in hierarchical, object, document, or graph stores computes a correct join, replayed in every subsequent navigational-versus-relational debate. Even systems that abandoned SQL syntax largely came back to relational semantics — Google's Spanner and F1, Cassandra's CQL, and the SQL layers over Hadoop all reintroduced tables, declared keys, and declarative queries over the navigational alternatives.

In the paper’s words — verbatim

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

Abstract

“It provides a means of describing data with its natural structure only — that is, without superimposing any additional structure for machine representation purposes.”

§1.1

“A lack of understanding of relational composition has led several systems designers into what may be called the connection trap.”

§2.1.4

Vocabulary — as this paper uses it

relation (of degree n): A set of n-tuples drawn from n named domains S1 through Sn, equivalently a subset of their Cartesian product. Degree 1, 2, and 3 relations are called unary, binary, and ternary.
relationship: The domain-unordered counterpart of a relation, formally an equivalence class of relations that are equivalent under permutation of domains. This is what users are meant to interact with, so column position never appears in their model.
primary key: A domain or combination of domains whose values uniquely identify each n-tuple of a relation. It is nonredundant if no participating simple domain is superfluous, and one nonredundant key is chosen arbitrarily when a relation has several.
foreign key: A domain or domain combination of relation R that is not the primary key of R but whose elements are values of the primary key of some relation S, where S may be R itself. In the relation supply, supplier, part, and project are each foreign keys.
nonsimple domain: A domain whose elements are themselves relations rather than atomic values, roughly what existing terminology called a repeating group. Codd's example is salary history as a domain of the employee relation.
normal form: The state in which every relation is defined only on simple domains, so that each is representable as a two-dimensional column-homogeneous array. It is reached by the normalization procedure that copies parent primary keys into subordinate relations.
natural join: For binary R and S with π2(R) = π1(S), the ternary relation consisting of all (a,b,c) with R(a,b) and S(b,c). It is the join that always exists in that case, it is associative, and its projections recover R and S exactly.
point of ambiguity: An element of the joining domain that has more than one relative under R and also more than one under S. Its presence is what allows several distinct joins of R with S to exist.
connection trap: The erroneous conclusion that following all pointer paths from a supplier through parts to projects yields the valid set of projects supplied by that supplier. It is correct only when the target relation is, for all time, the natural composition of the other two.

On the timeline — where this sits in the story

Year1970

MilestoneRelational model

Problem solvedUsers had to navigate physical record links; applications were tightly coupled to access paths and storage details.

How it solved itCodd proposed representing data as relations/tables and using formal logic so users specify what they want, not how to traverse records.

Why it matteredEstablished logical data independence, declarative querying, and the foundation for SQL databases.

DDIACh. 3: Data Models

View on the timeline