Relational Algebra

When working with the relational model, we have 2 groups of operations we can use.

The first is called relational algebra, and it’s a procedural language.

This is what SQL is based upon, and as such it is very important to learn - as SQL is the de-facto standard for working with relational databases.

The second is called relational calculus and instead of being procedural, it’s a declarative language. It’s a fundamental difference in how we interact with databases, because you don’t tell the database software what to do, you just tell it what you want, and let it sort out the details of how to do it.

This is a common distinction among programming languages. In modern frontend, we say interaction with the DOM in React is declarative. Using vanilla JavaScript to modify the DOM is procedural.

Languages like Datalog, QBE and QUEL have relational calculus as its base. I’m not going to talk about this because I think it’s a much more niche way of doing things compared to the more practical approach followed by SQL, but you can look at it if you want.

Given this introduction, let’s go on with relational algebra.

We have 2 types of operations:

• primary operations
• join operations

Primary operations in relational algebra

Primary operations are:

• union
• difference
• cartesian product
• select
• project
• rename

Here is how each one maps to everyday SQL:

Let’s walk through them with a small table.

Orders:

Select

Select keeps rows that match a condition. Columns stay the same.

Select orders where city = Rome:

In SQL that is a WHERE clause:

SELECT *
FROM orders
WHERE city = 'Rome';

Project

Project keeps only some columns. In relational algebra the result is a set, so rows that become identical appear once.

Project city from orders:

In SQL you name the columns in the SELECT list. SQL keeps duplicate rows, so you need DISTINCT to get the same result as the algebra:

SELECT DISTINCT city
FROM orders;

Union and difference

Union stacks two tables that share the same columns and types. Duplicate rows appear once.

Today’s sales and yesterday’s sales, same shape, become one list of all sales.

SELECT city, total FROM sales_today
UNION
SELECT city, total FROM sales_yesterday;

Difference keeps rows from the first table that are not in the second. Same column rule as union.

SELECT city FROM customers
EXCEPT
SELECT city FROM blocked_cities;

Cartesian product vs join

Cartesian product pairs every row of table A with every row of table B. No matching rule. Three cities and two products become six rows.

That is rarely what you want as a final answer. It is the raw “all combinations” step.

A join starts from that idea, then keeps only the combinations that match a condition (same employee id, same order id, and so on). So: product = all pairs; join = filtered pairs.

Rename

Rename changes an attribute name. You need it when two tables both have a column called id, or when a join would produce two columns with the same name.

Say orders also has a customer_id column that points at a customers table:

SELECT o.id AS order_id, c.id AS customer_id
FROM orders AS o
JOIN customers AS c ON o.customer_id = c.id;

Without the rename, both columns would be called id, and the result would be hard to read and hard to join further.

Join operations in relational algebra

Joins are probably the most powerful operations you can perform with relational algebra. They build on top of primary operations, and they allow you to correlate data contained in different relations (tables).

Note: this post stays on the theory. For joins in practice, see SQL joins.

We have 2 main join versions: natural join and theta join. All the other versions are extracted from those 2.

Natural Join

Natural join correlates two relations (tables), and creates a new table based on the same values of an attribute.

We need two relations with the same attribute name (column), first. Then if values in the attributes in relation A are unmatched in the attributes in relation B, the row is not part of the result, it’s ignored.

Example:

Relation A

Relation B

We can perform a natural join to get the boss name for each employee:

Since the relations have the Employee ID attribute name in common, it is only present once in the result, not 2 times.

The employee #3 present in relation A, Rick, is not included in this table, because there’s no corresponding entry in relation B.

Theta-join

A theta-join allows to perform a join based on any criteria to compare two columns in two different relations, not just equality like the natural join does.

It performs a cartesian product of two tables, and filters the results based on the selection we want to make. That filter is what turns raw combinations into a join.

Equi-join

The equi-join is a theta join, where the selection is based on equality between attribute values in the two different tables.

The difference with the natural join is that we can choose which attributes names (columns) we want to compare.

When you want to use joins in SQL, I have a separate SQL joins post.

Want me to talk about your product? You can sponsor this site.