Relational Database Fundamentals: Relational Algebra, ACID Engines, and B+Tree Storage

Invented by Edgar F. Codd in 1970, the Relational Model revolutionized data storage by establishing a mathematical foundation based on first-order predicate logic and set theory. By strictly separating physical storage representations from logical declarative queries (Data Independence), relational database management systems (RDBMS) like PostgreSQL, MySQL, and Oracle have anchored global enterprise software architectures for over half a century.

This guide provides deep technical coverage of relational algebra operators, B+Tree disk page architectures, Write-Ahead Logging (WAL / ARIES), Multi-Version Concurrency Control (MVCC), and Cost-Based Query Optimization (CBO).

1. Quick-Reference: The Relational Engine Architecture

+-----------------------------------------------------------------------------------------------------------------------+
|                                           RDBMS COMPONENT ARCHITECTURE                                                |
+-----------------------------------------------------------------------------------------------------------------------+
| Layer                  | Core Responsibility                    | Key Invariant / Structure    | Performance Bottleneck|
+------------------------+----------------------------------------+------------------------------+----------------------+
| SQL Parser & Rewriter  | Lexing, AST construction, view expansion| Valid Abstract Syntax Tree   | Query complexity     |
| Cost-Based Optimizer   | Join ordering, index scan selection    | Dynamic Programming / Selinger| Statistics drift     |
| Execution Engine       | Volcano iterator model (next() calls)  | Pipelined tuple streams      | CPU cache locality   |
| Buffer Pool Manager    | Frame allocation, disk page caching    | LRU-K / Clock sweep eviction | Buffer cache miss    |
| Storage Engine         | B+Tree indexing, row/column serialization| 8KB Slotted disk pages       | Random disk I/O      |
| Transaction & Log Mgr  | WAL emission, crash recovery, MVCC     | ARIES / Append-only log      | Fsync latency (IOPs) |
+-----------------------------------------------------------------------------------------------------------------------+

2. Mathematical Foundations: Relational Algebra

Relational queries are declarative expressions translated by database parsers into procedural Relational Algebra Expressions:

+-----------------------------------------------------------------------------------------------------------------------+
|                                           RELATIONAL ALGEBRA OPERATORS                                                |
+-----------------------------------------------------------------------------------------------------------------------+
| Operator               | Notation       | Description                        | SQL Equivalent                         |
+------------------------+----------------+------------------------------------+----------------------------------------+
| Selection              | $\sigma_{\phi}(R)$| Filters tuples matching predicate $\phi$| `WHERE condition`                     |
| Projection             | $\pi_{a_1,\dots,a_n}(R)$| Subsets attributes $a_1, \dots, a_n$| `SELECT col1, col2`                    |
| Cartesian Product      | $R 	imes S$   | Cross pairing of all tuples        | `CROSS JOIN`                           |
| Natural Join           | $R owtie S$  | Equi-join on matching attribute names| `INNER JOIN ON R.id = S.id`            |
| Union / Difference     | $R \cup S, R - S$| Set union and set subtraction     | `UNION`, `EXCEPT`                      |
+-----------------------------------------------------------------------------------------------------------------------+

3. Storage Internals: Slotted Disk Pages & B+Trees

Relational storage engines organize tables into fixed-size Pages (typically $8 ext{ KB}$ in PostgreSQL, $16 ext{ KB}$ in MySQL InnoDB) that map directly to OS block device transfers.

+-----------------------------------------------------------------------------------------+
|                               SLOTTED DISK PAGE LAYOUT (8 KB)                           |
+-----------------------------------------------------------------------------------------+
| [ Page Header: LSN, Free Space Pointers, Flags ]                                        |
| [ Line Pointer 1 ] [ Line Pointer 2 ] [ Line Pointer 3 ] ----> (Grows Downward)         |
| ....................................................................................... |
|                                 FREE SPACE WINDOW                                       |
| ....................................................................................... |
| <---- (Grows Upward) [ Tuple 3 Data ] [ Tuple 2 Data ] [ Tuple 1 Data ]                 |
+-----------------------------------------------------------------------------------------+

B+Tree Index Invariants

Unlike standard Binary Search Trees, B+Trees are self-balancing multi-way search trees with high fanout ( $B pprox 100 - 500$ ), minimizing disk seek depth:

Shallow Depth: A 3-level B+Tree with fanout $F = 200$ indexes up to $200^3 = 8,000,000$ leaf pages ( $64 ext{ GB}$ of data) in at most 3 page lookups.
Doubly-Linked Leaves: All leaf nodes are linked sequentially ( $L_i \leftrightarrow L_{i+1}$ ), enabling $O(\log N + K)$ index range scans (WHERE age BETWEEN 20 AND 30) without tree backtracking.

4. ACID Mechanics: WAL and MVCC

                  +-----------------------------------+
                  | Client Executes UPDATE ...        |
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  | 1. Write Log Record to WAL Buffer |
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  | 2. Synchronous fsync() to Disk    |  <-- Invariant: WAL before Data!
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  | 3. Mutate Dirty Page in Buffer Pool|
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  | 4. Return Success (Commit ACK)    |
                  +-----------------------------------+

Write-Ahead Logging (WAL): Ensures Durability and Atomicity via the ARIES protocol. No dirty data page is written to disk until the corresponding log record has been safely flushed via fsync().
Multi-Version Concurrency Control (MVCC): Readers do not block writers, and writers do not block readers. When a row is modified, the engine writes a new tuple version stamped with xmin (creating transaction ID) and sets xmax on the old version. A query reading at snapshot $T_{ ext{snapshot}}$ only sees versions where $ext{xmin} \le T_{ ext{snapshot}} < ext{xmax}$ .

References

Codd, E. F. (1970). A Relational Model of Data for Large Shared Data Banks. Communications of the ACM.
Mohan, C., et al. (1992). ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks. ACM TODS.
Hellerstein, J. M., Stonebraker, M., & Hamilton, J. (2007). Architecture of a Database System. Foundations and Trends in Databases.