Реляционная алгебра: выборка и проекция

Откуда берется реляционная алгебра?

В 1970 году Эдгар Франк Кодд создал математический аппарат для манипулирования отношениями.

Исторический контекст

До реляционной модели (1960-е)

Программист писал процедурный код с указателями и адресами диска, обходя физические записи по цепочкам связей (навигационная модель). Изменение структуры файла ломало все программы.

Прорыв Э. Кодда

Декларативность и математика

Кодд предложил абстрагироваться от дисков: данные представляются в виде математических отношений (множеств), а манипулирование ими описывается замкнутой алгеброй операций.

Свойство реляционной замкнутости (Relational Closure)

Ключевой математический закон: результат ЛЮБОЙ операции есть снова ОТНОШЕНИЕ.

Следствие 1

Вложенность и композиция

Выход одной операции можно мгновенно подать на вход другой: π(σ(R)). В SQL это легло в основу подзапросов (Subqueries) и общих табличных выражений (CTE).

Следствие 2

Чистые функции

Операции не разрушают и не перезаписывают исходные таблицы в памяти или на диске. Они вычисляют совершенно новое порожденное отношение.

Следствие 3

Оптимизация запросов

Благодаря законам алгебры оптимизатор СУБД переставляет операторы местами, ускоряя запрос в тысячи раз без изменения смысла данных.

Геометрическая модель: два среза таблицы

Унарные операции выборки и проекции работают в перпендикулярных плоскостях.

Горизонтальный срез

Селекция / Выборка (σ)

Фильтрует строки (кортежи) по предикату условия. Заголовок таблицы (набор атрибутов) остается неизменным.

σ[Стаж ≥ 5](Сотрудники) → срез строк

Вертикальный срез

Проекция (π)

Вырезает столбцы (атрибуты). Ненужные поля удаляются, а образовавшиеся одинаковые строки схлопываются.

π[ФИО, Должность](Сотрудники) → срез колонок

Операция Селекции (σ)

Фильтрация кортежей, удовлетворяющих истинности логического предиката φ.

σφ(R) = { t ∈ R | φ(t) = True }

Характеристики селекции

Степень (число колонок): строго сохраняется (°(σ(R)) = °(R)).
Мощность (число строк): от 0 до card(R).
Смысл: отбор записей, удовлетворяющих критерию.

Предикат φ (булево условие)

Строится из имен атрибутов, констант и операторов:

Сравнение: =, ≠, <, ≤, >, ≥
Конъюнкция (И): ∧ (AND)
Дизъюнкция (ИЛИ): ∨ (OR)
Отрицание (НЕ): ¬ (NOT)

Операция Проекции (π)

Выделение заданного набора атрибутов с ликвидацией нерелевантных столбцов.

πA1, ..., Ak(R) = { t[A1, ..., Ak] | t ∈ R }

Характеристики проекции

Степень: строго равна количеству выбранных атрибутов k (k ≤ °(R)).
Мощность: от 1 до card(R) (при непустом отношении).
Смысл: скрытие лишних колонок и декомпозиция.

Практическое назначение

Сокрытие конфиденциальных атрибутов (пароли, зарплаты).
Подготовка данных к передаче по сети (уменьшение трафика).
Формирование промежуточных таблиц для соединений и отчетов.

Автоматическое устранение дубликатов в проекции

Фундаментальный математический закон: отношение — это МНОЖЕСТВО по Кантору.

Потеря первичного ключа

В исходной таблице уникальность строк гарантировалась первичным ключом ID. Если проекция отбрасывает ID и оставляет только столбец Город, в таблице неизбежно возникнут повторы одинаковых значений.

Закон устранения повторов

Множество не может содержать одинаковых элементов: {'Сургут', 'Сургут'} = {'Сургут'}. Реляционная проекция обязана автоматически схлопнуть дубликаты в одну строку!

Пример: проекция π[Город, Должность]

Наглядная трансформация таблицы с устранением дубликатов.

Исходное отношение R (4 строки)

ID	ФИО	Город	Должность
1	Иванов	Сургут	Инженер
2	Петров	Москва	Менеджер
3	Сидоров	Сургут	Инженер
4	Козлов	Сургут	Бухгалтер

Результат π[Город, Должность] (3 строки!)

Город	Должность
Сургут	Инженер
Москва	Менеджер
Сургут	Бухгалтер

✓ Строки Иванова и Сидорова дали одинаковую пару (Сургут, Инженер) — дубликат автоматически устранен!

Суперпозиция операций: π(σ(R))

Композиция селекции и проекции — классический алгоритм извлечения данных.

Шаг 1

Внутренняя селекция

Вычисляется R' = σφ(R): фильтруются строки, не удовлетворяющие предикату φ. Набор атрибутов полный.

Шаг 2

Внешняя проекция

Вычисляется R'' = πA(R'): из отфильтрованных строк вырезаются нужные атрибуты, дубликаты схлопываются.

Правило порядка

Pushdown-предикат

Селекцию ВСЕГДА выполняют раньше проекции, чтобы уменьшить объем промежуточных данных и не потерять атрибуты из предиката.

Соответствие реляционной алгебры и SQL

Как теоретические операторы транслируются в реальный синтаксис SQL.

Реляционная алгебра Кодда

σ[Стаж ≥ 5](R)

π[Город](R)

π[ФИО, Должность](σ[Оклад < 70000](R))

Эквивалент в стандарте SQL

SELECT * FROM R WHERE exp ≥ 5;

SELECT DISTINCT city FROM R;

SELECT DISTINCT fio, post
FROM R
WHERE salary < 70000;

Почему в SQL нужен DISTINCT?

Различие между чистым математическим множеством и мультимножеством (мешком).

Инженерный компромисс SQL

В реальных базах хранятся миллионы строк. Устранение дубликатов требует либо тяжелой сортировки на диске O(N log N), либо выделения сотен мегабайт ОЗУ под хэш-таблицу.

Поэтому создатели SQL сделали проекцию по умолчанию сохраняющей дубликаты (SELECT col FROM tbl).

Когда обязателен DISTINCT?

Получение справочника уникальных значений (список городов доставки).
Устранение избыточных строк при объединениях таблиц (JOIN).
Точное соответствие требованиям математической реляционной алгебры Кодда.

Теоретико-множественные операции: ∪ и ∩

Бинарные операции над отношениями с обязательной совместимостью схем.

Объединение (R ∪ S)

Реляционное объединение

Множество всех кортежей, входящих либо в R, либо в S, либо в оба. Одинаковые строки схлопываются в одну.

SQL: UNION (без дублей) / UNION ALL (с дублями).

Требование: одинаковое число атрибутов и совместимые типы данных.

Пересечение (R ∩ S)

Реляционное пересечение

Множество кортежей, одновременно присутствующих и в отношении R, и в отношении S.

SQL: INTERSECT.

Свойство: выражается через двойную разность: R ∩ S = R \ (R \ S).

Теоретико-множественные операции: ∖ и ×

Разность отношений и прямое произведение как основа соединений.

Разность (R ∖ S)

Относительное дополнение

Кортежи, которые принадлежат отношению R, но отсутствуют в отношении S.

SQL: EXCEPT (PostgreSQL) / MINUS (Oracle).

Внимание: некоммутативна (R ∖ S ≠ S ∖ R).

Декартово произведение (R × S)

Конкатенация строк

Каждая строка отношения R сцепляется со всеми строками отношения S.

Степень: deg(R) + deg(S).
Мощность: card(R) × card(S).
SQL: CROSS JOIN.

Типовые ошибки и чек-лист самопроверки

На что обратить внимание при решении задач в рабочем листе.

✗ Забыли удалить дубликаты

Если проекция отбрасывает первичный ключ, проверьте одинаковые строки. В итоговом отношении повторяющихся кортежей быть НЕ ДОЛЖНО!

✗ Перепутали порядок срезов

Селекция фильтрует строки (высоту таблицы), проекция оставляет столбцы (ширину таблицы). Не пытайтесь удалять столбцы через σ.

✓ Проверка булевых связок

Предикат с ∧ (И) требует одновременного выполнения условий. Предикат с ∨ (ИЛИ) требует хотя бы одного.

✓ Проверка реляционной замкнутости

Убедитесь, что результат вычисления оформлен в виде полноценной таблицы со столбцами и строками, а не отдельного числа.

Классический мем реляционных баз данных: «Bobby Tables»

Комикс xkcd №327: «Exploits of a Mom» (автор Рэндалл Манро) — самый знаменитый в мире мем о реляционных СУБД, структуре запросов и безопасности данных.

Мама называет сына именем:
Robert'); DROP TABLE Students;--

Когда наивная школьная программа попыталась выполнить конкатенацию строк без реляционной типизации параметров, СУБД выполнила удаление таблицы учащихся за целый год!

Атрибуция и лицензия первоисточника:
Комикс: xkcd #327 "Exploits of a Mom" (автор Randall Munroe).
Лицензия: Creative Commons Attribution-NonCommercial 2.5 License (CC BY-NC 2.5).
Методический вывод: алгебраическая строгость предикатов, четкое разделение данных и команд — основа надежности реляционных СУБД.