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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

$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 ограничиваются набором . $\Pi _{a_{1},\ldots ,a_{n}}(R)$ $a_{1},\ldots ,a_{n}$ $\{a_{1},\ldots ,a_{n}\}$

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

Выбор

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

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

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

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

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

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

Естественное соединение

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

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

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

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

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

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

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

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

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

Распространенные расширения

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

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

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

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

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

Левое внешнее соединение

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

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

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

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

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

(R\бабочка S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\бабочка S))\times \{(\omega ,\dots ,\omega )\})

Правое внешнее соединение

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

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

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

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

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

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

(R\бабочка S)\cup (\{(\omega ,\dots ,\omega )\}\times (S-\pi _{s_{1},s_{2},\dots ,s_{n}}(R\бабочка S)))

Полное внешнее соединение

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

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

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

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

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

Р ⟗ С = ( Р ⟕ С ) ∪ ( Р ⟖ С )

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

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

Агрегация

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

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(_Balance₎ ( Account ). Чтобы найти максимальный баланс всех счетов независимо от филиала, мы могли бы просто написать G _Max(_Balance₎ ( Account ).

Группировка часто записывается как _{Branch_Name} ɣ _Max(_Balance₎ ( Account ). ^[6]

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

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

\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 года, и задолго до этого у него появились расширения в этом направлении, специфичные для конкретных поставщиков.

Реализации

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

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

Даже язык запросов SQL в некоторой степени основан на реляционной алгебре, хотя операнды в SQL ( таблицы ) не являются в точности отношениями , и несколько полезных теорем о реляционной алгебре не выполняются в аналоге SQL (возможно, в ущерб оптимизаторам и/или пользователям). Модель таблицы SQL представляет собой мешок ( мультимножество ), а не множество. Например, выражение является теоремой для реляционной алгебры на множествах, но не для реляционной алгебры на мешках. ^[6] $(R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)$

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

Примечания

^ В Unicode символом соединения является ⨝ (U+2A1D), а символом «галстук-бабочка», который иногда используется вместо него, является ⋈ (U+22C8).
^ В Unicode символ левого внешнего соединения — ⟕ (U+27D5).
^ В Unicode символ правого внешнего соединения — ⟖ (U+27D6).
^ В Unicode символ полного внешнего соединения — ⟗ (U+27D7).

Ссылки

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

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

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

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

RAT Relational Algebra Translator Бесплатное программное обеспечение для преобразования реляционной алгебры в SQL
Видеолекции: Обработка реляционной алгебры — введение в то, как системы баз данных обрабатывают реляционную алгебру
Конспект лекций: Реляционная алгебра – краткое руководство по адаптации SQL-запросов в реляционную алгебру
Реляционная – графическая реализация реляционной алгебры.
Оптимизация запросов Эта статья представляет собой введение в использование реляционной алгебры для оптимизации запросов и включает многочисленные цитаты для более глубокого изучения.
Система реляционной алгебры для Oracle и Microsoft SQL Server
Pireal – экспериментальный образовательный инструмент для работы с реляционной алгеброй
DES – образовательный инструмент для работы с реляционной алгеброй и другими формальными языками
RelaX - Калькулятор реляционной алгебры (программное обеспечение с открытым исходным кодом, доступное как онлайн-сервис без регистрации)
RA: Интерпретатор реляционной алгебры
Перевод SQL в реляционную алгебру