Введение

Теория реляционных баз данных

В теории баз данных реляционная алгебра – это теория, использующая алгебраические структуры для моделирования данных и определения запросов к ним с чётко определённой семантикой. Теория была предложена Эдгаром Ф. Коддом. Основное применение реляционной алгебры – обеспечение теоретической основы для реляционных баз данных, в частности, языков запросов к таким базам данных, среди которых SQL является основным. Реляционные базы данных хранят табличные данные, представленные в виде отношений. Запросы к реляционным базам данных часто также возвращают табличные данные, представленные в виде отношений. Основная цель реляционной алгебры – определение операторов, преобразующих одно или несколько входных отношений в выходное отношение. Поскольку эти операторы принимают отношения на вход и выдают отношения на выход, их можно комбинировать для выражения сложных запросов, преобразующих несколько входных отношений (данные которых хранятся в базе данных) в одно выходное отношение (результат запроса). Унитарные операторы принимают на вход одно отношение. Примеры включают операторы для фильтрации определённых атрибутов (столбцов) или кортежей (строк) из входного отношения. Бинарные операторы принимают два отношения на вход и объединяют их в одно выходное отношение. Например, выборка всех кортежей, найденных в любом из отношений (объединение), удаление кортежей из первого отношения, найденных во втором отношении (разность), расширение кортежей первого отношения кортежами из второго отношения, удовлетворяющими определённым условиям, и так далее. Также могут быть включены и другие, более сложные операторы, причём включение или исключение определённых операторов приводит к формированию семейства алгебр.

Введение

Реляционная алгебра не привлекала особого внимания за пределами чистой математики до публикации реляционной модели данных Э. Ф. Кодда в 1970 году. Кодд предложил эту алгебру в качестве основы для языков запросов к базам данных. (См. раздел "Реализации".) Реляционная алгебра оперирует однородными множествами кортежей, где обычно m интерпретируется как количество строк в таблице, а n – как количество столбцов. Все элементы в каждом столбце имеют один и тот же тип. Пять примитивных операций алгебры Кодда – это выборка, проекция, декартово произведение (также называемое перекрестным произведением или перекрестным соединением), объединение множеств и разность множеств.

Операторы

В реляционной алгебре используются объединение множеств, разность множеств и декартово произведение из теории множеств, но для этих операторов вводятся дополнительные ограничения. Для объединения и разности множеств два отношения должны быть совместимы по объединению – то есть, оба отношения должны иметь один и тот же набор атрибутов. Поскольку пересечение множеств определяется через объединение и разность множеств, два отношения, участвующие в пересечении, также должны быть совместимы по объединению. Для определения декартова произведения два участвующих отношения должны иметь непересекающиеся заголовки – то есть, они не должны иметь общих имен атрибутов. Кроме того, декартово произведение определяется иначе, чем в теории множеств, в том смысле, что кортежи рассматриваются как "плоские" для целей данной операции. То есть, декартово произведение множества из n кортежей с множеством из m кортежей дает множество "развернутых" (n + m) кортежей (в то время как базовая теория множеств предписывала бы множество из 2 кортежей, каждый из которых содержит n-кортеж и m-кортеж). Более формально, R × S определяется следующим образом:

Мощность декартова произведения равна произведению мощностей его сомножителей, то есть, |R × S| = |R| × |S|.

Проекция ()

Проекция — это унарная операция, записываемая как Π<sub>A</sub>R, где A — набор имен атрибутов. Результат такой проекции определяется как множество, получаемое при ограничении всех кортежей в R набором A. Примечание: при реализации в соответствии со стандартом SQL "проекция по умолчанию" возвращает мультимножество вместо множества, а проекция Π для исключения дубликатов достигается добавлением ключевого слова DISTINCT.

Выбор (σ)

Обобщенный выбор — это унарная операция, записываемая как , где — это пропозициональная формула, состоящая из атомов, допустимых в обычном выборе, и логических операторов (И), (ИЛИ) и (ОТРИЦАНИЕ). Этот выбор отбирает все кортежи в R, для которых выполняется условие . Чтобы получить список всех друзей или деловых партнеров в адресной книге, выбор можно записать как . Результатом будет отношение, содержащее каждый атрибут каждой уникальной записи, где size=90% истинно или где size=90% истинно.

Переименование (ρ)

Переименование — это унарная операция, записываемая как , где результат идентичен R, за исключением того, что атрибут b во всех кортежах переименовывается в атрибут a. Это используется просто для переименования атрибута отношения или самого отношения. Для переименования атрибута "isFriend" в "isBusinessContact" в отношении может быть использовано . Существует также обозначение , где R переименовывается в x, а атрибуты переименовываются в .

Общие расширения

На практике классическая реляционная алгебра, описанная выше, расширяется различными операциями, такими как внешние объединения, агрегатные функции и даже транзитивное замыкание.

Внешние соединения

В то время как результат соединения (или внутреннего соединения) состоит из кортежей, сформированных путем объединения совпадающих кортежей в двух операндах, внешнее соединение содержит эти кортежи и, дополнительно, некоторые кортежи, сформированные путем расширения несоответствующего кортежа в одном из операндов "заполнителями" для каждого из атрибутов другого операнда. Внешние соединения не рассматриваются как часть классической реляционной алгебры, обсуждаемой до настоящего момента. Операторы, определенные в этом разделе, предполагают существование нулевого значения ω, которое мы не определяем, для использования в качестве значений-заполнителей; на практике это соответствует NULL в SQL. Чтобы последующие операции отбора в полученной таблице имели смысл, нулевым значениям необходимо придать семантическое значение; в подходе Кодда пропозициональная логика, используемая отбором, расширяется до трехзначной логики, хотя мы опускаем эти детали в данной статье. Определены три оператора внешнего соединения: левое внешнее соединение, правое внешнее соединение и полное внешнее соединение. (Слово "внешний" иногда опускается.)

Операции для вычислений домена

До сих пор в реляционной алгебре не представлено ничего, что позволило бы выполнять вычисления над областями данных (за исключением вычисления логических выражений, включающих равенство). Например, используя только алгебру, представленную до сих пор, невозможно записать выражение, которое бы умножало числа из двух столбцов, например, цену за единицу на количество, чтобы получить общую стоимость. Практические языки запросов обладают такими возможностями: например, в SQL SELECT разрешены арифметические операции для определения новых столбцов в результате – SELECT цена_за_единицу * количество AS общая_стоимость FROM t, а Tutorial D предоставляет аналогичную возможность более явно с помощью ключевого слова EXTEND. В теории баз данных это называется расширенной проекцией.

Переходное закрытие

Хотя реляционная алгебра кажется достаточно мощной для большинства практических целей, существуют некоторые простые и естественные операции над отношениями, которые нельзя выразить средствами реляционной алгебры. Одной из них является транзитивное замыкание бинарного отношения. Пусть задана область D, и пусть бинарное отношение R является подмножеством D×D. Транзитивное замыкание R+ отношения R – это наименьшее подмножество D×D, содержащее R и удовлетворяющее следующему условию:

Это можно доказать, основываясь на том, что не существует выражения реляционной алгебры E(R), принимающего R в качестве аргумента, которое бы выдавало R+. Однако SQL официально поддерживает такие запросы, вычисляющие неподвижные точки, начиная с 1999 года, а специализированные расширения в этом направлении существовали и у отдельных производителей баз данных задолго до этого.

Выбор

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

Основные свойства выбора

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

Разделение выборов с сложными условиями

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

Селекция и кросс-продукт

Кроссовое произведение – самый дорогостоящий оператор для вычисления. Если входные отношения содержат N и M строк, результат будет содержать строк. Поэтому важно уменьшить размер обоих операндов перед применением оператора кроссового произведения. Это можно эффективно сделать, если за кроссовым произведением следует оператор отбора, например, учитывая определение операции соединения (join), это наиболее вероятный случай. Если за кроссовым произведением не следует оператор отбора, можно попытаться "опустить" отбор с более высоких уровней дерева выражений, используя другие правила отбора. В вышеописанном случае условие A разбивается на условия B, C и D с использованием правил разделения сложных условий отбора, так что B содержит атрибуты только из R, C содержит атрибуты только из P, а D содержит часть A, которая содержит атрибуты как из R, так и из P. Следует отметить, что B, C или D могут быть пустыми. Тогда справедливо следующее:

Операторы выбора и набора

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

Выбор и проекция

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

Основные свойства проекции

Проекция является идемпотентной, поэтому последовательность (корректных) проекций эквивалентна самой внешней проекции.

Основные свойства переименования

Последовательные переименования одной и той же переменной могут быть объединены в одно переименование. Операции переименования, не затрагивающие общие переменные, могут быть переупорядочены произвольным образом, что позволяет сгруппировать последовательные переименования для последующего объединения.

Переименование и набор операторов

Переименование дистрибутивно относительно разности множеств, объединения и пересечения.

Продукт и союз

Декартово произведение распределительно относительно объединения.

Реализация

Первым языком запросов, основанным на алгебре Кодда, был Alpha, разработанный самим доктором Коддом. Впоследствии был создан ISBL, и эта новаторская работа была признана многими авторитетами как указавшая путь к реализации идеи Кодда в полезный язык. Business System 12 была недолговечной, но промышленно-ориентированной реляционной СУБД, которая следовала примеру ISBL. В 1998 году Крис Дэйт и Хью Дарвен предложили язык Tutorial D, предназначенный для обучения теории реляционных баз данных, а его язык запросов также опирается на идеи ISBL. Rel является реализацией Tutorial D.

Даже язык запросов SQL в некоторой степени основан на реляционной алгебре, хотя операнды в SQL (таблицы) не являются строго отношениями, и некоторые полезные теоремы реляционной алгебры не применимы к аналогу SQL (что, возможно, негативно сказывается на оптимизаторах и/или пользователях). Модель таблицы SQL представляет собой множество с повторениями (multiset), а не множество. Например, выражение является теоремой для реляционной алгебры множеств, но не для реляционной алгебры множеств с повторениями; подробнее о реляционной алгебре множеств с повторениями можно узнать в главе 5 учебника "Complete" Гарсии Молины, Ульмана и Видома.