Database Theory §
Database theory studies how to store, query, and maintain collections of structured records (tuples) with guarantees of correctness and performance. It is relevant whenever an application must persist data, enforce constraints, and answer multi-table queries. It builds on key-value stores (B-tree indexes, hash indexes) and list structures (posting lists, sorted runs) but adds the dimension of relational algebra: predicates over multiple attributes, joins, and transactional consistency.
Utility §
- It gives a formal model (relational algebra) for expressing multi-table queries.
- It provides execution guarantees: ACID transactions, index-backed lookups, and cost-based query planning.
- It composes with distributed systems: sharding, replication, and consensus extend the single-node model.
Details
The five classes partition database theory by the fundamental question each answers: structure (what data exists), semantics (what operations mean), execution (how operations run efficiently), concurrency (how parallel access stays safe), and evolution (how the structure changes over time). Each builds on the previous: you must define a schema before you can write algebra over it, you must define algebra before you can compile it to a plan, you must have a plan before you can reason about concurrent execution, and you must have all of the above before you can safely evolve the schema.
History §
- 1970: Codd publishes the relational model, defining tables, keys, and relational algebra.
- 1974: System R (IBM) demonstrates a working relational DBMS with SQL and a cost-based optimizer.
- 1978: Oracle ships the first commercial relational database.
- 1995: MVCC and WAL-based recovery become standard in PostgreSQL and MySQL InnoDB.
Classes §
| Page | Aspect | Key question | Core guarantee |
|---|---|---|---|
| Schema | Structure | What tables, columns, and keys exist? | Referential integrity, normalization |
| Relational Algebra | Semantics | What does a query compute? | Set-theoretic correctness of joins, selections, projections |
| SQL & Query Planning | Execution | How is a query compiled and run cheaply? | Cost-optimal plan, index usage |
| Transactions | Concurrency | How do parallel operations stay consistent? | ACID, serializability, MVCC |
| Migrations | Evolution | How does the schema change over time? | Ordered, idempotent, reversible schema changes |
Authoritative sources