Реляционная алгебра и таблицы

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Реляционная база на математическом языке — это не «файл с ячейками», а отношение: множество кортежей (строк), каждый кортеж — упорядоченный набор значений из доменов (столбцов). Столбец i соответствует i-му домену Dᵢ; допустимые строки лежат в D₁ × D₂ × … × Dₙ.

Предпосылки: множества и кортежи, при необходимости логика. Дальше по Кодду и SQL: теория реляционных данных, реляционная модель.

// Строка таблицы orders как кортеж (id, user_id, amount)
строка := (1042, 7, 1500.00)

// Множество всех допустимых строк таблицы — отношение Orders
Orders ⊆ Id × UserId × Amount

---

Алгебра отношений

Рассматривают множество отношений R = {P₁, P₂, …} и операции над совместимыми отношениями: оба лежат в одном и том же Aⁿ (одинаковая «арность» кортежа).

Операция	Обозначение	Результат
Объединение	P ∪ Q	кортежи из P или из Q
Пересечение	P ∩ Q	кортежи одновременно в P и Q
Разность	P \ Q	кортежи из P, которых нет в Q
Декартово произведение	P × Q	конкатенация кортежа X ∈ P и Y ∈ Q

P := {(a, b, d), (b, c, e)}
Q := {(a, b, d), (b, d, e)}

P ∪ Q  // {(a,b,d), (b,c,e), (b,d,e)}
P ∩ Q  // {(a,b,d)}
P \ Q  // {(b,c,e)}

Декартово произведение «склеивает» кортежи: если X = (x₁,…,xᵣ) и Y = (y₁,…,yₛ), то X̂Y = (x₁,…,xᵣ,y₁,…,yₛ). Отсюда взрыв числа строк при JOIN без условия — в алгебре Кодда его сужают выборкой σ и соединением ⋈.

---

Таблица на практике

Понятие теории	В СУБД	Пример
отношение Rₙ	таблица	exams(schedule_id, subject, room, date)
кортеж	строка	(1, "Math", "A-101", "2026-06-01")
домен Dᵢ	тип столбца + ограничения	date, varchar, NOT NULL
R ⊆ D₁×…×Dₙ	допустимые строки по схеме	CHECK, FK, UNIQUE

Четырехместное отношение «расписание экзаменов» в формальной постановке — тот же объект, что таблица в PostgreSQL: столбцы задают домены, каждая запись — один кортеж, принадлежащий отношению.

---

Две алгебры — один SQL

Уровень	Операции (идея)	Аналог в SQL
Алгебра отношений (множества кортежей)	∪, ∩, , ×	UNION, INTERSECT, EXCEPT, декартово FROM a, b
Алгебра Кодда	σ (выборка), π (проекция), ⋈ (соединение), переименование	WHERE, список столбцов, JOIN, alias

Оптимизатор SQL переписывает запрос в дерево операций реляционной алгебры Кодда, но семантика «таблица = множество строк-кортежей» остаётся той же, что в дискретной математике.

Маршрут чтения

1. Множества и отношения — формальный слой
2. эта статья
3. Реляционная модель → теория под капотом СУБД

Назад: дискретная математика (обзор). Дальше: теория чисел и алгоритмы или раздел SQL.

---