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

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

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

Введение

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

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

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

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

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

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

Кроме того, декартово произведение определяется иначе, чем в набор теория в том смысле, что кортежи считаются "мелкими" для целей операции. То есть декартово произведение набора п-комплекты с набором м-tuples дает набор "сплющенных" (п + м)-кортежи (тогда как базовая теория множеств предписывала бы набор из 2-х кортежей, каждый из которых содержит ппара и м-комплект). Более формально р × 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 }}$

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

Проекция (Π)

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

Примечание: при реализации в SQL стандартная "проекция по умолчанию" возвращает мультимножество вместо набора, и Π прогноз для исключения повторяющихся данных получается путем добавления ОТЧЕТЛИВЫЙ ключевое слово.

Выбор (σ)

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

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

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

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

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

Операторы соединения и подобные операторы

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

Естественное соединение (⋈) - это бинарный оператор который записывается как (р ⋈ S) где р и S находятся связи.^[1] Результатом естественного соединения является набор всех комбинаций кортежей в р и S которые совпадают по своим общим именам атрибутов. Для примера рассмотрим таблицы Наемный рабочий и Отдел и их естественное соединение:

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

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

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

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

${ displaystyle R bowtie S = left {r cup s vert r in R land s in S land { mathit {Fun}} (r cup s) верно}}$

(1)

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

Естественное соединение можно смоделировать с помощью примитивов Кодда следующим образом. Предположим, что c₁,...,c_м являются ли имена атрибутов общими для р и S, р₁,...,р_п являются ли имена атрибутов уникальными для р и s₁,...,s_k являются ли имена атрибутов уникальными для S. Кроме того, предположим, что имена атрибутов Икс₁,...,Икс_м ни в р ни в 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)

θ-соединиться и равняться

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

Машина Модель автомобиля 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 (или theta-join). В θ-join - это бинарный оператор, который записывается как ${ Displaystyle {R bowtie S на theta b}}$ или ${ Displaystyle {R bowtie S на theta v}}$ где а и б имена атрибутов, θ бинарный реляционный оператор в наборе {<, ≤, =, ≠, >, ≥}, υ - постоянная величина, а р и S отношения. Результат этой операции состоит из всех комбинаций кортежей в р и S это удовлетворяет θ. Результат θ-join определяется, только если заголовки S и р не пересекаются, то есть не содержат общего атрибута.

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

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

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

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

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

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

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

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

р ⋉ S = { т : т ∈ р ∧ ∃s ∈ S(Весело (т ∪ s)) }

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

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

р ⋉ S = π_а1,..,ап(р ⋈ S).

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

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

Antijoin (▷)

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

Для примера рассмотрим таблицы Наемный рабочий и Отдел и theirantijoin:

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

р ▷ S = { т : т ∈ р ∧ ¬∃s ∈ S(Весело (т ∪ s)) }

или

р ▷ S = { т : т ∈ р, нет кортежа s из S это удовлетворяет Весело (т ∪ s) }

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

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

р ▷ S = р − р ⋉ S

(5)

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

Деление (÷)

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

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

р ÷ S = { т[а1,...,ап] : т ∈ р ∧ ∀s ∈ S ( (т[а1,...,ап] ∪ s) ∈ р) }

(6)

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

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

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

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

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

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

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

связь:

U := Т − р

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

Е.Г .: Опять же с прогнозами - Т и р должны иметь идентичные имена / заголовки атрибутов.

U := Т - π_{Студент, Задание}(р) // Это дает нам список «чего не хватает».

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

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

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

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

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

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

W : = π_а1,...,ап(р) − V

НАПРИМЕР: W : = π_{Студент}(р) − V.

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

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

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

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

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

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

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

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

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

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

Поскольку в Отдел с DeptName из Финансы или Должностное лицо, ωs входят в результирующее отношение, где кортежи в Наемный рабочий есть DeptName из Финансы или Должностное лицо.

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

${ displaystyle (R bowtie S) cup ((R- pi _ {r_ {1}, r_ {2}, dots, r_ {n}} (R bowtie S)) times {( омега, точки омега) })}$

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

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

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

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

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

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

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

${ Displaystyle (R Bowtie S) чашка ( {( omega, dots, omega) } times (S- pi _ {s_ {1}, s_ {2}, dots, s_ { n}} (R bowtie S)))}$

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

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

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

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

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

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

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

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

В реляционной алгебре до сих пор не введено ничего, что позволяло бы вычисления в областях данных (кроме оценки пропозициональных выражений, включающих равенство). Например, невозможно использовать только представленную до сих пор алгебру, чтобы написать выражение, которое умножало бы числа из двух столбцов, например цена за единицу с количеством, чтобы получить общую цену. Практические языки запросов имеют такие возможности, например SQL SELECT позволяет арифметическим операциям определять новые столбцы в результате ВЫБРАТЬ Цена за единицу * количество В КАЧЕСТВЕ Итоговая цена ИЗ т, и аналогичная возможность предоставляется более явно Учебник D с ПРОДЛЕВАТЬ ключевое слово.^[10] В теории баз данных это называется расширенная проекция.^[11]:213

Агрегация

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

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

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

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

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

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

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

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

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

Однако 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 земля 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)}$. Учитывая определение соединения, это наиболее вероятный случай. Если за перекрестным произведением не следует оператор выбора, мы можем попытаться сдвинуть выборку с более высоких уровней дерева выражения, используя другие правила выбора.

В приведенном выше случае мы нарушаем условие А в условиях B, C и D используя правила разделения для сложных условий выбора, так что ${ Displaystyle А = В клин С клин D}$ и B содержит атрибуты только из р, C содержит атрибуты только из п, и D содержит часть А который содержит атрибуты из обоих р и п. Обратите внимание, что B, C или 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 чашка 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 {где поля в}} A substeq {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 {где}} {a_ {1}, ldots, a_ {n} } substeq {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 = а rangle }}$

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

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

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

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

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

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 чашка 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 (А раз В) чашка (А раз С) = А раз (В чашка С)}$

Реализации

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

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

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

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

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

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

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

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

внешняя ссылка

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

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