- Atlas
- Computer Science
- Database Theory
Database Theory
Database theory is the mathematical study of what databases can and cannot do.
12 frameworks, from 1969 to today · Databases · Computer Science
- Relational model 1969-Present
- Database normalization 1970-Present
- Relational calculus and logic-based query theory 1971-Present
- Database transaction 1975-Present
- Query optimization and complexity theory 1977-Present
- Query optimization 1979-Present
- Deductive databases and Datalog 1980-Present
- Finite model theory 1980-Present
- Incomplete information and certain answers 1982-Present
- Complex-value and object-oriented data models 1985-2000
- Data exchange and schema mapping 2000-Present
- Provenance and annotation semantics 2000-Present
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
- Database theory, Wikipedia
- Database (History), Wikipedia
- Relational model, Wikipedia
- Relational algebra, Wikipedia
- Relational calculus, Wikipedia
- Tuple relational calculus, Wikipedia
- Database normalization, Wikipedia
- Query plan, Wikipedia
- Deductive database, Wikipedia
- Datalog, Wikipedia
- Object–relational database, Wikipedia
- Object database, Wikipedia
- Certain answer, Wikipedia
- 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.
- 1969-Present
- 1970-Present
- 1971-Present
Relational calculus and logic-based query theory
What can be asked of data in pure logic?
- 1975-Present
- 1977-Present
Query optimization and complexity theory
How hard is it to answer a query?
- 1979-Present
- 1980-Present
Deductive databases and Datalog
What do recursive rules over facts mean?
- 1980-Present
- 1982-Present
Incomplete information and certain answers
What is true when data is incomplete?
- 1985-2000
Complex-value and object-oriented data models
How can data hold nested and structured objects?
- 2000-Present
Data exchange and schema mapping
What target data is guaranteed by a mapping?
- 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.
Database normalization grew out of Relational model
Codd derived normalization directly from his relational model, defining first, second, and third normal forms to remove redundancy from relations. Functional dependencies and lossless decomposition were formulated as properties of relational schemas.
Carried by Edgar F. Codd.
Relational calculus and logic-based query theory grew out of Relational model
Codd presented relational calculus as one of the two formal faces of the relational model and proved it equivalent to relational algebra. Later logic-based query theory refined this first-order calculus over finite structures.
Carried by Edgar F. Codd.
Data exchange and schema mapping grew out of Incomplete information and certain answers
Data exchange theory grew directly out of the certain-answers framework: given source data and schema mappings, one asks which target instances are guaranteed. Fagin, Kolaitis, and Popa carried over conditional tables and certain answers to characterize universal solutions.
Carried by Ronald Fagin; Phokion Kolaitis; Lucian Popa.
Query optimization and complexity theory grew out of Relational model
The declarative character of relational queries raised the question of how to evaluate them efficiently, and Chandra and Merlin's containment results for conjunctive queries were posed within the relational framework. Complexity of query evaluation was studied for relational algebra and calculus.
Carried by Ashok Chandra; Philip Merlin.
Incomplete information and certain answers grew out of Relational model
The theory of incomplete information arose within the relational model, asking what a query means when relations are only partially known. Null values and conditional tables were defined as extensions of relational instances.
Carried by Tomasz Imieliński; Witold Lipski.
Complex-value and object-oriented data models reacted against Relational model
Object-oriented and complex-value data models defined themselves against the relational model's flat tables, adding nested structures, inheritance, and methods. The movement argued the relational assumption of first normal form was too restrictive for new applications.
Query optimization and complexity theory influenced by Relational calculus and logic-based query theory
Logic-based query theory supplied the conjunctive-query and homomorphism machinery that Chandra and Merlin used to settle query containment, a core problem in query optimization. The data versus expression complexity distinction was framed for logical query languages.
Carried by Ashok Chandra; Philip Merlin.
Deductive databases and Datalog grew out of Relational calculus and logic-based query theory
Datalog extended the first-order relational calculus with recursive rules, addressing the calculus's inability to express transitive closure. The least fixed-point semantics gave the recursive extension a precise meaning.
Carried by Alfred Aho; Jeffrey Ullman.
Finite model theory grew out of Relational calculus and logic-based query theory
Finite model theory grew out of the study of first-order query languages over finite relational structures, asking which properties such languages can express. Descriptive complexity characterized query languages by the complexity classes they capture.
Carried by Moshe Vardi.
Provenance and annotation semantics influenced by Relational calculus and logic-based query theory
Provenance theory built on the algebraic and logical semantics of queries, annotating relational operations to track which input tuples contributed to an output. How-provenance used semiring annotations over the same query algebra.
Carried by Peter Buneman; Sanjeev Khanna; Wang-Chiew Tan.
Finite model theory influenced by Deductive databases and Datalog
Recursive query languages such as Datalog raised expressiveness questions that finite model theory took up, comparing fixed-point logics with first-order logic over finite structures. The study of recursion in databases fed into descriptive complexity.
Provenance and annotation semantics influenced by Deductive databases and Datalog
Annotation and provenance semantics drew on the rule-based view of queries from deductive databases, treating provenance as an annotation propagated through derivation rules. The connection linked lineage to logic-programming 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.
Relational model reacted against Network model in Data Modeling
Codd presented the relational model explicitly as an alternative to the pointer-based network (CODASYL) model, arguing that data independence required abandoning navigation by links. The relational model defined itself against the network model's record-at-a-time access.
Carried by Edgar F. Codd; A Relational Model of Data for Large Shared Data Banks (1970).
Relational model led to Semantic data model in Data Modeling
Semantic data modeling grew out of the relational model by adding abstraction constructs (entities, generalization, aggregation) to flat relations.
Carried by Peter Pin-Shan Chen; Michael Hammer; Dennis McLeod.
Relational model led to Entity-relationship model in Data Modeling
The entity-relationship model grew out of Codd's relational model, adopting its treatment of data as sets of records while adding a conceptual entity/relationship layer.
Carried by Peter Pin-Shan Chen; Edgar F. Codd.
Relational model influenced Physical operator and access-method design in Query Processing
Physical operator and access-method design implemented the relational model's operators, taking Codd's relational algebra as the specification of what operators such as join, select, and project must compute. Access methods were designed to realize these relational operations efficiently.
Carried by Edgar F. Codd.
Database normalization grew out of Relational model in Databases
Database normalization is a branch of the relational model, formulated by Codd in terms of relations and functional dependencies. The later theory refines the earlier model's treatment of redundancy.
Carried by Edgar F. Codd.
Database normalization grew out of Relational model in Data Modeling
Normalization was developed directly out of Codd's relational model, using functional dependencies over relations to define first, second and third normal forms. It is a refinement within the relational framework rather than an independent doctrine.
Carried by Edgar F. Codd; Further Normalization of the Data Base Relational Model (1971).
Relational calculus and logic-based query theory led to Deductive database in Computational Logic
Deductive databases grew directly out of Codd's relational calculus and the logic-based query theory built on it. Datalog and the deductive database model extended relational query languages with recursive rules.
Carried by Edgar F. Codd.
Relational calculus and logic-based query theory influenced Query optimization in Databases
Query optimization rests on the equivalence of relational calculus expressions and their algebraic rewritings, so that logically equivalent queries can be transformed into cheaper plans. Codd's relational calculus and algebra supplied the equivalence laws the optimizers exploit.
Carried by E. F. Codd.
Database transaction influenced Optimistic Concurrency Control in Transaction Processing
Kung and Robinson's optimistic concurrency control was formulated directly for database transactions, using the transaction as its unit of validation and serializability as its correctness criterion. The paper appeared in ACM TODS in 1981 and built on the transaction concept developed in the 1970s.
Carried by H. T. Kung; John T. Robinson; On Optimistic Methods for Concurrency Control (1981).
Database transaction influenced Deterministic Transaction Execution in Transaction Processing
The database transaction concept, with its begin/commit/abort semantics and serializability criterion, is the object that deterministic execution systems re-implement without locking; the later work takes the transaction abstraction and its correctness conditions directly from database theory.
Database transaction led to ACID in Transaction Processing
ACID properties were formulated as a summary of the guarantees that database transaction systems already provided; the transaction concept is the object whose properties ACID names.
Carried by Theo Härder; Andreas Reuter; Principles of Transaction-Oriented Database Recovery (1983).
Database transaction led to Distributed transaction in Distributed Databases
Distributed transactions extended the single-node database transaction concept to multiple sites, keeping atomicity and serializability as the goal. The two-phase commit protocol and distributed concurrency control were built directly on the local transaction model.
Carried by Jim Gray.

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 TheoryRelated fields
Fields its ideas are linked to
- Data Modeling 12 links
- Databases 12 links
- Query Processing 7 links
- Transaction Processing 7 links
- Distributed Databases 4 links
- Nosql Systems 3 links
- Computational Logic 3 links
- Data Science 2 links
- Model Theory 2 links
- Logic 2 links
- Complexity Theory 2 links
- Knowledge Representation Reasoning 1 link
More in Databases
See where Database Theory sits on the Map of Human Knowledge