What a database is, and where it came from

1What we mean by a database

Start with the plainest answer, from the manual of the database this site runs on. PostgreSQL calls itself a relational database management system: a system for managing data stored in relations, where relation is essentially the mathematical word for a table (PostgreSQL 18 docs, §2.2). The same page adds something surprising. Files and directories on a Unix-like operating system are themselves an example of a database, a hierarchical one (PostgreSQL 18 docs, §2.2).

So a folder of files already stores data. What it lacks is the second half of the name, the management system. Donald Chamberlin, one of the two people who designed SQL, describes the field as it looked in the early 1970s: the problem was persistent data, data that stays in a computer until someone explicitly deletes it, and systems for managing it were spreading quickly through business (Chamberlin 2012, p. 78). The paper the next lecture reads is titled for large shared data banks, and says it is about systems that give shared access to large banks of formatted data (Codd 1970, p. 377).

Persistent, large and shared: those three words are the whole story of this lecture. Each step below, from cards to Postgres, was taken because the step before could not keep one of three promises that a folder of files leaves to every program that touches it.

Ask without knowing the layout. A program should be able to ask a question of the data without knowing how it is arranged, and keep working when the arrangement changes. Codd called this data independence (Codd 1970, p. 377).

Many at once. Many people and programs should be able to use the data at the same time without corrupting it. Postgres runs as a server that accepts many concurrent connections from clients (PostgreSQL 18 docs, §1.2).

All or nothing, and then for good. A change made of several steps, such as moving money from one account to another, either happens completely or not at all, and once the database says it is done, a crash does not undo it (PostgreSQL 18 docs, §3.4).

2Cards: a record you could hold

The story starts with a counting problem. By 1870 the United States census had grown so large that clerks could no longer tabulate it accurately by hand, and the results of the 1880 census were not finished until 1887 (US Census Bureau, Tabulation and Processing). In 1888 the Census Office held a competition: process the 1880 returns of four areas of St. Louis, fastest wins the contract for 1890 (US Census Bureau, The Hollerith Machine).

Three contestants entered. Herman Hollerith, a former Census employee, captured the data in 72.5 hours against 144.5 and 100.5 for the other two, and prepared it for tabulation in 5.5 hours against 44.5 and 55.5 (US Census Bureau, The Hollerith Machine). He won.

His machine read punched cards, each holding one person's census data (US Census Bureau, Tabulation and Processing). Each hole position stood for a specific category, so the meaning of a hole was its place on the card. A clerk closed a reader over the card, pins passed through the holes into cups of mercury, and each completed circuit advanced a counting dial. A sorting table beside the machine then told the clerk which drawer the card went into (US Census Bureau, The Hollerith Machine).

The 1890 count finished months ahead of schedule and far under budget. In 1896 Hollerith founded the Tabulating Machine Company, which after mergers became International Business Machines, IBM (US Census Bureau, Tabulation and Processing).

Two ideas from the card outlive it. A record is one thing described in fixed fields, and the card was one person in fixed hole positions. And grouping records meant physically sorting them: to count by a different category, you sorted the deck again. Hold on to that second idea, because the next sixty years kept running into it.

3Tape: a file in one order

Electronic computers took over the counting. The Census Bureau commissioned UNIVAC I, first used on the 1950 census, which tabulated 4,000 items a minute, twice what the electro-mechanical machines managed (US Census Bureau, Tabulation and Processing). In the 1950s the Bureau and the National Bureau of Standards developed FOSDIC, which read questionnaires photographed onto microfilm and wrote the answers to magnetic tape, the input for the Bureau's computers (US Census Bureau, Tabulation and Processing). Tape kept the deck's character: it is read in sequence, from the beginning, one record after another (Bachman 2004, p. 33).

Charles Bachman, who went on to build the first database management system, described in a 2004 interview how a tape system he admired worked, the file maintenance and report generator built at Hanford for an IBM 702 (Bachman 2004, p. 24). The master file lived on tape. Each update copied the entire file from one set of tapes to another, changing some records on the way, and was repeated weekly, monthly or in some cases daily; every pass was also the chance to print reports (Bachman 2004, p. 25).

A deck or a tape can be in only one order at a time. Bachman recalls files being sorted by material item for the inventory reports and then sorted back the other way for the sales reports (Bachman 2004, p. 33). And programs came to rely on the order they found. Codd describes the result in 1970: systems let a program assume records arrive in the order they are stored, and a program that takes advantage of that order is likely to fail when the order has to change (Codd 1970, pp. 377 to 378).

Here is that failure, run for real. The file holds the prices that System R's 1981 paper uses as its example: which supplier sells which part, at what price (Chamberlin et al. 1981, p. 633). The program was written while the tape was sorted by part, and it stops reading at the first record past the part it wants. The query asks the same question without saying anything about order.

for each record on the tape:
  if part > 'P113': stop
  if part = 'P113': keep lowest price

SELECT min(price) FROM prices
WHERE part = 'P113';

Notice what does not happen when the tape is re-sorted: nothing fails. The program finishes and prints an answer: the wrong price for nuts, no price at all for screws, while bolts and gears still come out right. A program that is wrong for some inputs and right for others is the kind that survives testing.

4Disk, and the programmer as navigator

Disk changed the constraint. In Bachman's words, moving from tape to disk meant direct access instead of sequential access: a program could reach any record if it knew where to look, so a record could belong to more than one grouping at once instead of being sorted into one (Bachman 2004, p. 33).

At General Electric, Bachman designed the Integrated Data Store, IDS, to hold the networks of manufacturing data needed by a manufacturing control system; he calls IDS the first database management system (Bachman 2004, p. 45). Its specifications were reviewed by a group of GE departments in the fall of 1961 (Bachman 2004, p. 50). GE's computer department had almost no disk files at the time, so the team first debugged IDS on two tape drives made to imitate one (Bachman 2004, p. 51). IDS introduced the network data model, and the database standards of the CODASYL Data Base Task Group in the late 1960s were heavily influenced by it (Bachman 2004, p. 2).

IBM's line ran through the space program. In 1963 IBM's Uri Berman and Rockwell's Peter Nordyke answered an urgent request from the space program for a parts tracker, and the system, called ICS/DL/I, printed its first "READY" on 14 August 1968 at the Rockwell Space Division in Downey, California, tracking the bills of material for millions of parts (IBM, IMS history). Renamed IMS for the commercial market, it combined a database built on a hierarchical data model with software for high-volume transactions such as cash machine withdrawals and travel reservations (IBM, IMS history).

These systems stored facts in two ways: in the contents of records, and in the connections between records, called links, sets, chains or parents depending on the system. To ask a question, a user wrote a program that navigated through the connections until it reached the answer, and the program then depended on the structure that existed when it was written (Chamberlin et al. 1981, p. 632). Chamberlin recalls learning the CODASYL language this way, writing each query as a program that walked a network of pointers (Chamberlin 2012, p. 78).

IBM's own history of IMS is candid about the cost. IMS was very efficient when where to look was obvious, but specialists had to hardcode the instructions for each search, and when the data changed, queries often had to be rewritten with new pointers (IBM, IMS history). Disk had removed the single order of the tape, and replaced it with the paths between records. The program still knew how the data was laid out.

5Codd's answer: facts as values

In 1970 E. F. Codd, at IBM's research laboratory in San Jose, proposed something different. The systems of the day gave users tree-structured files or slightly more general network models; he proposed a model based on relations instead (Codd 1970, p. 377). The System R paper sums up what that meant in practice: every piece of information is represented by data values, never by connections the user can see, and the user asks in a high-level language without spelling out how to find the answer (Chamberlin et al. 1981, pp. 632 to 633).

The question "What is the lowest price for bolts?" becomes SELECT MIN(PRICE) FROM PRICES WHERE PARTNO IN (SELECT PARTNO FROM PARTS WHERE NAME = 'BOLT') (Chamberlin et al. 1981, p. 633). The system may keep whatever pointers or indexes it finds useful, but the question is not written in terms of them, so the system can change its representation without disturbing the programs that ask (Chamberlin et al. 1981, p. 633). That is the first promise, kept by the design of the language.

How Codd defined a relation, what keys are, and why following connections can claim facts that are not true, is the next lecture, which reads his paper page by page.

6SQL, and the proof that it could be fast

Codd's proposal had two open questions: could ordinary users write in it, and could a machine run it as fast as a trained programmer's navigation? Donald Chamberlin and Raymond Boyce met Codd at a symposium he organised at IBM's Watson Research Center in 1972, and were struck by how a query that needed a complex program in the CODASYL language shrank to a few lines in his languages (Chamberlin 2012, p. 78). But those languages used mathematical symbols hard to type at a keyboard and concepts from set theory and logic, and the two wanted a language that people without that training could use (Chamberlin 2012, p. 78).

Their first attempt, Square, used a subscript notation that was hard to type. After moving to San Jose in 1973 to join the System R project they designed Sequel, which describes the information it wants and leaves the plan for finding it to an optimizing compiler: a declarative language (Chamberlin 2012, p. 79). Boyce, who also gave his name to Boyce-Codd normal form, died suddenly in 1974 at 26 (Chamberlin 2012, p. 79). In 1977 a trademark issue shortened Sequel to SQL (Chamberlin 2012, pp. 79 to 80).

System R was the second question. It was built at IBM San Jose to show that a relational system could have the complete function and high performance that everyday production use requires, at a time when people doubted an automatic system could choose as good an algorithm as a programmer (Chamberlin et al. 1981, pp. 632 to 633). A first prototype for one user at a time came in 1974 and 1975, the full multiuser system in 1976 and 1977, and evaluation in real use in 1978 and 1979 (Chamberlin et al. 1981, p. 634).

The multiuser version kept the other two promises. Its locking subsystem let each data value be used by one user at a time, made all of a transaction's updates take effect together, and detected deadlocks; its recovery subsystem could restore the database to a consistent state after a hardware or software failure (Chamberlin et al. 1981, pp. 635 to 636). Even the description of the database, the catalog, was stored as ordinary relations in the database itself (Chamberlin et al. 1981, p. 634).

The first installations came in June 1977. Several sites reported installing the system, designing and loading a database and running applications within days, and tuning performance afterwards by creating and dropping indexes without disturbing users or programs; users with no prior experience learned a usable subset of SQL at their first sitting (Chamberlin et al. 1981, p. 639). Commercial SQL systems such as Oracle and DB2 appeared in the late 1970s and early 1980s, and by 1986 ANSI and ISO had adopted a standard definition, Database Language SQL (Chamberlin 2012, p. 80).

7Postgres

The other early relational system was built at a university. INGRES was implemented at the University of California between 1975 and 1977. Michael Stonebraker and Lawrence Rowe later judged it too hard to extend, and designed a successor named for what it came after: POSTGRES, post-Ingres (Stonebraker and Rowe 1986, p. 1). Its goals included better support for complex objects, letting users add their own data types, operators and access methods, simpler crash recovery, and as few changes as possible to the relational model (Stonebraker and Rowe 1986, p. 1).

Implementation began in 1986, and a first version reached a few outside users in June 1989; the Berkeley project ended with version 4.2 (PostgreSQL 18 docs, Preface §2). Its query language was not SQL but PostQUEL. In 1994 Andrew Yu and Jolly Chen added an SQL interpreter, and the result, Postgres95, was released on the web as open source (PostgreSQL 18 docs, Preface §2). In 1996 it was renamed PostgreSQL, with version numbers restarting at 6.0 to continue the Berkeley sequence, and Postgres remains an official name (PostgreSQL 18 docs, Preface §2).

Today the three promises are in its manual. A query never says how rows are stored, and SQL does not guarantee the order of rows in a table unless you ask for a sort (PostgreSQL 18 docs, §2.2): the tape program's mistake is ruled out by the language. The server accepts many connections at once, starting a process for each (PostgreSQL 18 docs, §1.2), and with multiversion concurrency control, reading never blocks writing and writing never blocks reading (PostgreSQL 18 docs, §13.1).

“The essential point of a transaction is that it bundles multiple steps into a single, all-or-nothing operation.”

And a transaction's updates are logged on disk before it is reported complete, so a crash just afterwards does not lose it (PostgreSQL 18 docs, §3.4). The manual calls transactions a fundamental concept of all database systems (PostgreSQL 18 docs, §3.4): not a Postgres feature, but what the word database came to mean.

8Where the next lecture begins

Cards made a record something you could hold, and sorting was how you asked a new question. Tape made files fast but kept them in one order, and programs learned that order. Disk freed the order, and navigational systems traded it for paths that programs learned instead. Each time, the program knew too much about the layout.

Codd's 1970 paper was written against exactly that problem, and opens by naming it: future users of large data banks should not have to know how the data is organised in the machine (Codd 1970, p. 377). The next lecture reads it page by page.