Relational Database Foundations, DBMS Architecture & Relational Algebra

⚡ The Data Engine of Civilization: Every bank transaction, airline reservation, medical record, and e-commerce checkout relies on a Database Management System (DBMS). Before relational databases, applications wrote unstructured data directly to disk files—resulting in data corruption, race conditions, and catastrophic failures. To engineer resilient systems, we must understand the mathematical foundation upon which all modern databases are built.

1. Why Flat Files Fail at Scale

In the earliest days of software, applications stored data in simple flat files (such as raw text files, comma-separated CSVs, or proprietary binary blobs).

While adequate for simple single-user scripts, flat files collapse under multi-user concurrency and enterprise scale:

2. What is a DBMS? The 4 Core Responsibilities

A Database Management System (DBMS) is specialized systems software designed to manage, store, retrieve, and safeguard structured data on behalf of multiple concurrent applications.

APPLICATION TIER              DATABASE MANAGEMENT SYSTEM (DBMS)
┌───────────────────┐        ┌──────────────────────────────────────────────────┐
│ Web / API Servers │◄──────►│ 1. Storage Engine (8KB Disk Pages, B+ Tree Index)│
├───────────────────┤        │ 2. Query Engine   (SQL Parser, Optimizer, Plan) │
│ Background Jobs   │◄──────►│ 3. Concurrency    (Lock Manager, MVCC Engine)    │
├───────────────────┤        │ 4. Reliability    (Write-Ahead Log, Crash ARIES) │
│ Analytics / BI    │◄──────►└─────────────────────────┬────────────────────────┘
└───────────────────┘                                  │
                                           PHYSICAL NON-VOLATILE STORAGE (NVMe / SSD)

The ACID Transaction Guarantees:

Every enterprise relational database (such as PostgreSQL, MySQL, SQLite, Oracle) adheres to the ACID contract:

• Atomicity (All-or-Nothing): A transaction is an indivisible unit of work. If a transfer deducts money from Account A but crashes before crediting Account B, the entire transaction is rolled back.
• Consistency (State Invariants): The database transitions from one valid state to another, strictly enforcing all schema rules, foreign keys, and check constraints.
• Isolation (Independent Concurrency): Concurrent transactions execute as if they were running serially in isolation without stepping on each other’s uncommitted data.
• Durability (Survival on Disk): Once a transaction commits, its modifications are permanently recorded to disk (via Write-Ahead Logging) and will survive power failures or operating system crashes.

3. Edgar F. Codd & The Relational Model (1970)

In 1970, computer scientist Edgar F. “Ted” Codd published his revolutionary paper: A Relational Model of Data for Large Shared Data Banks at IBM Research.

Codd proposed separating logical data representation (how users perceive and query data) from physical storage representation (how bits are physically laid out on spinning disks).

RELATIONAL TERMINOLOGY MAPPING:

Formal Mathematical Term         SQL & Industry Equivalent
────────────────────────────────────────────────────────────
Relation                         Table
Tuple                            Row / Record
Attribute                        Column / Field
Domain                           Data Type (e.g. INT, VARCHAR)
Cardinality                      Total Number of Rows (N)
Degree / Arity                   Total Number of Columns (K)

Relation: USERS (Degree = 3, Cardinality = 3)
┌──────────┬─────────────────┬──────────────────────┐
│ user_id  │ name            │ email                │  ◄── Attributes (Columns)
├──────────┼─────────────────┼──────────────────────┤
│ 1        │ Linus Torvalds  │ linus@kernel.org     │  ◄── Tuple (Row 1)
│ 2        │ Ada Lovelace    │ ada@analytical.engine│  ◄── Tuple (Row 2)
│ 3        │ Ken Thompson    │ ken@bell-labs.com    │  ◄── Tuple (Row 3)
└──────────┴─────────────────┴──────────────────────┘

4. Relational Algebra: The Mathematical Engine of SQL

SQL is not an arbitrary string syntax; it is a declarative representation of Relational Algebra—a formal mathematical system where operations take one or more relations as input and produce a new relation as output.

1. Selection ($\sigma$): Filtering Tuples (Rows)

Filters rows that satisfy a specific boolean predicate.

• Mathematical Notation: σ_predicate(R)
• SQL Equivalent: WHERE predicate

σ_{user_id = 2}(USERS) ➔ Produces a relation containing only the tuple for Ada Lovelace.

2. Projection ($\pi$): Filtering Attributes (Columns)

Extracts specific columns while discarding unrequested attributes and eliminating duplicate rows.

• Mathematical Notation: π_{attribute1, attribute2}(R)
• SQL Equivalent: SELECT attribute1, attribute2

π_{name, email}(USERS) ➔ Produces a relation containing only the name and email columns.

3. Cartesian Product ($\times$): Cross Combination

Combines every single tuple of relation $R$ with every tuple of relation $S$.

• Mathematical Notation: R × S
• SQL Equivalent: FROM R CROSS JOIN S
• Result Size: If $R$ has $N$ rows and $S$ has $M$ rows, the product contains N * M rows.

4. Natural Join ($\bowtie$): Conditional Merging

Combines tuples from two relations where common attribute values match.

• Mathematical Notation: R ⋈_{R.id = S.user_id} S
• SQL Equivalent: FROM R INNER JOIN S ON R.id = S.user_id

Relation: USERS                        Relation: ORDERS
┌────┬───────────────┐                 ┌──────────┬─────────┬────────┐
│ id │ name          │                 │ order_id │ user_id │ amount │
├────┼───────────────┤                 ├──────────┼─────────┼────────┤
│ 1  │ Linus         │                 │ 101      │ 1       │ 45.00  │
│ 2  │ Ada           │                 │ 102      │ 1       │ 89.00  │
└────┴───────────────┘                 └──────────┴─────────┴────────┘

Result of USERS ⋈_{USERS.id = ORDERS.user_id} ORDERS:
┌────┬───────────────┬──────────┬────────┐
│ id │ name          │ order_id │ amount │
├────┼───────────────┼──────────┼────────┤
│ 1  │ Linus         │ 101      │ 45.00  │
│ 1  │ Linus         │ 102      │ 89.00  │
└────┴───────────────┴──────────┴────────┘

5. Set Operators: Union ($\cup$), Intersection ($\cap$), Difference ($-$)

• Union (R ∪ S): All tuples appearing in either $R$ or $S$ (UNION).
• Intersection (R ∩ S): Tuples appearing in both $R$ and $S$ (INTERSECT).
• Set Difference (R - S): Tuples in $R$ that do not appear in $S$ (EXCEPT / MINUS).

5. From Relational Algebra to SQL Query Execution

When you send a SQL statement to a database, the engine converts your declarative query into a Relational Algebra Expression Tree, optimizes the mathematical operations, and executes the lowest-cost execution plan:

SQL Query:
SELECT name, email FROM users WHERE user_id > 100;

Relational Algebra Formulation:
π_{name, email}( σ_{user_id > 100}(USERS) )

QUERY EXECUTION PIPELINE:
┌─────────────────┐       ┌────────────────────────┐       ┌──────────────────────┐
│  SQL Text Parse │ ➔ ➔ ➔ │ Algebraic Tree Planner │ ➔ ➔ ➔ │ Physical Index Scan  │
│  (Lexing & AST) │       │ (Push Down Predicates) │       │ (B+ Tree Leaf Fetch) │
└─────────────────┘       └────────────────────────┘       └──────────────────────┘

6. Key Takeaways & Summary