Database Theory

Database Theory

Databases are one of the most theoretically grounded areas of computing. Codd's relational model (1970) was a mathematical breakthrough that replaced ad-hoc data access with a rigorous algebraic foundation. Understanding that theory makes you a far better database designer and a far more effective developer.

The Relational Model

A relation is a set of tuples (rows) over a schema (column names and types). Unlike files, relations are sets — no ordering, no duplicates, pure mathematical structure. This clean foundation enables algebraic manipulation.

Relational algebra defines operations on relations:

• Selection σ condition(R): filters rows where condition is true
• Projection π attributes(R): keeps only specified columns
• Join R ⋈ condition S: combines rows from two relations where the condition holds
• Union R ∪ S: all rows from both (schemas must match)
• Difference R − S: rows in R but not S
• Rename ρ new(R): rename a relation or attribute

SQL is a declarative surface over relational algebra. SELECT implements projection, WHERE implements selection, JOIN implements join. The query optimizer translates SQL to a relational algebra expression tree, then finds the most efficient execution plan.

Normalization

Unnormalized schemas cause update anomalies: inserting, deleting, or updating data requires changes in multiple places, risking inconsistency. Normal forms eliminate these by removing redundancy.

1NF: all attribute values are atomic (no repeating groups or nested relations). A "tags" column with comma-separated values violates 1NF.

2NF: no partial dependencies — every non-key attribute depends on the entire primary key. Violated in a table with composite key (OrderID, ProductID) where a column like SupplierAddress depends only on ProductID.

3NF: no transitive dependencies — non-key attribute A depends on non-key attribute B which depends on the key. Fix: move B and A to a separate table.

BCNF (Boyce-Codd NF): every functional dependency X → Y has X as a superkey. Stricter than 3NF; sometimes decomposition into BCNF loses join dependencies.

The goal is lossless-join decomposition — splitting a table into two tables that can be rejoined to recover the original data exactly. Not all decompositions are lossless.

Transactions and ACID

A transaction is a sequence of operations treated as a single unit. ACID properties guarantee reliability:

Atomicity: the transaction either completes fully or has no effect. Achieved through undo logs — if a transaction aborts, the log is replayed in reverse to restore the previous state.

Isolation: concurrent transactions behave as if executed serially. Serializable isolation is the gold standard but expensive. Weaker levels (Read Uncommitted, Read Committed, Repeatable Read) trade correctness anomalies for performance.

Dirty Read: reading uncommitted changes from another transaction (prevented above Read Uncommitted).

Non-repeatable Read: re-reading a row returns different data because another transaction committed a change (prevented above Read Committed).

Phantom Read: a range query returns different rows on re-execution because another transaction inserted rows (prevented only at Serializable).

Durability: committed transactions survive crashes. Achieved through Write-Ahead Logging (WAL): changes are written to a sequential log before being applied to data pages. On crash, the log is replayed from the last checkpoint.

Indexing

An index is a separate data structure that speeds queries at the cost of storage and write overhead. The dominant index structure is the B-Tree.

A B-Tree with branching factor B stores up to B-1 keys per node. With n records, the tree height is log_B(n). For B=1000 and n=1 billion, height = 3. Three disk reads to find any record in 1 billion. This is why indexes are transformative: without one, a full table scan reads all rows (O(n)); with an index, O(log n).

Hash indexes support only equality lookups (perfect for primary key lookups) but cannot handle range queries. B-Trees support both equality and range queries.

Covering indexes include all columns needed for a query, eliminating the need to access the main table at all — queries are answered entirely from the index.

Query Optimization

The query optimizer is the database's most sophisticated component. It translates SQL into a logical plan (relational algebra expression), then generates physical plans (specific algorithms), estimates their cost using statistics (row counts, cardinality, histograms), and chooses the cheapest.

Join algorithms:

• Nested Loop Join: for each row in R, scan S for matches. O(|R|·|S|). Good for small tables or when one table fits in memory.
• Hash Join: build a hash table from the smaller relation, probe it with each row of the larger. O(|R| + |S|). Good for large tables without relevant indexes.
• Merge Join: sort both relations on the join key, merge. O(|R| log |R| + |S| log |S|). Excellent when data is already sorted.

Join order matters exponentially. For n tables, there are n!/2 possible join orders. The optimizer uses dynamic programming to find the optimal order for small n, and heuristics for large n.

EXPLAIN (or EXPLAIN ANALYZE) reveals the chosen plan, estimated vs actual row counts, and time per node. Mismatched estimates (wrong statistics) are the most common cause of bad query plans — running ANALYZE updates statistics.