Relational Algebra
Scenario
You write a SQL query: 'SELECT name FROM users WHERE age > 18'. Before the database executes it, it translates your English-like SQL into a mathematical pipeline.
What is the underlying math language that powers every relational database engine on earth?
Mental model
A physical assembly line for data. Each station (operator) takes in a conveyer belt of rows, transforms them, and passes them to the next station.
Relational algebra is a procedural query language. It takes instances of relations as input and yields instances of relations as output. Because the output is always the same shape as the input (a table), you can chain operations together indefinitely.
Explanation
SQL is a declarative language — you tell the database WHAT you want, not HOW to get it. But computers need a 'how'. Relational algebra is that 'how'. It is the mathematical foundation of the relational model, consisting of a set of fundamental operations that can be chained together to extract any data. Every SQL query you write is compiled down into a relational algebra expression before the execution engine runs it.
The most basic operations are Selection and Projection. They slice the data in different directions. Selection (represented by the Greek letter Sigma, σ) is a horizontal slice: it filters rows based on a condition, exactly like the WHERE clause in SQL. Projection (represented by Pi, π) is a vertical slice: it extracts specific columns and discards the rest, exactly like the SELECT clause in SQL. Because relational algebra operates on sets, Projection automatically removes duplicate rows.
To combine data from multiple tables, we use the Cartesian Product (Cross Product, ×). It combines every row from Table A with every row from Table B. If A has 100 rows and B has 100 rows, the cross product creates 10,000 rows. This is mathematically pure but computationally disastrous. In the real world, we almost never want a raw cross product.
Instead, we use the Join operation (⨝), which is just a Cross Product immediately followed by a Selection condition. An Inner Join takes the massive cross product and instantly filters it down to only the rows where the keys match (e.g., A.id = B.user_id). This combined operation is so common that it gets its own fundamental operator in the algebra.
The most important characteristic of relational algebra is the 'closure property'. An operation takes one or two tables as input, and always produces a new table as output. This means you can infinitely nest operations: the output of a Join can be fed into a Selection, which can be fed into a Projection. This composability is what allows databases to optimize queries by rearranging the algebraic tree before executing it.
Key points
- Selection (σ): Filters rows horizontally based on a predicate condition (equivalent to SQL WHERE).
- Projection (π): Extracts columns vertically and drops duplicates (equivalent to SQL SELECT).
- Cartesian Product (×): Combines every row of relation A with every row of relation B.
- Join (⨝): A Cartesian Product followed by a Selection condition on matching attributes.
Common mistakes
- Confusing Selection and Projection: It's easy to mix them up because SQL uses the word 'SELECT' for columns. In math, Selection (Sigma) filters ROWS, and Projection (Pi) picks COLUMNS.
- Thinking relational algebra is just theoretical: It is the literal engine under the hood. Query optimizers work by converting SQL to an algebraic tree, and then applying mathematical rules to rewrite the tree into a faster, equivalent form.
Glossary
- Relational Algebra
- The formal mathematical foundation behind how databases work, consisting of operations used to manipulate and filter data tables.
- Selection
- A database operation that acts like a filter, picking out only specific rows from a table that meet a certain condition.
- Projection
- A database operation that acts like a vertical slice, picking out only specific columns from a table and ignoring the rest.
Recall questions
- Which relational algebra operator corresponds to the SQL WHERE clause?
- Which relational algebra operator corresponds to the SQL SELECT clause?
- A Join is fundamentally a combination of which two basic operators?
Questions & answers
What is the closure property in relational algebra?
The property that the output of any relational algebra operation is always a relation (table), allowing operations to be nested.
Approach: Mention that this is what enables query chaining and optimization trees.
Differentiate between Selection and Projection.
Selection filters tuples (rows) based on a condition. Projection extracts specific attributes (columns) and eliminates duplicates.
Approach: Use the horizontal/vertical slice analogy. Mention the Greek letters (σ vs π) for bonus points.
Continue learning
Previous: DBMS vs File System