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

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

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

Введение [ править ]

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

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

Установить операторы [ править ]

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

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

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

Кроме того, декартово произведение определяется иначе, чем в теории множеств, в том смысле, что кортежи считаются «мелкими» для целей операции. То есть декартово произведение набора из n наборов на набор из m наборов дает набор «уплощенных» ( n  +  m ) наборов (тогда как базовая теория множеств предписывала бы набор из двух наборов, каждый содержащий 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 × S | = | R | × | S |,

Проекция ( Π ) [ править ]

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

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

Выбор ( σ ) [ править ]

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

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

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

Переименования является унарная операция записывается в виде , где результат идентичен R за исключением того, что б атрибута во всех кортежей переименован к в атрибуте. Это просто используется для переименования атрибута отношения или самого отношения.${\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 - отношения . ^[2] Результатом естественного соединения является набор всех комбинаций кортежей в R и S , которые равны по своим общим именам атрибутов. В качестве примера рассмотрим таблицы Employee и Dept и их естественное соединение:

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

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

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

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

${\displaystyle R\bowtie S=\left\{r\cup s\ \vert \ r\in R\ \land \ s\in S\ \land \ {\mathit {Fun}}(r\cup s)\right\}}$

( 1 )

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

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

${\displaystyle T=\rho _{x_{1}/c_{1},\ldots ,x_{m}/c_{m}}(S)=\rho _{x_{1}/c_{1}}(\rho _{x_{2}/c_{2}}(\ldots \rho _{x_{m}/c_{m}}(S)\ldots ))}$

( 2 )

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

${\displaystyle P=\sigma _{c_{1}=x_{1},\ldots ,c_{m}=x_{m}}(R\times T)=\sigma _{c_{1}=x_{1}}(\sigma _{c_{2}=x_{2}}(\ldots \sigma _{c_{m}=x_{m}}(R\times T)\ldots ))}$

( 3 )

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

${\displaystyle U=\Pi _{r_{1},\ldots ,r_{n},c_{1},\ldots ,c_{m},s_{1},\ldots ,s_{k}}(P)}$

( 4 )

θ -соединение и равное соединение [ править ]

Рассмотрим таблицы Car и Boat, в которых перечислены модели автомобилей и лодок и их цены. Предположим, покупатель хочет купить машину и лодку, но не хочет тратить на лодку больше денег, чем на машину. & Thetas ; -join (⋈ & _thetas ; ) на предикате CarPrice ≥ BoatPrice производит уплощенные пары строк , которые удовлетворяют предикат. При использовании условия, в котором атрибуты равны, например Цена, тогда условие может быть указано как Цена = Цена или, как вариант, само ( Цена ).

Машина Модель автомобиля CarPrice CarA 20 000 CarB 30 000 CarC 50 000

Лодка ЛодкаМодель ЛодкаЦена Лодка1 10 000 Лодка2 40 000 Лодка3 60 000

${\displaystyle {Car\bowtie Boat \atop \scriptstyle CarPrice\geq BoatPrice}}$ Модель автомобиля CarPrice ЛодкаМодель ЛодкаЦена CarA 20 000 Лодка1 10 000 CarB 30 000 Лодка1 10 000 CarC 50 000 Лодка1 10 000 CarC 50 000 Лодка2 40 000

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

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

R ⋈ _θ S = σ _θ ( R × S )

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

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

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

Semijoin (⋉) (⋊) [ править ]

Левое полусоединение - это соединение, аналогичное естественному соединению, и записывается как R ⋉ S, где R и S - отношения . ^[3] Результатом является набор всех кортежей в R, для которых есть кортеж в S , равный по их общим именам атрибутов. Отличие от естественного соединения в том, что другие столбцы S не появляются. Например, рассмотрим таблицы Employee и Dept и их полусоединение:

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

R ⋉ S = { t  : t ∈ R ∧ ∃ s ∈ S ( Fun ( t ∪ s ))}

где Fun ( r ) такое же, как в определении естественного соединения.

Полусоединение можно смоделировать с помощью естественного соединения следующим образом. Если a ₁ , ..., a _n - имена атрибутов R , то

R ⋉ S = π _{a 1 , .., a n} ( R ⋈ S ).

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

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

Antijoin (▷) [ править ]

Антисоединение, записанное как R ▷ S, где R и S - отношения , похоже на полусоединение, но результатом антисоединения являются только те кортежи в R, для которых нет кортежей в S , равных по их общим именам атрибутов. ^[5]

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

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

R ▷ S = { t  : t ∈ R ∧ ¬∃ s ∈ S ( Fun ( t ∪ s ))}

или же

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

где Fun ( t ∪ s ) такое же, как в определении естественного соединения.

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

R ▷ S = R  -  R ⋉ S

( 5 )

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

Деление (÷) [ править ]

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

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

R ÷ S = { t [ a 1 , ..., a n ]: t ∈ R ∧ ∀ s ∈ S (( t [ a 1 , ..., a n ] ∪ s ) ∈ R )}

( 6 )

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

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

T  : = π _{a 1 , ..., a n} ( R ) × S

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

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

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

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

отношение :

U  : = T - R

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

EG: Опять же с прогнозами - T и R должны иметь одинаковые имена / заголовки атрибутов.

U  : = T - π _{Student, Task} ( R ) // Это дает нам список «чего не хватает».

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

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

V  : = π _{a 1 , ..., a n} ( U )

EG: Проект U вплоть до рассматриваемого атрибута (ов) (Студент)

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

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

W  : = π _{a 1 , ..., a n} ( R ) - V

EG: W  : = π _{студент} ( R ) - V .

Общие расширения [ править ]

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

Внешние соединения [ править ]

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

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

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

Левое внешнее соединение (⟕) [ править ]

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

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

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

Поскольку в Dept нет кортежей с именем DeptName of Finance или Executive , в результирующем отношении встречаются ω, где кортежи в Employee имеют 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 . ^[9] Результат правого внешнего соединения представляет собой набор из всех комбинаций кортежей в R и S , которые равны их общих имен атрибутов, в дополнение к кортежей в S , которые не имеют совпадающие кортежи в R .

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

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

Поскольку неты кортежей Работник с DEPTNAME из производства , omega ; s происходит во имени и EmpId атрибутов результирующего отношения , где кортежи в МЭИ были DEPTNAME из производства .

Пусть 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 - отношения . ^[10] Результатом полного внешнего соединения является набор всех комбинаций кортежей в R и S , которые равны по своим общим именам атрибутов, в дополнение к кортежам в S , у которых нет совпадающих кортежей в R, и кортежам в R, которые имеют нет совпадающих кортежей в S в их общих именах атрибутов.

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

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

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

R ⟗ S = ( R ⟕ S ) ∪ ( R ⟖ S )

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

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

Агрегация [ править ]

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

${\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, являются атрибутами группировки, которые действуют как предложение «group by» в SQL. Затем к отдельным атрибутам применяется произвольное количество функций агрегирования. Операция применяется к произвольному отношению r . Атрибуты группировки являются необязательными, и если они не указаны, функции агрегирования применяются ко всему отношению, к которому применяется операция.

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

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

Переходное закрытие [ править ]

Хотя реляционная алгебра кажется достаточно мощной для большинства практических целей, есть несколько простых и естественных операторов отношений, которые не могут быть выражены с помощью реляционной алгебры. Один из них - транзитивное замыкание бинарного отношения. Учитывая , область 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 ⁺ . Это может быть доказано , используя тот факт , что, учитывая относительное выражение Е , для которой он утверждает , что Е ( R ) = R ⁺ , где R представляет собой переменный, всегда можно найти экземпляр г из R (и соответствующая область д ) такое, что E ( r ) ≠ r ⁺ . ^[14]

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

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

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

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

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

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

Выбор [ править ]

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

Основные свойства выбора [ править ]

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

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 , и эта новаторская работа была одобрена многими авторитетными специалистами ^[15] как показывающая способ превратить идею Кодда в полезный язык. Business System 12 была недолговечной реляционной СУБД, которая последовала примеру ISBL.

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

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

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

Внешние ссылки [ править ]

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

• КРЫСА. Программный транслятор реляционной алгебры в SQL
• Видео лекций: Обработка реляционной алгебры - введение в то, как системы баз данных обрабатывают реляционную алгебру
• Лекционные заметки: реляционная алгебра - краткое руководство по адаптации SQL-запросов в реляционную алгебру
• Реляционная - графическая реализация реляционной алгебры.
• Оптимизация запросов Эта статья представляет собой введение в использование реляционной алгебры для оптимизации запросов и включает многочисленные ссылки для более глубокого изучения.
• Система реляционной алгебры для Oracle и Microsoft SQL Server
• Pireal - экспериментальный обучающий инструмент для работы с реляционной алгеброй.
• DES - образовательный инструмент для работы с реляционной алгеброй и другими формальными языками
• RelaX - Калькулятор реляционной алгебры (программное обеспечение с открытым исходным кодом, доступное в виде онлайн-сервиса без регистрации)
• РА: интерпретатор реляционной алгебры
• Перевод SQL в реляционную алгебру