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

Реляционная алгебра — это теоретический язык манипулирования данными, основанный на теории множеств и реляционной модели данных. В рамках реляционной модели все данные представляются в виде отношений (таблиц), а операции реляционной алгебры позволяют на основе одного или нескольких исходных отношений получать новое отношение, не изменяя исходные. Реляционная алгебра является формальной основой для языков запросов к реляционным базам данных, в частности, SQL, хотя последний реализует не все её операции и обладает дополнительными возможностями.

Основные понятия и определения

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

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

Базовые операции реляционной алгебры

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

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

Эти операции аналогичны операциям над множествами, но применяются к отношениям. Для их выполнения отношения должны быть совместимы по объединению, то есть иметь одинаковые схемы (одинаковое количество атрибутов с совпадающими доменами).

• Объединение (union, ∪) — возвращает отношение, содержащее все кортежи, входящие хотя бы в одно из исходных отношений. Дублирующиеся кортежи отбрасываются.
• Пересечение (intersection, ∩) — возвращает отношение, содержащее кортежи, входящие одновременно в оба исходных отношения.
• Разность (difference, −) — возвращает отношение, содержащее кортежи, входящие в первое отношение, но не входящие во второе.
• Декартово произведение (product, ×) — возвращает отношение, схема которого является объединением схем исходных отношений, а кортежи — всеми возможными комбинациями кортежей из первого и второго отношения. Если в первом отношении n кортежей, а во втором — m, то результирующее отношение содержит n*m кортежей.

Специальные реляционные операции

Эти операции учитывают структуру отношений и являются уникальными для реляционной модели.

• Выборка (select, σ) — операция горизонтального подмножества. Возвращает отношение, содержащее только те кортежи исходного отношения, которые удовлетворяют заданному логическому условию (предикату). Например, σ(Возраст > 30) отберет все строки таблицы, где значение атрибута «Возраст» больше 30.
• Проекция (project, π) — операция вертикального подмножества. Возвращает отношение, схема которого состоит из указанного набора атрибутов исходного отношения. Кортежи при этом «усекаются» до этих атрибутов, а дублирующиеся кортежи удаляются. Например, π(Фамилия, Имя) оставит в таблице только столбцы с фамилиями и именами.
• Соединение (join, ⋈) — одна из важнейших операций. В общем виде (θ-соединение) она возвращает отношение, кортежи которого являются комбинациями кортежей из двух исходных отношений, удовлетворяющих заданному условию. На практике наиболее часто используется естественное соединение (natural join), при котором отношения соединяются по совпадающим значениям атрибутов с одинаковыми именами (атрибуты-ключи). Промежуточное декартово произведение «фильтруется» так, чтобы одинаковые атрибуты имели равные значения, затем один из дублирующихся столбцов удаляется.
• Деление (division, ÷) — операция, обратная декартову произведению. Позволяет найти кортежи из первого отношения, которые соответствуют всем кортежам второго отношения. Например, если первое отношение содержит список студентов и курсов, которые они посещают, а второе — список всех курсов, то деление первого на второе вернет список студентов, посещающих все курсы.

Производные операции

Некоторые операции могут быть выражены через базовые. К часто используемым производным относятся:

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

История и развитие

Концепция реляционной алгебры была предложена британским математиком и информатиком Эдгаром Фрэнком Коддом в 1970 году в его основополагающей статье «A Relational Model of Data for Large Shared Data Banks». Кодд стремился создать математически строгую модель для управления данными, которая была бы независимой от физической организации хранения и обеспечивала бы гибкость и простоту работы.

В 1974 году Кодд и его коллега Кристофер Дейт доработали алгебру, назвав её Реляционной алгеброй Кодда. Позднее появились её модификации, такие как Унарная реляционная алгебра (использующая только выборку, проекцию и переименование) и Алгебра с каналами (pipe algebra), которая легла в основу языков запросов, работающих с потоками данных.

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

Сравнение с реляционным исчислением

Наряду с реляционной алгеброй существует альтернативный формальный язык — реляционное исчисление. Реляционное исчисление является декларативным: оно описывает не порядок выполнения операций, а свойства желаемого результата. Например, в исчислении кортежей запрос «Найти всех студентов старше 30 лет» выглядит как {t | Студент(t) AND t.Возраст > 30}. Коддом была доказана эквивалентность (равномощность) реляционной алгебры и реляционного исчисления по выразительной силе: любой запрос, который можно сформулировать на одном языке, можно сформулировать и на другом.

Критика и ограничения

• Эффективность на практике: Прямая реализация операций реляционной алгебры, особенно декартова произведения и соединения, может быть крайне ресурсоёмкой. Поэтому реальные СУБД используют оптимизированные алгоритмы (сортировка, хэш-соединения, индексы), а не наивное следование теоретическим операциям.
• Отсутствие рекурсии: Классическая реляционная алгебра не поддерживает рекурсивные запросы (например, поиск всех подчинённых в иерархии сотрудников). Для этого были предложены расширения, такие как рекурсивное объединение в SQL (WITH RECURSIVE).
• Замкнутость: Хотя замкнутость — преимущество, она требует, чтобы все операции возвращали отношения. Это может приводить к потере семантики при работе с упорядоченными результатами (например, при ранжировании), так как в отношении порядок кортежей не определён.
• Обработка NULL-значений: В стандартной реляционной алгебре нет специальных правил для работы с пропущенными значениями (NULL), что приводит к трёхзначной логике (истина/ложь/неизвестно) в реальных SQL-реализациях и сложностям при оптимизации.

Источники

1. Кодд, Э. Ф. (1970). «A Relational Model of Data for Large Shared Data Banks». Communications of the ACM, 13(6), 377–387.
2. Дейт, К. Дж. (1981). «An Introduction to Database Systems» (3rd ed.). Addison-Wesley.
3. Ульман, Дж. Д., & Виджи С. (2002). «Основы систем баз данных» (2-е изд.). Вильямс.
4. Гарсия-Молина, Г., Ульман, Дж. Д., & Виджи, Дж. (2009). «Системы баз данных: полный курс». Вильямс.