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

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

В теории баз данных реляционная алгебра — это теория, которая использует алгебраические структуры для моделирования данных и определения запросов к ним с хорошо обоснованной семантикой . Теория была представлена ​​Эдгаром Ф. Коддом .

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

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

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

Могут быть включены и другие, более продвинутые операторы, где включение или исключение определенных операторов приводит к созданию семейства алгебр.

Введение

Реляционной алгебре уделялось мало внимания за пределами чистой математики до публикации реляционной модели данных Э. Ф. Кодда в 1970 году. Кодд предложил такую ​​алгебру в качестве основы для языков запросов к базам данных. (См. раздел «Реализации».)

Реляционная алгебра оперирует однородными наборами кортежей , где мы обычно интерпретируем m как количество строк в таблице, а n как количество столбцов. Все записи в каждом столбце имеют один и тот же тип. Пять примитивных операторов алгебры Кодда — это выбор , проекция , декартово произведение (также называемое перекрестным произведением или перекрестным соединением ), объединение множеств и разность множеств . ${\displaystyle S=\{(s_{j1},s_{j2},...s_{jn})|j\in 1...m\}}$

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

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

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

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

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

$${\displaystyle R\times S:=\{(r_{1},r_{2},\dots ,r_{n},s_{1},s_{2},\dots ,s_{m})|(r_{1},r_{2},\dots ,r_{n})\in R,(s_{1},s_{2},\dots ,s_{m})\in S\}}$$

Мощность декартова произведения есть произведение мощностей его факторов, т. е. | Р × С | = | р | × | С |.

Проекция ( Π )

Проекция — это унарная операция , записанная как где — набор имен атрибутов. Результат такого проектирования определяется как набор , который получается, когда все кортежи в R ограничены набором . ${\displaystyle \Pi _{a_{1},\ldots ,a_{n}}(R)}$ ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$

Примечание. При реализации в стандарте SQL «проекция по умолчанию» возвращает мультимножество вместо набора, а проекция Π для устранения повторяющихся данных получается путем добавления ключевого DISTINCTслова .

Выбор ( σ )

Обобщенный выбор — это унарная операция, записанная следующим образом: где φ — формула высказывания , состоящая из атомов , разрешенных при нормальном выборе , и логических операторов ( и ), ( или ) и ( отрицание ). Этот выбор выбирает все те кортежи в R , для которых выполняется φ . ${\displaystyle \sigma _{\varphi }(R)}$ ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$

Чтобы получить список всех друзей или деловых партнеров в адресной книге, выбор можно записать как . Результатом будет отношение, содержащее каждый атрибут каждой уникальной записи, где isFriend имеет значение true или isBusinessContact имеет значение true. ${\displaystyle \sigma _{{\text{isFriend = true}}\,\lor \,{\text{isBusinessContact = true}}}({\text{addressBook}})}$

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

Переименование — это унарная операция, записанная так , что результат идентичен R , за исключением того, что атрибут b во всех кортежах переименовывается в атрибут a . Это просто используется для переименования атрибута отношения или самого отношения. ${\displaystyle \rho _{a/b}(R)}$

Чтобы переименовать атрибут «isFriend» в «isBusinessContact» в отношении, можно использовать. ${\displaystyle \rho _{\text{isBusinessContact / isFriend}}({\text{addressBook}})}$

Существует также обозначение, где R переименовывается в x , а атрибуты переименовываются в . ^[1] ${\displaystyle \rho _{x(A_{1},\ldots ,A_{n})}(R)}$ ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$ ${\displaystyle \{A_{1},\ldots ,A_{n}\}}$

Соединения и подобные им операторы

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

Естественное соединение (⋈) — это бинарный оператор , который записывается как ( R ⋈ S ), где R и S — отношения . ^[a] Результатом естественного соединения является набор всех комбинаций кортежей в R и S , которые равны по своим общим именам атрибутов. В качестве примера рассмотрим таблицы «Сотрудник» и «Отдел» и их ^{естественное соединение :}

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

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

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

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

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

Естественное соединение можно смоделировать с помощью примитивов Кодда следующим образом. Предположим, что c ₁ ,..., cm — имена атрибутов, общие для R и S , r ₁ ,..., r _n — имена атрибутов, уникальные для _R , а s ₁ ,..., sk _— атрибут имена, уникальные для S . Кроме того, предположим, что имена атрибутов x ₁ ,..., x _m не находятся ни в R , ни в S . На первом этапе можно переименовать общие имена атрибутов в S :

Затем мы берем декартово произведение и выбираем кортежи, которые необходимо соединить:

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

θ -соединение и равносоединение

Рассмотрим таблицы «Автомобиль» и «Лодка» , в которых перечислены модели автомобилей и лодок и соответствующие цены. Предположим, клиентка хочет купить машину и лодку, но не хочет тратить на лодку больше денег, чем на машину. θ -соединение (⋈ _θ ) по предикату CarPrice ≥ BoatPrice создает сглаженные пары строк, которые удовлетворяют предикату. При использовании условия, в котором атрибуты равны, например Цена, условие может быть указано как Цена = Цена или, альтернативно, ( Цена ).

Чтобы объединить кортежи из двух отношений, где условием объединения является не просто равенство общих атрибутов, удобно иметь более общую форму оператора соединения, которая представляет собой θ - соединение (или тета-соединение). θ -join — это бинарный оператор, который записывается как или где a и b — имена атрибутов, θ — бинарный реляционный оператор в множестве {<, ≤, =, ≠, >, ≥ }, υ — константа значения, а R и S — отношения. Результатом этой операции являются все комбинации кортежей из R и S , удовлетворяющие θ . Результат θ -соединения определяется только в том случае, если заголовки S и R не пересекаются, то есть не содержат общего атрибута. ${\displaystyle {R\ \bowtie \ S \atop a\ \theta \ b}}$ ${\displaystyle {R\ \bowtie \ S \atop a\ \theta \ v}}$

Таким образом, моделирование этой операции в основных операциях выглядит следующим образом:

р ⋈ _θ S знак равно σ _θ ( р × S )

Если оператор θ является оператором равенства (=), то это соединение также называется эквисоединением .

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

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

Полусоединение (⋉ и ⋊)

Левое полусоединение — это соединение, аналогичное естественному соединению и записываемое как где и являются отношениями . ^[b] Результатом является набор всех кортежей, в которых есть кортеж, равный по именам общих атрибутов. Отличие от естественного соединения состоит в том, что другие столбцы не отображаются. Например, рассмотрим таблицы «Сотрудник» и ^« Отдел» и их ^{полусоединение :} ${\displaystyle R\ltimes S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

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

${\displaystyle R\ltimes S=\{t:t\in R\land \exists s\in S(\operatorname {Fun} (t\cup s))\}}$

где соответствует определению естественного соединения. ${\displaystyle \operatorname {Fun} (r)}$

Полусоединение можно смоделировать с использованием естественного соединения следующим образом. Если являются именами атрибутов , то ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle R}$

${\displaystyle R\ltimes S=\Pi _{a_{1},\ldots ,a_{n}}(R\bowtie S).}$

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

В статье Кодда 1970 года полусоединение называется ограничением. ^[2]

Антисоединение (▷)

Антисоединение, записываемое как R ▷ S , где R и S — отношения , ^[c] похоже на полусоединение, но результатом антисоединения являются только те кортежи в R, для которых нет кортежа в S , равного в их общих точках. имена атрибутов. ^{[ нужна цитата ]}

В качестве примера рассмотрим таблицы «Сотрудник» и «Отдел» и их антисоединение:

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

р ▷ S знак равно { т  : т ∈ R ∧ ¬∃ s ∈ S ( Fun ( т ∪ s )) }

или

R ▷ S = { t  : t ∈ R , не существует кортежа s из S , который удовлетворяет условию Fun ( t ∪ s ) }

где Fun ( t ∪ s ) соответствует определению естественного соединения.

Антисоединение также можно определить как дополнение полусоединения следующим образом:

Учитывая это, анти-соединение иногда называют анти-полусоединением, а оператор анти-соединения иногда записывается как символ полусоединения с чертой над ним вместо ▷.

Дивизион (÷)

Деление — это бинарная операция, которая записывается как R ÷ S. Деление не реализовано непосредственно в SQL. Результат состоит из ограничений кортежей в R на имена атрибутов, уникальные для R , т. е. в заголовке R , но не в заголовке S , для чего считается, что все их комбинации с кортежами в S присутствуют в R. Для примера см. таблицы Completed , DBProject и их разделение:

Если DBProject содержит все задачи проекта «База данных», то результат приведенного выше разделения содержит ровно тех студентов, которые выполнили обе задачи проекта «База данных». Более формально семантика деления определяется следующим образом:

где { a ₁ ,..., a _n } — набор имен атрибутов, уникальных для _R , а t [ a ₁ ,..., an ] — ограничение t на этот набор. Обычно требуется, чтобы имена атрибутов в заголовке S были подмножеством имен атрибутов R , поскольку в противном случае результат операции всегда будет пустым.

Моделирование деления с основными операциями происходит следующим образом. Мы предполагаем, что a ₁ ,..., an _— имена атрибутов, уникальные для R , а b ₁ ,..., b _m — имена атрибутов S . На первом этапе мы проецируем R на его уникальные имена атрибутов и создаем все комбинации с кортежами в S :

Т  := π _{а 1 ,..., а п} ( р ) × S

В предыдущем примере T будет представлять таблицу, в которой каждый студент (поскольку студент является уникальным ключом/атрибутом таблицы «Завершено») сочетается с каждой заданной задачей. Так, например, у Юджина в T будет две строки: Юджин → База данных1 и Юджин → База данных2.

ЭГ: Во-первых, давайте представим, что у «Завершено» есть третий атрибут, называемый «оценка». Это нежелательный багаж, поэтому мы всегда должны его проецировать. Фактически, на этом этапе мы также можем удалить «Задачу» из R; умножение возвращает его обратно.

T  := π _Student ( R ) × S // Это дает нам все возможные желаемые комбинации, включая те, которые на самом деле не существуют в R, и исключая другие (например, Фред | компилятор1, который не является желаемой комбинацией)

На следующем шаге мы вычитаем R из T

отношение :

У  := Т - Р

В U у нас есть возможные комбинации, которые «могли» быть в R , но не были.

ЭГ: И снова про проекции: T и R должны иметь одинаковые имена/заголовки атрибутов.

U  := T − π _Student,Task ( R ) // Это дает нам список того, чего не хватает.

Итак, если мы теперь возьмем проекцию имен атрибутов, уникальных для R

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

V  := π _{а 1 ,..., а п} ( U )

ПРИМЕР: Проект U вплоть до рассматриваемых атрибутов (Студент)

V  := π _{Студент} ( U )

Итак, что осталось сделать, так это взять проекцию R на его уникальные имена атрибутов и вычесть их из V :

W  := π _{а 1 ,..., а п} ( р ) - V

Например: W  := π _{Студент} ( R ) − V .

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

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

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

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

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

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

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

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

В качестве примера рассмотрим таблицы «Сотрудник» и «Отдел» и их левое внешнее соединение:

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

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

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

${\displaystyle (R\bowtie S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\bowtie S))\times \{(\omega ,\dots ,\omega )\})}$

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

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

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

Например, рассмотрим таблицы «Сотрудник» и «Отдел» и их правое внешнее соединение:

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

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

Пусть s ₁ , s ₂ , ..., s _n — атрибуты отношения S и пусть {( ω , ..., ω )} — одноэлементное отношение к атрибутам, уникальным для отношения R (те, которые не являются атрибутами S ). Затем, как и в случае с левым внешним соединением, правое внешнее соединение можно смоделировать с использованием естественного соединения следующим образом:

${\displaystyle (R\bowtie S)\cup (\{(\omega ,\dots ,\omega )\}\times (S-\pi _{s_{1},s_{2},\dots ,s_{n}}(R\bowtie S)))}$

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

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

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

В качестве примера рассмотрим таблицы «Сотрудник» и «Отдел» и их полное внешнее соединение:

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

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

р ⟗ S знак равно ( р ⟕ S ) ∪ ( р ⟖ S )

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

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

Агрегация

Более того, вычисление различных функций над столбцом, например суммирование его элементов, также невозможно с использованием введенной до сих пор реляционной алгебры. В большинство систем реляционных баз данных включены пять агрегатных функций . Этими операциями являются сумма, счет, среднее, максимум и минимум. В реляционной алгебре операция агрегирования над схемой ( A ₁ , A ₂ , ... An ) записывается следующим образом _:

${\displaystyle G_{1},G_{2},\ldots ,G_{m}\ g_{f_{1}({A_{1}}'),f_{2}({A_{2}}'),\ldots ,f_{k}({A_{k}}')}\ (r)}$

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

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

Предположим, что у нас есть таблица с именем Account с тремя столбцами: Account_Number, Branch_Name и Balance . Мы хотим найти максимальный баланс каждой ветви. Это достигается с помощью _{Branch_Name} G _{Max( Balance )} ( Account ). Чтобы найти наибольший баланс всех счетов независимо от филиала, мы могли бы просто написать G _{Max( Balance )} ( Account ).

Вместо этого группировку часто записывают как _{Branch_Name} ɣ _{Max( Balance )} ( Account ). ^[6]

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

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

${\displaystyle \forall x\forall y\forall z\left((x,y)\in R^{+}\wedge (y,z)\in R^{+}\Rightarrow (x,z)\in R^{+}\right)}$

Это можно доказать, используя тот факт, что не существует выражения реляционной алгебры E ( R ), принимающего R в качестве переменного аргумента, производящего R ⁺ . ^[7]

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

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

Два возможных плана запроса для треугольного запроса R(A, B) ⋈ S(B, C) ⋈ T(A, C) ; первый сначала соединяет S и T и соединяет результат с R , второй сначала соединяет R и S и соединяет результат с T

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

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

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

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

Вот набор правил, которые можно использовать при таких преобразованиях.

Выбор

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

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

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

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

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

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

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

Выбор и перекрестное произведение

Перекрестное произведение — самый затратный оператор для оценки. Если входные отношения содержат N и M строк, результат будет содержать строки. Поэтому важно уменьшить размер обоих операндов перед применением оператора перекрестного произведения. ${\displaystyle NM}$

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

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

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

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

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

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

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

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

${\displaystyle \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}\}}$

Проекция

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

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

${\displaystyle \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}\}}$

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

Проекция дистрибутивна по объединению множеств.

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

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

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

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

и

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

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

где b предполагается отличным от b' .

Переименовать

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

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

1. ${\displaystyle \rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!}$
2. ${\displaystyle \rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R))\,\!}$

Переименование и установка операторов

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

1. ${\displaystyle \rho _{a/b}(R\setminus P)=\rho _{a/b}(R)\setminus \rho _{a/b}(P)}$
2. ${\displaystyle \rho _{a/b}(R\cup P)=\rho _{a/b}(R)\cup \rho _{a/b}(P)}$
3. ${\displaystyle \rho _{a/b}(R\cap P)=\rho _{a/b}(R)\cap \rho _{a/b}(P)}$

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

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

1. ${\displaystyle (A\times B)\cup (A\times C)=A\times (B\cup C)}$

Реализации

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

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

Даже язык запросов SQL во многом основан на реляционной алгебре, хотя операнды в SQL ( таблицы ) не являются в точности отношениями , и некоторые полезные теоремы о реляционной алгебре не выполняются в аналоге SQL (возможно, в ущерб оптимизаторам и/или или пользователей). Модель таблицы SQL представляет собой пакет ( мультмножество ), а не набор. Например, это выражение является теоремой для реляционной алгебры на множествах, но не для реляционной алгебры на мешках; описание реляционной алгебры на мешках см. в главе 5 «Полного» учебника Гарсиа-Молины , Ульмана и Видома . ^[6] ${\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}$

Смотрите также

• Декартово произведение
• D4 (язык программирования) (реализация D)
• База данных
• Логика родственников
• Объектно-ролевое моделирование
• Проекция (математика)
• Проекция (реляционная алгебра)
• Проекция (теория множеств)
• Связь
• Связь (база данных)
• Алгебра отношений
• Композиция отношений
• Построение отношений
• Реляционное исчисление
• Реляционная база данных
• Реляционная модель
• Теория отношений
• Триадное отношение
• Кортежное реляционное исчисление
• SQL
• Журнал данных
• Теорема Кодда

Примечания

1. В Юникоде символ галстука-бабочки — ⋈ (U+22C8).
2. В Юникоде символ ltimes — ⋉ (U+22C9). Символ rtimes: ⋊ (U+22CA).
3. В Юникоде символ антисоединения — ▷ (U+25B7).
4. В Юникоде символ левого внешнего соединения — ⟕ (U+27D5).
5. В Юникоде символ правого внешнего соединения — ⟖ (U+27D6).
6. В Юникоде символ полного внешнего соединения — ⟗ (U+27D7).

Рекомендации

1. Зильбершац, Авраам; Генри Ф. Корт; С. Сударшан (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк. п. 56. ИСБН 978-0-07-802215-9. ОСЛК  1080554130.{{cite book}}: CS1 maint: location missing publisher (link)
2. Кодд, EF (июнь 1970 г.). «Реляционная модель данных для больших общих банков данных». Коммуникации АКМ . 13 (6): 377–387. дои : 10.1145/362384.362685 . S2CID  207549016.
3. М. Тамер Озсу; Патрик Вальдурье (2011). Принципы систем распределенных баз данных (3-е изд.). Спрингер. п. 46. ​​ИСБН 978-1-4419-8833-1.
4. Патрик О'Нил; Элизабет О'Нил (2001). База данных: принципы, программирование и производительность, второе издание. Морган Кауфманн. п. 120. ИСБН 978-1-55860-438-4.
5. Дата CJ (2011). SQL и реляционная теория: как писать точный код SQL. O'Reilly Media, Inc., стр. 133–135. ISBN 978-1-4493-1974-8.
6. Гектор Гарсиа-Молина; Джеффри Д. Уллман; Дженнифер Видом (2009). Системы баз данных: полная книга (2-е изд.). Пирсон Прентис Холл. ISBN 978-0-13-187325-4.
7. Ахо, Альфред В.; Джеффри Д. Уллман (1979). «Универсальность языков поиска данных». Материалы 6-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования : 110–119. дои : 10.1145/567752.567763 . S2CID  3242505.
8. Дата CJ. «Эдгар Ф. Кодд - лауреат премии А. М. Тьюринга». amturing.acm.org . Проверено 27 декабря 2020 г.

дальнейшее чтение

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

• Имелинский, Т. ; Липски, В. (1984). «Реляционная модель данных и цилиндрические алгебры». Журнал компьютерных и системных наук . 28 : 80–102. дои : 10.1016/0022-0000(84)90077-1 .(Для связи с цилиндрическими алгебрами ).

Внешние ссылки

• КРЫСА. Программный транслятор реляционной алгебры в SQL
• Видеолекции: Обработка реляционной алгебры. Введение в то, как системы баз данных обрабатывают реляционную алгебру.
• Конспект лекций: Реляционная алгебра – краткое руководство по адаптации SQL-запросов к реляционной алгебре.
• Реляционная - графическая реализация реляционной алгебры.
• Оптимизация запросов (Страница удалена; Ближайшие альтернативы: Standford Query Optimization 2, Исследование Microsoft «Оптимизация запросов в реляционных системах», Стэнфордская статья: Оптимизация запросов). Эта статья представляет собой введение в использование реляционной алгебры при оптимизации запросов и включает многочисленные цитаты для получения дополнительной информации. углубленное изучение.
• Система реляционной алгебры для Oracle и Microsoft SQL Server
• Pireal — экспериментальный образовательный инструмент для работы с реляционной алгеброй.
• DES – образовательный инструмент для работы с реляционной алгеброй и другими формальными языками.
• RelaX - Калькулятор реляционной алгебры (программное обеспечение с открытым исходным кодом, доступное в виде онлайн-сервиса без регистрации)
• РА: интерпретатор реляционной алгебры
• Перевод SQL в реляционную алгебру