Реляционная алгебра: операторы, лежащие под SQL

Когда вы пишете SELECT ... WHERE ... JOIN ..., СУБД не выполняет ваш SQL буквально слово за словом. Она сначала переводит запрос во внутреннее представление — дерево операторов реляционной алгебры, — затем оптимизатор переставляет эти операторы (например, фильтрует строки до соединения, а не после), и только потом исполняет. Реляционная алгебра — это «ассемблер» реляционных СУБД. Понимая её, вы перестаёте воспринимать SQL как набор магических заклинаний и начинаете видеть, что именно происходит.

Реляционная алгебра — это набор операторов, каждый из которых принимает один или два relations и возвращает новый relation. Из-за свойства замкнутости (прошлый урок: результат операции — снова relation) операторы можно вкладывать. Разберём шесть базовых. Математические символы в этом уроке показаны внутри блоков text, где парсер их не трогает.

select: фильтрация строк

Оператор select, обозначается греческой сигмой, выбирает из relation те tuples, которые удовлетворяют предикату (условию). Он работает «по горизонтали»: строки либо проходят, либо нет; набор атрибутов не меняется.

σ (selection) — фильтр строк по предикату

Запись:   σ[age > 25](users)
Смысл:    взять из users все строки, где age > 25

В SQL это WHERE:
  SELECT * FROM users WHERE age > 25;

Важно: реляционный оператор называется select, а ключевое слово SQL SELECT — это НЕ он. Путаница историческая и досадная. Реляционному select соответствует SQL-клауза WHERE. А слову SELECT в SQL соответствует следующий оператор — project.

project: выбор столбцов

Оператор project, обозначается греческой пи, выбирает из relation подмножество атрибутов (столбцов) и отбрасывает остальные. Он работает «по вертикали».

У project есть тонкость, которой нет у SELECT по умолчанию: поскольку результат project — это relation, а relation не содержит дубликатов, project автоматически удаляет дубликаты строк.

π (projection) — выбор столбцов, дубликаты удаляются

Запись:   π[city](users)
Смысл:    взять только столбец city, убрать повторы

Дано users:           π[city] даёт:
name | city           city
-----+--------        --------
Ann  | Moscow         Moscow
Bob  | Moscow         Berlin
Cy   | Berlin         (две строки, не три — дубль Moscow убран)

В SQL project — это список столбцов после SELECT. Но SELECT city FROM users вернёт Moscow дважды, потому что SQL по умолчанию работает с мультимножествами. Чтобы получить именно реляционный project, нужно написать SELECT DISTINCT city FROM users. Это одно из мест, где SQL сознательно отступает от теории ради производительности: убирать дубликаты дорого, и SQL не делает этого без явной просьбы.

join: соединение

Оператор join, обозначается «бабочкой», соединяет два relations по совпадению значений общих атрибутов. Это самый важный оператор реляционной модели: именно join позволяет хранить данные разнесёнными по таблицам без избыточности, а при запросе собирать их вместе.

⋈ (natural join) — соединить по совпадению общих атрибутов

users:                      orders:
user_id | name              user_id | amount
--------+------             --------+-------
   1    | Ann                  1    | 100
   2    | Bob                  1    | 250
                                3    | 70

users ⋈ orders   (соединяем по user_id):
user_id | name | amount
--------+------+-------
   1    | Ann  | 100
   1    | Ann  | 250

Строка Bob не попала (нет заказов), заказ user_id=3 не попал
(нет такого пользователя) — это поведение INNER JOIN.

В SQL это JOIN ... ON:

SELECT u.user_id, u.name, o.amount
FROM users u
JOIN orders o ON u.user_id = o.user_id;
-- user_id | name | amount
-- --------+------+-------
--    1    | Ann  |   100
--    1    | Ann  |   250

Концептуально join = декартово произведение (см. ниже) с последующим select по условию совпадения. Так его определяют в теории. Но если бы СУБД действительно строила полное произведение, а потом фильтровала, JOIN двух таблиц по миллиону строк создавал бы триллион промежуточных строк. Поэтому реальные СУБД исполняют join специальными алгоритмами — hash join, merge join, nested loop join — которые дают тот же результат, но без построения полного произведения. Выбор алгоритма — задача оптимизатора.

Теоретико-множественные операторы: union, intersection, difference

Три оператора пришли напрямую из теории множеств. Все они требуют, чтобы оба relations были union-compatible: имели одинаковое число атрибутов, и атрибуты на соответствующих позициях были над совместимыми domains. Нельзя объединить таблицу пользователей с таблицей заказов — у них разные heading.

∪ union          — все строки, которые есть в A ИЛИ в B
∩ intersection   — строки, которые есть И в A, И в B
− difference     — строки, которые есть в A, но НЕТ в B

A:        B:        A ∪ B:    A ∩ B:    A − B:
x         x         x         x         z
-         -         -         -         -
x=1       x=1       1         1         3
x=2       x=2       2         2
x=3       x=4       3
                    4

В SQL это UNION, INTERSECT, EXCEPT (в некоторых СУБД EXCEPT называется MINUS):

-- Пользователи из Москвы И из Берлина вместе, без дубликатов:
SELECT name FROM users WHERE city = 'Moscow'
UNION
SELECT name FROM users WHERE city = 'Berlin';

-- difference: пользователи, которые НЕ сделали ни одного заказа
SELECT user_id FROM users
EXCEPT
SELECT user_id FROM orders;

Тонкость: UNION в SQL удаляет дубликаты (как и положено множеству), а UNION ALL — нет. UNION ALL работает быстрее, потому что не делает дедупликацию; используйте его, когда точно знаете, что дубликатов не будет, или когда они нужны.

Декартово произведение

Оператор product, обозначается крестиком, соединяет каждую строку первого relation с каждой строкой второго. Если в A было m строк, а в B — n, то в произведении A и B будет m умножить на n строк.

× (Cartesian product) — каждая строка с каждой

A (2 строки):   B (3 строки):    A × B (2*3 = 6 строк):
a               b                a | b
-               -                --+--
1               x                1 | x
2               y                1 | y
                z                1 | z
                                 2 | x
                                 2 | y
                                 2 | z

В SQL декартово произведение получается, если написать FROM a, b без условия соединения, или CROSS JOIN:

SELECT * FROM colors CROSS JOIN sizes;
-- 3 цвета * 4 размера = 12 комбинаций

Декартово произведение почти никогда не нужно само по себе — это самый частый источник случайно «взорвавшихся» запросов. Если вы написали FROM a, b и забыли WHERE a.id = b.a_id, СУБД вернёт m умножить на n строк вместо ожидаемых. Поэтому современный стиль — всегда явный JOIN ... ON: забыть ON синтаксически сложнее, чем забыть WHERE.

Как алгебра превращается в SQL-запрос

Соберём всё вместе. Запрос «имена пользователей из Москвы, сделавших заказ дороже 100» на языке алгебры строится так:

π[name](
  σ[city='Moscow' AND amount > 100](
    users ⋈ orders
  )
)

Читается изнутри наружу:
1. users ⋈ orders        — соединить пользователей с заказами
2. σ[city.. AND amount..] — отфильтровать нужные строки
3. π[name]                — оставить только столбец name

Тот же запрос на SQL:

SELECT DISTINCT u.name
FROM users u
JOIN orders o ON u.user_id = o.user_id
WHERE u.city = 'Moscow' AND o.amount > 100;

Минимальный набор и производные операторы

Шесть операторов, которые мы разобрали, — это не случайный список. Среди них есть минимальный базис: select, project, product, union, difference и rename. Через эти шесть выражаются все остальные операторы реляционной алгебры. join, например, — производный: это product плюс select, как мы видели. Пересечение тоже производное: пересечение A и B равно разности A - (A - B) — двойная разность даёт пересечение.

Почему это важно понимать junior-инженеру? Потому что отсюда следует, что реляционная алгебра — компактная и замкнутая система: небольшое ядро операторов, и всё остальное — комбинации. SQL устроен так же: за богатым синтаксисом стоит небольшое число фундаментальных операций. Когда вы видите сложный запрос с подзапросами, JOIN, EXISTS, IN — это всё раскладывается в дерево из тех же базовых операторов. СУБД именно так его и обрабатывает.

Есть и операторы, которые в базис не входят, но полезны на практике. Деление (division) отвечает на запросы вида «найди всех, кто связан со ВСЕМИ элементами некоторого множества» — например, «студенты, записанные на все курсы без исключения». В SQL прямого оператора деления нет, и такие запросы выражают через NOT EXISTS с двойным отрицанием («нет курса, на который студент не записан»). Это известная сложная конструкция, и понимание, что за ней стоит операция деления, помогает её осмыслить.

Алгебра против исчисления: два взгляда на запрос

Стоит знать, что у реляционных запросов есть два эквивалентных формальных описания. Реляционная алгебра, которую мы разбирали, — процедурная: она описывает запрос как последовательность операций («сначала соедини, потом отфильтруй, потом спроецируй»). Есть и второй подход — реляционное исчисление (relational calculus), оно декларативное: описывает не «как получить», а «какими свойствами обладает результат» («все tuple t, такие что выполняется условие…»).

Codd доказал, что эти два подхода эквивалентны по выразительной силе: что можно описать алгеброй, то можно описать и исчислением, и наоборот. SQL вобрал черты обоих: внешне он декларативен (вы описываете желаемый результат, как в исчислении), а внутри СУБД переводит запрос в алгебраическое дерево операторов и оптимизирует его. Эта двойственность — «декларативно для человека, процедурно для машины» — и есть инженерная суть SQL.

Попробуй сам

Создайте в SQLite или PostgreSQL две таблицы — students(student_id, name, group_id) и enrollments(student_id, course_id, grade) — и наполните их 5-6 строками каждую так, чтобы у одного студента было несколько записей, а у одного — ни одной.

1. Напишите оператор select (через WHERE): студенты из группы 2.
2. Напишите оператор project (через SELECT DISTINCT): список уникальных course_id из enrollments.
3. Напишите оператор join (через JOIN): имя студента + его оценки. Убедитесь, что студент без записей в результат не попал.
4. Напишите оператор product (через CROSS JOIN или FROM a, b): посчитайте count(*) и проверьте, что оно равно произведению числа строк двух таблиц.
5. Напишите оператор difference (через EXCEPT): студенты, не записанные ни на один курс.

Для каждого запроса проговорите, какой оператор алгебры вы только что выразили. Это упражнение связывает теорию с реальным SQL намертво.