Реляционная алгебра и таблицы
Play ITЗагрузка интерактивного демо…
Реляционная база на математическом языке — это отношение: множество кортежей (строк), каждый кортеж — упорядоченный набор значений из доменов (столбцов). Столбец 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 переписывает запрос в дерево операций реляционной алгебры Кодда, но семантика "таблица = множество строк-кортежей" остаётся той же, что в дискретной математике.
Назад: дискретная математика (обзор). Дальше: теория чисел и алгоритмы или раздел SQL.