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

1. Введение: что такое реляционная алгебра?

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

В 1970 году создатель реляционной модели Эдгар Франк Кодд (Edgar F. Codd) предложил строгий математический аппарат для манипулирования данными — реляционную алгебру (Relational Algebra). Это процедурный язык запросов, в котором операции применяются к отношениям и порождают новые отношения.

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

Свойство замкнутости — краеугольный камень теории реляционных баз данных. Оно гласит:

• Если на вход подается таблица (отношение), то на выходе мы гарантированно получаем снова таблицу (отношение), а не массив указателей, не отдельное скалярное число и не дерево объектов.
• Благодаря замкнутости операции можно бесконечно комбинировать, создавая суперпозиции (вложенные выражения): результат первого действия немедленно становится входом для второго.
• Именно реляционная замкнутость позволяет писать в SQL вложенные подзапросы и выражения WITH ... AS (CTE).

2. Геометрическая концепция унарных операций

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

3. Операция Выборки (Селекции, $\sigma$)

Математическое обозначение: греческая буква $\sigma$ (сигма) с индексом-предикатом $\varphi$:

Здесь:

• $R$ — исходное отношение.
• $t$ — кортеж (строка) отношения $R$.
• $\varphi$ — логический предикат (условие отбора). Может содержать атрибуты, константы, операторы сравнения ($=, \ne, <, \le, >, \ge$) и булевы логические операторы:
  • $\land$ — конъюнкция (логическое И / AND);
  • $\lor$ — дизъюнкция (логическое ИЛИ / OR);
  • $\neg$ — отрицание (логическое НЕ / NOT).

Свойства выборки:

1. Степень отношения (количество столбцов) не меняется: $\text{deg}(\sigma_\varphi(R)) = \text{deg}(R)$. Все столбцы схемы остаются на месте.
2. Мощность отношения (количество строк) уменьшается или сохраняется: $0 \le \text{card}(\sigma_\varphi(R)) \le \text{card}(R)$.
3. Коммутативность последовательных выборок: $\sigma_{\varphi_1}(\sigma_{\varphi_2}(R)) \equiv \sigma_{\varphi_2}(\sigma_{\varphi_1}(R)) \equiv \sigma_{\varphi_1 \land \varphi_2}(R)$.

4. Операция Проекции ($\pi$) и устранение дубликатов

Математическое обозначение: греческая буква $\pi$ (пи) с перечнем оставляемых атрибутов в подстрочном индексе:

Закон устранения дубликатов

Постулат теории множеств гласит: множество не может содержать одинаковых элементов. В исходном отношении $R$ уникальность каждой строки гарантировалась первичным ключом (например, ID). Но если мы проецируем таблицу на атрибуты, не включающие первичный ключ (например, только на столбец Город), в столбце неизбежно возникнут повторы.

Свойства проекции:

1. Степень результата равна количеству спроецированных атрибутов: $\text{deg}(\pi_{A_1, \dots, A_k}(R)) = k$.
2. Мощность результата не превышает мощности исходного отношения: $\text{card}(\pi_A(R)) \le \text{card}(R)$.
3. Идемпотентность повторной проекции на то же подмножество: $\pi_A(\pi_{A \cup B}(R)) \equiv \pi_A(R)$.

5. Суперпозиция операций: $\pi(\sigma(R))$ и пошаговый пример

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

Исходное отношение «Преподаватели» ($T$):

Задача: Вычислить выражение $\pi_{\text{Кафедра}}(\sigma_{\text{Стаж} \ge 6 \land \text{Оклад} < 80000}(T))$

Шаг 1. Вычисляем внутреннюю операцию — селекцию $\sigma$:
Предикат: $\text{Стаж} \ge 6$ И $\text{Оклад} < 80000$. Проверяем каждый кортеж:

• Кортеж 1: Иванов (Стаж 8 $\ge$ 6 — ДА, Оклад 65000 < 80000 — ДА). Подходит!
• Кортеж 2: Петров (Стаж 3 $\ge$ 6 — НЕТ). Не подходит.
• Кортеж 3: Сидорова (Стаж 12 $\ge$ 6 — ДА, Оклад 82000 < 80000 — НЕТ). Не подходит.
• Кортеж 4: Смирнов (Стаж 6 $\ge$ 6 — ДА, Оклад 59000 < 80000 — ДА). Подходит!
• Кортеж 5: Козлова (Стаж 10 $\ge$ 6 — ДА, Оклад 71000 < 80000 — ДА). Подходит!

Промежуточное отношение $T' = \sigma(T)$:

Шаг 2. Вычисляем внешнюю операцию — проекцию $\pi_{\text{Кафедра}}$:
Вырезаем только столбец «Кафедра». Из строк Иванова и Смирнова получаем два значения «Информатика». По правилу Кодда дубликаты схлопываются!

Финальный результат $\pi_{\text{Кафедра}}(T')$:

Итог: Отношение степени 1 и мощности 2.

6. Сопоставление с языком SQL

В реляционных СУБД декларативным языком взаимодействия является SQL. Важно понимать, как формулы реляционной алгебры транслируются в реальные команды:

-- Реляционная селекция: sigma_{стаж >= 6}(T)
SELECT * 
FROM Teachers 
WHERE experience >= 6;

-- Реляционная проекция с устранением дубликатов: pi_{department}(T)
SELECT DISTINCT department 
FROM Teachers;

-- SQL-проекция БЕЗ устранения дубликатов (мультимножество):
SELECT department 
FROM Teachers;

-- Суперпозиция: pi_{department}(sigma_{experience >= 6 AND salary < 80000}(T))
SELECT DISTINCT department
FROM Teachers
WHERE experience >= 6 AND salary < 80000;

7. Обзор теоретико-множественных операций реляционной алгебры

Помимо унарных операций, реляционная алгебра включает четыре базовые бинарные операции над парами отношений $R$ и $S$: