Databases

Relations, Transactions, and the Storage Engine

Databases manage persistent structured data at scale under concurrency and failures.

The irreducible elements are relations (sets of tuples), transactions (atomic units of work), indexes, the buffer pool, and the log. The storage engine, query optimizer, and concurrency control mechanisms are the higher-order structures that turn raw storage into a reliable, high-performance data management system.

This note connects deeply to algorithms & data structures (query processing and indexing algorithms), operating systems (buffer management, I/O scheduling), and the general theory of systems (ACID as a set of invariants maintained by feedback loops).

Normal Forms, Serializability, and Recovery Theory

Functional dependencies and Armstrong’s axioms give us a deductive framework for schema design. Conflict serializability and the ARIES recovery model provide the mathematical guarantees that allow correct concurrent execution and recovery after crashes.

These principles underpin every production DBMS.

What We Measure in a Real DBMS

Selectivity and cardinality estimates, actual vs. estimated query cost, throughput under concurrent load, abort rates, and recovery time are the observables. Index choice, join order, isolation level, and buffer pool size have direct causal effects on performance and correctness.

The Core Database Procedures

Query optimization (dynamic programming join ordering), ARIES-style recovery, B-tree maintenance, and two-phase locking are the production-grade algorithms that every serious database depends on.

Each has a clear specification, correctness argument, and well-understood performance characteristics.

(See the detailed step lists in the YAML.)

Durable State under Concurrent Mutation and Failure

A database is a classic stock-and-flow system. Relations are the primary stocks. Queries and updates are flows. The write-ahead log and buffer pool create the feedback mechanisms that guarantee durability and atomicity even when the underlying hardware fails or multiple transactions run concurrently.

The ACID properties emerge from the careful design of these loops.

The Brutal Engineering Reality

Building a production DBMS that is correct, fast, scalable, and evolvable is one of the hardest problems in systems engineering. The constraints of real storage devices, the need for online operation, the complexity of query optimization, and the requirement to support decades of legacy workloads dominate every major design decision.

The substrate declared here makes the essential objects, flows, and trade-offs explicit for the knowledge graph, gap analysis, and construction workbench.