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

Реляционная алгебра, впервые созданная Эдгаром Ф. Коддом в IBM, представляет собой семейство алгебр с хорошо обоснованной семантикой, используемой для моделирования данных, хранящихся в реляционных базах данных, и определения запросов к ним.

Основное применение реляционной алгебры заключается в теоретическом обосновании реляционных баз данных, в частности языков запросов для таких баз данных, главным из которых является SQL

Навь-яга. Учение о мере стихий, а мерой стихий является движение - в нашем случае бег. Поэтому предметом её изучающему, являлась алгебра (ал + «геб», обратное бег).

Введение

Реляционная алгебра получала мало внимания за пределами чистой математики до публикации реляционной модели данных E. F. Codd в 1970 году. Codd предложил такую алгебру в качестве основы для языков запросов баз данных. (См. раздел реализации .) $S=\{(s_{j1},s_{j2},...s_{jn})|j\in 1...m\}$

Пять примитивных операторов алгебры Codd являются выбором, проекцией, декартовым произведением (также называемым перекрестным произведением или перекрестным соединением), объединением множеств и разностью множеств .

Задать операторы

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

Для объединения множеств и разности множеств два связанных отношения должны быть совместимы с Союзом —то есть два отношения должны иметь один и тот же набор атрибутов. Поскольку пересечение множеств определяется в терминах объединения множеств и разности множеств, два отношения, участвующие в пересечении множеств, также должны быть совместимы с объединением.

Чтобы декартово произведение было определено, эти два отношения должны иметь несвязанные заголовки—то есть они не должны иметь общего имени атрибута.

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

R × S := { ( r 1 , r 2 , … , r n , s 1 , s 2 , … , s m ) | ( r 1 , r 2 , … , r n ) ∈ R , ( s 1 , s 2 , … , s m ) ∈ S }

Кардинальность декартова произведения есть произведение кардинальностей его факторов, то есть | R × S | = | R | × | S |.

Проекция (Π)

Основная статья: проекция (реляционная алгебра)

Проекция-это унарная операция, записанная как Π a 1 , … , a n ( R ) ldots, a_n-набор имен атрибутов. Результат такой проекции определяется как множество, которое получается, когда все Кортежи в R ограничены множеством { a 1 , … , a n }

Примечание: при реализации в стандарте SQL "проекция по умолчанию" возвращает multiset вместо set, и проекция Π получается добавлением DISTINCTключевого слова для устранения дубликатов данных.

Selection (σ )

Основная статья: выбор (реляционная алгебра)

Обобщенный выбор-это унарная операция, записанная как σ φ ( R ) где φ-пропозициональная формула, состоящая из атомов, разрешенных в нормальном отборе, и логических операторов ∧ , ∨ и ¬ \отрицательный ( отрицание ). Этот выбор выбирает все те кортежи в R, для которых выполняется φ.

Чтобы получить список всех друзей или деловых партнеров в адресной книге, выбор может быть записан как σ isFriend = true ∨ isBusinessContact = true ( addressBook ) = true}} . Результатом будет отношение, содержащее каждый атрибут каждой уникальной записи, где isfriend имеет значение true или где isBusinessContact имеет значение true.

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

Основная статья: переименовать (реляционная алгебра)

Переименование-это унарная операция, в ρ a / b ( R )(R)которой результат идентичен R, за исключением того, что атрибут b во всех кортежах переименован в атрибут a. Это просто используется для переименования атрибута отношения или самого отношения.

Чтобы переименовать атрибут "isFriend" в "isBusinessContact" в отношении, ρ isBusinessContact / isFriend ( addressBook ) )может использоваться.

Операторы join и join-like

Естественное соединение ( ⋈ )

"Natural join" перенаправляет сюда. Реализацию SQL см. В разделе Natural join (SQL) .

Естественное соединение ( ⋈ ) является двоичным оператором, который записывается как ( R ⋈ S), где R и S-отношения .[1] результатом естественного объединения является множество всех комбинаций кортежей в R и S, равных по общим именам атрибутов. В качестве примера рассмотрим таблицы Employee и Dept и их естественное соединение:

Работник

Имя	EmpId	DeptName
Разорять	3415	Финансы
Вылазка	2241	Продажи
Джордж	3401	Финансы
Гарриет	2202	Продажи

Отдел

DeptName	Менеджер
Финансы	Джордж
Продажи	Гарриет
Производство	Чарльз

Сотрудник DEP Dept

Имя	EmpId	DeptName	Менеджер
Разорять	3415	Финансы	Джордж
Вылазка	2241	Продажи	Гарриет
Джордж	3401	Финансы	Джордж
Гарриет	2202	Продажи	Гарриет

Это также может быть использовано для определения состава отношений . Например, состав Employee и Dept является их соединением, как показано выше, проецируемым на все, кроме общего атрибута DeptName . В теории категорий, соединение точно продукт волокна .

Естественное соединение, возможно, является одним из наиболее важных операторов, поскольку оно является реляционным аналогом логического И. Обратите внимание, что если одна и та же переменная появляется в каждом из двух предикатов, связанных с помощью и, то эта переменная означает одно и то же, и оба вида всегда должны быть заменены одним и тем же значением. В частности, естественное соединение позволяет комбинировать отношения, связанные внешним ключом . Например, в приведенном выше примере внешний ключ, вероятно, содержится от Employee .DeptName к Dept .DeptName, а затем естественное соединение сотрудника и Dept объединяет всех сотрудников со своими отделами. Это работает, потому что внешний ключ удерживается между атрибутами с тем же именем. Если это не так, например, во внешнем ключе от Dept .Менеджер сотруднику .Имя затем мы должны переименовать эти столбцы, прежде чем мы примем естественное соединение. Такое соединение иногда также называют equijoin (см. θ-join).

Более формально семантика естественного соединения определяется следующим образом:

R  S =  {R \ cup s  r \in R  s \in S  mathit{Fun} (r \cup s) }

где Fun-предикат, истинный для отношения t (в математическом смысле) , если t-функция. Обычно требуется, чтобы R и S имели хотя бы один общий атрибут, но если это ограничение опущено, а R и S не имеют общих атрибутов, то естественное соединение становится точно декартовым произведением.

Естественное соединение можно смоделировать с примитивами Codd следующим образом. Предположим, что c 1,...,.., c m-имена атрибутов, общие для R и S, r 1,..., r n являются имена атрибутов, уникальные для R и s 1 ,..., s k являются имена атрибутов, уникальные для S . Кроме того, предположим, что имя атрибута x 1,..., x m не находятся ни в R, ни в S . На первом этапе мы можем переименовать общие имена атрибутов в S:

См.в ен википедии .

join-join и equijoin

Рассмотрим таблицы автомобиль и лодка, в которых перечислены модели автомобилей и лодок и их соответствующие цены. Предположим, клиент хочет купить автомобиль и лодку, но он не хочет тратить больше денег на лодку, чем на автомобиль. Θ-join (⋈ θ ) на предикате CarPrice ≥ Boatprice создает уплощенные пары строк, которые удовлетворяют предикату. При использовании условия, где атрибуты равны, например Price, то условие может быть указано как Price = Price или альтернатива (цена) сама по себе.

См.в ен википедии .

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

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

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

Основная статья: внешнее соединение

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

Операторы, определенные в этом разделе, предполагают существование значения null, ω, которое мы не определяем, для использования для значений заполнения; на практике это соответствует NULL в SQL. Для того, чтобы сделать последующие операции выбора на результирующей таблице значимыми , семантическое значение должно быть присвоено нулям; в подходе Codd пропозициональная логика, используемая выбором, расширена до трехзначной логики, хотя мы выделяем эти детали в этой статье.

Определены три внешних оператора соединения: левое внешнее соединение, правое внешнее соединение и полное внешнее соединение. (Слово "внешний" иногда опускается.)

Левое внешнее соединение ( ⟕ )

Левое внешнее соединение записывается как R ⟕ S, где R и S-отношения .[7] результатом левого внешнего соединения является набор всех комбинаций кортежей в R и S, которые равны по их общим именам атрибутов, в дополнение (грубо говоря) к кортежам в R, которые не имеют совпадающих кортежей в S .

В качестве примера рассмотрим таблицы Employee и Dept и их левое внешнее соединение:

В результирующем отношении кортежи в S, которые не имеют общих значений в общих именах атрибутов с кортежами в R, принимают нулевое значение, ω .

Поскольку в Dept нет кортежей с именем Dept из Finance или Executive, ω s возникают в результирующей связи, где кортежи в Employee имеют имя Dept из Finance или Executive .

Пусть r 1, r 2,...,.., r n-атрибуты отношения R и пусть {( ω,...,.., ω)} быть синглтоном отношение к атрибутам, уникальным для отношения S (не являющимся атрибутами R ). Тогда левое внешнее соединение может быть описано в терминах естественного соединения (и, следовательно, с использованием базовых операторов) следующим образом:

Правое внешнее соединение ( ⟖ )

Правое внешнее соединение ведет себя почти идентично левому внешнему соединению, но роли таблиц переключаются.

Правое внешнее соединение отношений R и S записывается как R ⟖ S .[8] результатом правого внешнего объединения является набор всех комбинаций кортежей в R и S, которые равны по общим именам атрибутов, в дополнение к кортежам в S, у которых нет совпадающих кортежей в R .

Например, рассмотрим таблицы Employee и Dept и их правое внешнее соединение:

В результирующем отношении кортежи в R, которые не имеют общих значений в общих именах атрибутов с кортежами в S, принимают нулевое значение, ω .

Поскольку в Employee нет кортежей с именем DeptName производства, ω s встречаются в атрибутах Name и EmpId результирующего отношения, где кортежи в Dept имели имя DeptName производства .

Пусть s 1, s 2,..., s n-атрибуты отношения S и пусть {( ω,...,.., ω)} быть синглтоном отношение к атрибутам, уникальным для отношения R (не являющимся атрибутами S ). Затем, как и с левым внешним соединением, правое внешнее соединение можно смоделировать с помощью естественного соединения следующим образом:

Полное внешнее соединение ( ⟗ )

Внешнее соединение или полное внешнее соединение фактически объединяет результаты левого и правого внешних соединений.

Полное внешнее соединение записывается как R ⟗ S, где R и S-отношения .[9] результатом полного внешнего объединения является набор всех комбинаций кортежей в R и S, которые равны по их общим именам атрибутов, в дополнение к кортежам в S, у которых нет совпадающих кортежей в R и кортежей в R, у которых нет совпадающих кортежей в S в их общих именах атрибутов.

Для примера рассмотрим таблицы Employee и Dept и их полное внешнее объединение: В результирующем отношении кортежи в R, которые не имеют общих значений в общих именах атрибутов с кортежами в S, принимают нулевое значение, ω . Кортежи в S, которые не имеют общих значений в общих именах атрибутов с кортежами в R, также принимают нулевое значение, ω .

Полное внешнее соединение можно смоделировать с помощью левого и правого внешних соединений (и, следовательно, естественного соединения и соединения набора) следующим образом:

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

В реляционной алгебре до сих пор нет ничего, что позволяло бы вычисления на областях данных (кроме оценки пропозициональных выражений, включающих равенство). Например, невозможно использовать только алгебру, введенную до сих пор, чтобы написать выражение, которое умножало бы числа из двух столбцов, например, цену единицы с количеством, чтобы получить общую цену. Практические языки запросов имеют такие возможности , например, SQL SELECT позволяет арифметическим операциям определять новые столбцы в результатеSELECT unit_price * quantity AS total_price FROM t, и аналогичная возможность предоставляется более явно ключевым словом Tutorial D 'sEXTEND.[10] В теории баз данных это называется расширенной проекцией .

Агрегация

Кроме того, вычисление различных функций на столбце, таких как суммирование его элементов, также невозможно с помощью реляционной алгебры, введенной до сих пор. Существует пять агрегатных функций, которые включены в большинство систем реляционных баз данных. Это операции Sum, Count, Average, Maximum и Minimum. В реляционной алгебре операция агрегации по схеме (A 1, A 2,...,.. A n) записывается следующим образом:

Формула

где каждый A j ', 1 ≤ j ≤ k , является одним из исходных атрибутов a i , 1 ≤ i ≤ n .

Атрибуты, предшествующие g, являются атрибутами группировки, которые функционируют как предложение "group by" в SQL. Затем к отдельным атрибутам применяется произвольное число функций агрегации. Операция применяется к произвольному отношению r . Атрибуты группирования являются необязательными, и если они не предоставлены, функции агрегации применяются по всему отношению, к которому применяется операция.

Предположим, что у нас есть таблица с именем Счет с тремя столбцами, а именно Account_Number, Branch_Name и Баланс . Мы хотим найти максимальный баланс каждой ветви. Это достигается Branch_NameGMax(Баланс )(Account). Чтобы найти самый высокий баланс всех счетов независимо от филиала, мы можем просто написать G Max(Баланс )(Account).

Транзитивное закрытие

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

Формула

Не существует выражения реляционной алгебры E (R), принимающего R в качестве переменного аргумента, порождающего R + . Это можно доказать, используя тот факт , что, учитывая реляционное выражение E, для которого утверждается, что E ( R ) = R+, где R-переменная, мы всегда можем найти экземпляр r R (и соответствующую область d ) такой, что E ( r ) ≠ r + .[12]

SQL, однако, официально поддерживает такие запросы fixpoint с 1999 года, и у него были специальные расширения поставщиков в этом направлении задолго до этого.

Использование алгебраических свойств для оптимизации запросов

Запросы могут быть представлены в виде дерева, где

• внутренние узлы являются операторами,
• листья-это отношения,
• поддеревья являются подвыражениями.

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

Здесь мы представляем набор правил, которые могут быть использованы в таких преобразованиях.

Выбор

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

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

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

1. $\sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!$
2. $\sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!$

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

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

1. $\sigma _{A\land B}(R)=\sigma _{A}(\sigma _{B}(R))=\sigma _{B}(\sigma _{A}(R))$
2. $\sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)$

Выбор и перекрестный продукт

Кросс-продукт является самым дорогостоящим оператором для оценки. Если входные отношения имеют N и M строк, результат будет содержать N M {\displaystyle NM} МОРСКАЯ МИЛЯстроки. Поэтому очень важно сделать все возможное, чтобы уменьшить размер обоих операндов перед применением оператора кросс-произведения.

Это может быть эффективно сделано, если кросс-продукт сопровождается оператором выбора, например σ A ( R × P ) {A}(R\times P)}. Учитывая определение join, это наиболее вероятный случай. Если за перекрестным произведением не следует оператор выборки, можно попытаться протолкнуть выборку с более высоких уровней дерева выражений, используя другие правила выборки.

В приведенном выше случае мы разбиваем условие A на условия B , C и D, используя правила разбиения о сложных условиях выбора , так что A = B ∧ C ∧ D D} }ко из P, А D содержит часть A, которая содержит атрибуты как из R, так и из P . Обратите внимание , что B, C или D, возможно, пусты. Затем выполняются следующие действия:

$\sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R)\times \sigma _{C}(P))$

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

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

1. $\sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P$
2. $\sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)$
3. $\sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)$

Выделение и проецирование

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

$\pi _{a_{1},\ldots ,a_{n}}(\sigma _{A}(R))=\sigma _{A}(\pi _{a_{1},\ldots ,a_{n}}(R)){\text{ where fields in }}A\subseteq \{a_{1},\ldots ,a_{n}\}$

Проекция

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

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

$\pi _{a_{1},\ldots ,a_{n}}(\pi _{b_{1},\ldots ,b_{m}}(R))=\pi _{a_{1},\ldots ,a_{n}}(R){\text{ where }}\{a_{1},\ldots ,a_{n}\}\subseteq \{b_{1},\ldots ,b_{m}\}$

Операторы проекции и набора

Проекция распределительна по множеству union.

$\pi _{a_{1},\ldots ,a_{n}}(R\cup P)=\pi _{a_{1},\ldots ,a_{n}}(R)\cup \pi _{a_{1},\ldots ,a_{n}}(P).\,$

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

$\pi _{A}(\{\langle A=a,B=b\rangle \}\cap \{\langle A=a,B=b'\rangle \})=\emptyset$

$\pi _{A}(\{\langle A=a,B=b\rangle \})\cap \pi _{A}(\{\langle A=a,B=b'\rangle \})=\{\langle A=a\rangle \}$

и

$\pi _{A}(\{\langle A=a,B=b\rangle \}\setminus \{\langle A=a,B=b'\rangle \})=\{\langle A=a\rangle \}$

$\pi _{A}(\{\langle A=a,B=b\rangle \})\setminus \pi _{A}(\{\langle A=a,B=b'\rangle \})=\emptyset \,,$

Где предполагается b в отличие от b'

Реализации

Первым языком запросов, основанным на алгебре Codd, был Alpha, разработанный самим Доктором Коддом. Впоследствии был создан ISBL, и эта новаторская работа была признана многими авторитетами [1] Как показавшая способ превратить идею Codd в полезный язык. Бизнес-система 12 была недолговечной отраслевой реляционной СУБД, которая следовала примеру ISBL.

В 1998 году Крис Дейт и Хью Дарвен предложили язык под названием Tutorial D, предназначенный для обучения теории реляционных баз данных, и его язык запросов также опирается на идеи ISBL. Rel является реализацией учебника D .

Даже язык запросов SQL слабо основан на реляционной алгебре, хотя операнды в SQL ( таблицы ) не являются точными отношениями и несколько полезных теорем о реляционной алгебре не удерживаются в аналоге SQL (возможно, в ущерб оптимизаторам и/или пользователям). Табличная модель SQL является сумкой (multiset), а не набором. Например, выражение ( R ∪ S ) ∖ T = ( R ∖ T ) ∪ ( S ∖ T ) {\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)} {\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}является теоремой для реляционной алгебры на множествах , но не для реляционной алгебры на мешках; для обработки реляционной алгебры на мешках см. Главу 5 "полного" учебника Гарсия-Молина, Уллмана и Видома

См. также

• Декартово произведение
• D (спецификация языка данных)
• D4 (язык программирования) (реализация D) *

База данных * Логика родственников * Объектно-ролевое моделирование * Проекция (математика)

• Проекция (реляционная алгебра)
• Проекция (теория множеств)
• Отношение

Связь (база данных) * Алгебра отношений * Состав отношения * Построение отношений

• Реляционное исчисление
• Реляционная база данных *

Реляционная модель * Теория отношений * Триадное отношение

• Учебник D
• Кортеж реляционное исчисление

Пруф

slinfo.una.ac.cr/rat/rat.html

• .databasteknik.se/webbkursen/relalg-lecture/index.html
• ltworf.github.io/relational/index.html
• cs.stanford.edu/people/widom/cs346/ioannidis.pdf
• .cse.fau.edu/~marty/index.html#RADownload
• centaurialpha.github.io/pireal/index.html
• des.sourceforge.net/