Database Theory

Database theory is the mathematical study of what databases can and cannot do.

12 frameworks, from 1969 to today · Databases · Computer Science

still a working view ended · each leads to its entry below

Overview

Database theory is the mathematical study of what databases can and cannot do1. Its practitioners ask: what does it mean for a query to be correct? When can a query be answered efficiently? What guarantees must a system provide when many users act at once? The field matters because every database system — from a bank's ledger to a phone's contact list — rests on answers to these questions. Theory tells builders which designs are sound and which are doomed, and it gives users a precise language for saying what they want.

The Relational Turn (1969–1974)

Before the 1970s, databases were navigational: programs walked pointers through hierarchical or network structures, and the programmer had to know the physical layout2. Edgar F. Codd, a mathematician at IBM, proposed in 1969–1970 that data be stored as simple tables (relations) and queried by describing the result, not the path to it. His relational model separated the logical description of data from its physical storage3.

Codd gave the model two formal faces. Relational algebra is a set of operations — selection (pick rows), projection (pick columns), join (combine tables), union, difference — that take relations to relations4. Relational calculus is a logical language: a query states "the set of tuples t such that P(t)," where P is a predicate in first-order logic5. Codd showed the two are equivalent in expressive power156. This equivalence was the field's founding insight: a declarative description and an algebraic procedure could be the same thing. A user could write a logical condition and a system could, in principle, evaluate it by any equivalent algebraic plan.

Normalization and the Study of Dependencies (1970s)

Codd immediately noticed a practical problem: badly designed tables duplicate facts and create update anomalies. His answer was normalization — decomposing tables into smaller ones without losing information7. The theoretical engine was functional dependency: a statement that whenever two rows agree on attribute set X, they must agree on Y. Codd defined first, second, and third normal forms; later work by Raymond Boyce and Codd produced Boyce–Codd normal form.

The 1970s turned this into a mature theory. Philip Bernstein, David Maier, and others studied multivalued and join dependencies, and Ronald Fagin characterized when a decomposition is lossless. The central question — given a set of dependencies, what decompositions preserve information and avoid redundancy? — became a well-defined combinatorial problem. Normalization theory gave designers a discipline: model the facts, derive the dependencies, decompose accordingly. It remains the standard justification for schema design.

Query Languages and Logic (1970s–1980s)

Codd's calculus was first-order logic over finite structures. In the mid-1970s, Michel Lacroix and Alain Pirotte, and independently Robert Demolombe, developed a domain-independent fragment that avoided nonsensical queries, and the language became the basis of QUEL. Meanwhile, Donald Chamberlin and Raymond Boyce at IBM designed SEQUEL (later SQL), which combined relational operations with a block-structured syntax. SQL became the commercial standard, but its semantics were informal; theory supplied the precision.

A key result was that relational calculus without recursion is exactly first-order logic, and its expressive power is limited: it cannot compute transitive closure (e.g., "all ancestors of a person") without recursion1. This limitation motivated the next wave.

Transactions and Concurrency (1970s–1980s)

As databases became multi-user, the question arose: what does it mean for concurrent transactions to be correct? The answer was serializability — a schedule of interleaved operations is correct if it is equivalent to some serial execution. Codd and others formalized this; Philip Bernstein, Vassos Hadzilacos, and Nathan Goodman systematized the theory in the 1980s.

The field developed conflict serializability (based on conflicting read/write operations), view serializability, and the two-phase locking protocol that guarantees conflict serializability. Jim Gray's work on transaction processing, including the ACID properties (atomicity, consistency, isolation, durability), gave the field its vocabulary. The theoretical contribution was to show which protocols are safe and which allow anomalies, and to prove impossibility results — for example, that no protocol can guarantee serializability without blocking or aborting in some cases. This theory directly shaped commercial systems.

Query Optimization and Complexity (1970s–1990s)

If a query is declarative, the system must choose an execution plan8. Patricia Selinger and colleagues at IBM published the first cost-based optimizer in 1979, using dynamic programming to choose join orders. Theory asked: how hard is it to find the best plan? The answer, in general, is NP-hard, so optimizers use heuristics and restricted search.

A parallel line studied the complexity of query evaluation and containment. Chandra and Merlin (1977) showed that containment of conjunctive queries — whether every answer to query Q1 is also an answer to Q2 — is decidable and equivalent to finding a homomorphism between query patterns. This connected database theory to finite model theory and constraint satisfaction. Later work by Ashok Chandra, Moshe Vardi, and others established the data complexity versus expression complexity distinction: how hard is a query as the data grows, versus as the query grows? These results told designers which query languages could be evaluated efficiently and which could not.

Deductive Databases and Logic Programming (1980s)

The idea that a database could store rules as well as facts led to deductive databases9. Datalog, a recursive query language based on Prolog, allowed rules like "ancestor(X,Y) :- parent(X,Y)" and "ancestor(X,Z) :- parent(X,Y), ancestor(Y,Z)."910 The theoretical challenge was semantics: what does a set of recursive rules mean? The answer came from logic programming — the least fixed-point semantics, developed by Alain Colmerauer, Robert Kowalski, and others — and from work by Jeffrey Ullman, Alfred Aho, and others on recursive query evaluation. Datalog became a bridge between database theory and logic programming, and its descendants (e.g., in ontology languages and program analysis) remain active.

Objects, Incomplete Information, and Data Exchange (1980s–2000s)

The relational model assumed flat tables. Object-oriented databases in the 1980s added complex objects, inheritance, and methods; object-relational systems extended SQL with user-defined types21112. Theory responded with models for nested relations and complex values, and with query languages that could handle them.

A deeper problem was incomplete information. Real databases often lack facts, and queries over them must return certain answers — answers true in every possible completion13. This led to the theory of null values, conditional tables, and certain answers, developed by Tomasz Imieliński, Witold Lipski, and later Ron Fagin, Phokion Kolaitis, and Lucian Popa. The same machinery powered data exchange: given a source database and a set of mappings to a target schema, what target instances are guaranteed? Fagin, Kolaitis, and others characterized when a universal solution exists and how to compute it, with applications to data integration and schema mapping.

Provenance (2000s–present)

As data flowed through queries, users wanted to know where results came from. Provenance theory formalized this: given a query and an output tuple, which input tuples contributed, and how14? Work by Peter Buneman, Sanjeev Khanna, Wang-Chiew Tan, and others defined why-provenance (which input facts suffice), how-provenance (algebraic annotations), and where-provenance (which source locations). The theory connected to semirings and to the study of query equivalence, and it now underpins debugging tools, data lineage in pipelines, and reproducibility in science.

The Present

Database theory today is a mature field with several active fronts. Finite model theory and descriptive complexity continue to characterize what query languages can express. Datalog and its extensions are central to knowledge representation, program analysis, and distributed computation. Certain answers and data exchange theory inform data integration and ontology-based querying. Provenance and annotation semantics are increasingly important for machine learning pipelines and data governance. Transaction theory has expanded to distributed and weakly consistent systems, where the classic serializability guarantees are relaxed and new correctness criteria are studied. Query optimization theory now addresses adaptive and learning-based planners. The founding questions — what does a query mean, when can it be answered efficiently, and what guarantees can a system provide — remain the field's compass.

References

  1. Database theory, Wikipedia
  2. Database (History), Wikipedia
  3. Relational model, Wikipedia
  4. Relational algebra, Wikipedia
  5. Relational calculus, Wikipedia
  6. Tuple relational calculus, Wikipedia
  7. Database normalization, Wikipedia
  8. Query plan, Wikipedia
  9. Deductive database, Wikipedia
  10. Datalog, Wikipedia
  11. Object–relational database, Wikipedia
  12. Object database, Wikipedia
  13. Certain answer, Wikipedia
  14. Data lineage (Data provenance), Wikipedia

The frameworks of Database Theory

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1969-Present

    Relational model

    How can data be described as simple tables?

    Fly to its tower in Nousfarer

  2. 1970-Present

    Database normalization

    How should tables be split to avoid redundancy?

    Fly to its tower in Nousfarer

  3. 1971-Present
  4. 1975-Present

    Database transaction

    When is concurrent access to data correct?

    Fly to its tower in Nousfarer

  5. 1977-Present
  6. 1979-Present

    Query optimization

    Which execution plan should a system choose?

    Fly to its tower in Nousfarer

  7. 1980-Present

    Deductive databases and Datalog

    What do recursive rules over facts mean?

    Fly to its tower in Nousfarer

  8. 1980-Present

    Finite model theory

    What can logical languages express on finite data?

    Fly to its tower in Nousfarer

  9. 1982-Present
  10. 1985-2000
  11. 2000-Present

    Data exchange and schema mapping

    What target data is guaranteed by a mapping?

    Fly to its tower in Nousfarer

  12. 2000-Present

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Relational modelDatabase normalizationRelational calculus and logic-based q…Database transactionQuery optimization and complexity the…Query optimizationDeductive databases and DatalogFinite model theoryIncomplete information and certain an…Complex-value and object-oriented dat…Data exchange and schema mappingProvenance and annotation semantics

Beyond the field

Where Database Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 68 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Database Theory is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Database Theory

Related fields

Fields its ideas are linked to

More in Databases

See where Database Theory sits on the Map of Human Knowledge