Relational algebra

Introduction

Relational algebra is the mathematics that SQL is built on. Each operation takes one or two relations (tables) and gives back a new relation, so operations can be chained, just like + and × in ordinary algebra. A DBMS turns your SQL into a relational algebra expression, then looks for the fastest way to work it out.

Careful with names: relational algebra's select (σ) picks rows, like SQL's WHERE, not like SQL's SELECT.

∪, − and ∩ need union-compatible relations: the same number of columns, with matching types.

Relational algebra is the theory under SQL. It explains why queries can be rewritten and optimised, and it is a standard part of database exams.

How it works

The worked example below runs one SQL query for each common operation. Here is one more operation that SQL has no keyword for.

Division, briefly

R ÷ S answers "for all" questions: the students who took every course in S. SQL has no division operator; you write it with NOT EXISTS twice, or by counting: a student who took as many of S's courses as S has took them all.

Syntax

π name ( σ dept = 'CSE' ∧ marks > 80 ( Student ) )

SELECT DISTINCT name FROM Student WHERE dept = 'CSE' AND marks > 80;

Example

"The names of the CSE students who scored over 80":

π name ( σ dept = 'CSE' ∧ marks > 80 ( Student ) )

Read it from the inside out: start with Student, select the rows, then project the column. In SQL:

SELECT DISTINCT name FROM Student WHERE dept = 'CSE' AND marks > 80;

CREATE TABLE Student (
  id INTEGER PRIMARY KEY,
  name TEXT,
  dept TEXT,
  marks INTEGER
);
CREATE TABLE ClubMember (
  name TEXT
);
INSERT INTO Student (name, dept, marks) VALUES
  ('Rahim', 'CSE', 85), ('Karim', 'EEE', 72), ('Nadia', 'CSE', 91),
  ('Tania', 'BBA', 64), ('Sumon', 'CSE', 58), ('Rina', 'EEE', 79);
INSERT INTO ClubMember VALUES ('Nadia'), ('Karim'), ('Imran');

-- σ dept = 'CSE' (Student)
SELECT * FROM Student WHERE dept = 'CSE';

-- π dept (Student): no repeated rows
SELECT DISTINCT dept FROM Student;

-- π name (σ dept = 'CSE' ∧ marks > 80 (Student))
SELECT DISTINCT name FROM Student WHERE dept = 'CSE' AND marks > 80;

-- π name (Student) ∩ ClubMember: students in the club
SELECT name FROM Student INTERSECT SELECT name FROM ClubMember;

-- π name (Student) − ClubMember: students not in the club
SELECT name FROM Student EXCEPT SELECT name FROM ClubMember;

-- π name (Student) ∪ ClubMember: everyone, once each
SELECT name FROM Student UNION SELECT name FROM ClubMember;

Each query in the example is one operation. Notice that π dept(Student) gives 3 rows, not 6: a relation is a set, so it has no repeated rows, and plain SQL SELECT dept would keep them. That is why π is SELECT DISTINCT.

Line by line

1. Student holds six students, and ClubMember holds three names, one of whom, Imran, is not a student.
2. The first query is σ: it keeps the CSE rows and all their columns.
3. SELECT DISTINCT dept is π: three departments, with no repeats.
4. The third query chains σ and π, which gives Rahim and Nadia.
5. INTERSECT gives the students who are in the club: Karim and Nadia.
6. EXCEPT gives the students who are not in the club, and UNION gives everyone in either table, each name once.

Expected result

id  name   dept  marks
--  -----  ----  -----
1   Rahim  CSE   85
3   Nadia  CSE   91
5   Sumon  CSE   58
(3 rows)

dept
----
CSE
EEE
BBA
(3 rows)

name
-----
Rahim
Nadia
(2 rows)

name
-----
Karim
Nadia
(2 rows)

name
-----
Rahim
Rina
Sumon
Tania
(4 rows)

name
-----
Imran
Karim
Nadia
Rahim
Rina
Sumon
Tania
(7 rows)

In the real world

Every SQL query is turned into a tree of these operations inside the DBMS. The query optimiser rewrites that tree, for example by doing a selection before a join, to make the query faster without changing its answer.

Common mistakes

• Confusing σ (select), which picks rows, with SQL's SELECT, which picks columns.
• Forgetting that π removes repeated rows, so plain SELECT is not quite π.
• Using union or difference on relations with different columns.

Best practices

• Read an algebra expression from the inside out.
• Write the algebra first for a hard query, then translate it into SQL.
• Check union compatibility before combining two results.

Summary

Relational algebra describes queries as operations on relations: selection, projection, product, join, union, difference, intersection, rename and division. SQL is built on it, with WHERE for σ and SELECT DISTINCT for π.

Mark lesson complete