Loading field map
Database theory is the branch of computer science concerned with the mathematical and logical foundations of data management. It studies what it means to store, query, and update data in a way that is precise, efficient, and correct. While database systems engineering builds the software that manages data at scale, database theory asks more abstract questions: What is a query, exactly? When do two queries mean the same thing? What can be computed from a database, and at what cost? The field's results take the form of formal models, complexity classifications, and logical characterizations, and they underpin the design of query languages, database schemas, and query optimizers.
At the heart of database theory is the relational model, introduced by Edgar F. Codd in 1970. A relational database is a collection of tables (relations), each with a fixed set of columns (attributes) and rows (tuples). The model's key insight was to separate the logical structure of data from its physical storage, allowing users to interact with data through a high-level, declarative language. The relational model also introduced a rigorous notion of schema: the structure of a table, including its attributes and the types of values they may hold, is distinct from the data itself. This separation enables a clean theory of query languages, constraints, and database design.
The dominant query language for relational databases is SQL, but database theory typically works with more abstract formalisms. The most important of these is relational algebra, a set of operations on relations—selection, projection, join, union, difference, and renaming—that can be composed to form queries. Relational algebra is procedural in flavor: it describes how to compute a query. Its logical counterpart is relational calculus, which describes what a query returns using first-order logic. A foundational result, Codd's theorem, states that relational algebra and relational calculus have exactly the same expressive power: every query expressible in one is expressible in the other. This equivalence is the theoretical justification for declarative query languages: users can write a query in a logical language, and the system can translate it into an algebraic plan for execution.
A central question in database theory is: What can a given query language express? This is studied through the lens of logic. First-order logic, the language of relational calculus, is the baseline. It can express queries such as "find all employees who earn more than their manager" or "find all pairs of cities connected by a direct flight." But first-order logic has a well-known limitation: it cannot express recursive queries, such as "find all cities reachable from Paris by any number of flights." This limitation motivated the study of extensions to first-order logic, including fixed-point logics, which add recursion, and Datalog, a logic-based query language that supports recursive rules. Datalog has become a major topic in its own right, both as a theoretical object and as a practical language for graph queries and data integration.
Another fundamental question is the complexity of query evaluation. Given a database and a query, how hard is it to compute the answer? The answer depends on what is being measured. In data complexity, the query is fixed and the database varies; in combined complexity, both vary. For first-order queries, data complexity is in the class LOGSPACE, meaning it is quite tractable. But combined complexity is PSPACE-complete for relational calculus, indicating that query evaluation can be intractable when the query itself is large. These results are not merely academic: they guide the design of query optimizers, which must find efficient evaluation strategies, and they explain why practical query languages restrict expressive power in certain ways.
Databases are not just collections of data; they are expected to satisfy certain constraints. A constraint is a condition that every valid database instance must meet, such as "every employee has a unique ID" or "every order references an existing customer." The theory of integrity constraints studies the logical form of such conditions and their consequences. The most important classes are functional dependencies, which generalize keys, and inclusion dependencies, which generalize foreign keys. These constraints are central to database design, where the goal is to produce a schema that avoids redundancy and update anomalies. The process of normalization—decomposing a relation into smaller, well-structured relations—is guided by the theory of functional dependencies. The Boyce-Codd normal form and the third normal form are criteria that ensure certain kinds of redundancy are eliminated, and the theory provides algorithms for testing and achieving these forms.
Constraints also raise the question of implication: given a set of constraints, what other constraints must necessarily hold? For functional dependencies, this question has a complete and elegant answer in Armstrong's axioms, a sound and complete proof system. For more expressive constraint languages, the implication problem can be undecidable, a result that has important consequences for data integration and schema matching.
When multiple users access a database simultaneously, the system must ensure that their operations do not interfere in harmful ways. The theory of transactions studies how to guarantee that concurrent executions produce the same result as some serial execution. The central notion is serializability: a schedule of operations is serializable if it is equivalent to a sequential execution of the transactions. The theory identifies sufficient conditions for serializability, such as conflict serializability, which is based on the order of conflicting operations (reads and writes on the same data item). This theory underpins the isolation levels offered by database systems, which trade strict correctness for performance. The ACID properties—atomicity, consistency, isolation, durability—are the practical embodiment of these theoretical guarantees, though the theory makes precise what each property means in formal terms.
Real-world data is often incomplete, inconsistent, or uncertain. Database theory has developed formal models for these situations. The simplest model of incomplete information is the null value, which represents "unknown" or "does not exist." But nulls are semantically tricky: query evaluation with nulls requires three-valued logic (true, false, unknown), and the results can be counterintuitive. More sophisticated approaches use maybe tables, which represent a set of possible databases, and query answers are then sets of tuples that are certain (present in all possible databases) or possible (present in some). This line of work connects to the theory of data exchange and data integration, where data from multiple sources must be combined despite inconsistencies.
Modern data management often involves combining data from multiple, heterogeneous sources. Data integration is the problem of providing a unified query interface over such sources. The theoretical framework distinguishes between a global schema, which users query, and local schemas, which describe the actual data sources. Mappings between the global and local schemas are expressed in a formal language, and the central question is how to answer queries posed against the global schema using only the local data. This is the problem of query rewriting, and its difficulty depends on the expressiveness of the mapping language. Data exchange is a related but distinct problem: instead of answering queries over sources, the goal is to materialize a database instance of the target schema that satisfies the mappings. The theory of data exchange studies when such a target instance exists, how to construct a canonical one, and how to answer queries over the exchanged data.
The relational model was not the first data model, nor is it the only one. It succeeded earlier hierarchical and network models, which were navigational in nature: users accessed data by following explicit links between records. The relational model's declarative character was a major departure, and its success was driven by the development of efficient query processing techniques. Later, object-oriented and object-relational models attempted to integrate richer data types and inheritance into databases, but they did not displace the relational model. More recently, NoSQL systems have revived interest in non-relational data models, such as document stores and graph databases. Database theory has responded by studying query languages for these models, but the relational model remains the theoretical benchmark, and many results for non-relational models are adaptations or extensions of relational theory.
Contemporary database theory is a mature field with several active research fronts. One is the study of query evaluation on massive data, where the goal is to understand the complexity of query answering under the assumption that the data is too large to fit in memory. This has led to work on streaming algorithms, sampling techniques, and the theory of parallel query evaluation. Another front is the connection between databases and constraint satisfaction problems, where queries are viewed as constraint satisfaction problems and the goal is to classify the tractability of query evaluation based on the structure of the query. This line of work has produced deep results linking database theory to finite model theory and combinatorics.
The rise of data science and machine learning has also influenced the field. There is growing interest in the theory of data cleaning, which studies how to detect and repair inconsistencies in data, and in the theory of fairness in data management, which asks how to ensure that query answers do not discriminate against groups. These topics are newer and less settled than the classical core, but they reflect the field's ongoing expansion.
Throughout its history, database theory has maintained a distinctive character: it is a branch of computer science that prizes mathematical rigor, but it is also deeply connected to practice. Many of its results—Codd's theorem, the theory of functional dependencies, serializability—were motivated by concrete problems in building database systems, and they have had lasting practical impact. The field's methods are those of mathematical logic, computational complexity, and combinatorics, and its enduring questions are about the expressive power of query languages, the cost of query evaluation, and the correctness of data management under constraints.