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

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

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

В процессе развития реляционной теории и практики было предложено несколько новых реляционных операций, например полусоединение (SEMI-JOIN) и полуразность, или анти-полусоединение (ANTI-SEMI-JOIN), CROSS APPLY и OUTER APPLY, транзитивное замыкание (TCLOSE) и др.

Поскольку многие операции выразимы друг через друга, в составе реляционной алгебры можно выделить несколько вариантов базиса (набора операций, через который выразимы все остальные). Наиболее известный и строго определённый базис (алгебра А) предложен Кристофером Дейтом и Хью Дарвеном.

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

Замкнутость реляционной алгебры

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

Операции над одним отношением называются унарными, над двумя отношениями — бинарными, над тремя — тернарными (таковые практически неизвестны).

Пример унарной операции — проекция, пример бинарной операции — объединение.

N-арную реляционную операцию f можно представить функцией, возвращающей отношение и имеющей n отношений в качестве аргументов:

<math>R = f(R_1, R_2,\dots, R_n)</math>

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

<math>R = f(f_1(R_{11},R_{12},\dots),f_2(R_{21},R_{22},\dots),\dots)</math>

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

Ограничения на операции

Некоторые реляционные операции, в частности, операции объединения, пересечения и вычитания, требуют, чтобы отношения имели совпадающие (одинаковые) заголовки (схемы). Это означает, что совпадают количество атрибутов, названия атрибутов и тип (домен) одноимённых атрибутов.

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

Операции реляционной алгебры

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

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

Результатом применения операции переименования атрибутов является отношение с изменёнными именами атрибутов.

Синтаксис:

R RENAME Atr₁, Atr₂, … AS NewAtr₁, NewAtr₂, …

где

R — отношение

Atr₁, Atr₂, … — исходные имена атрибутов

NewAtr₁, NewAtr₂, … — новые имена атрибутов.

Объединение

Отношение с тем же заголовком, что и у совместимых по типу отношений A и B, и телом, состоящим из кортежей, принадлежащих или A, или B, или обоим отношениям.
Синтаксис:

A UNION B

Пересечение

Отношение с тем же заголовком, что и у отношений A и B, и телом, состоящим из кортежей, принадлежащих одновременно обоим отношениям A и B.
Синтаксис:

A INTERSECT B

Вычитание

Отношение с тем же заголовком, что и у совместимых по типу отношений A и B, и телом, состоящим из кортежей, принадлежащих отношению A и не принадлежащих отношению B.
Синтаксис:

A MINUS B

Декартово произведение

Отношение (A₁, A₂, …, A_m, B₁, B₂, …, B_m), заголовок которого является сцеплением заголовков отношений A(A₁, A₂, …, A_m) и B(B₁, B₂, …, B_m), а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B:

(a₁, a₂, …, a_m, b₁, b₂, …, b_m)

таких, что

(a₁, a₂, …, a_m)∈ A,

(b₁, b₂, …, b_m)∈ B.

Синтаксис:

A TIMES B

Выборка (ограничение)

Отношение с тем же заголовком, что и у отношения A, и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие c дают значение ИСТИНА. c представляет собой логическое выражение, в которое могут входить атрибуты отношения A и/или скалярные выражения.
Синтаксис:

A WHERE c

Проекция

При выполнении проекции выделяется «вертикальная» вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов.
Синтаксис:

A[X, Y, …, Z]

или

PROJECT A {x, y, …, z}

Соединение

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

Синтаксис:

(A TIMES B) WHERE P

Деление

Отношение с заголовком (X₁, X₂, …, X_n) и телом, содержащим множество кортежей (x₁, x₂, …, x_n), таких, что для всех кортежей (y₁, y₂, …, y_m) ∈ B в отношении A(X₁, X₂, …, X_n, Y₁, Y₂, …, Y_m) найдется кортеж (x₁, x₂, …, x_n, y₁, y₂, …, y_m).
Синтаксис:

A DIVIDEBY B

Литература

• Грей П. Логика, алгебра и базы данных. — М.: Машиностроение, 1989. — С. 188-213. — 368 с.

Ссылки

• www.citforum.ru/database/dblearn/

Отрывок, характеризующий Реляционная алгебра

В самом счастливом состоянии духа возвращаясь из своего южного путешествия, Пьер исполнил свое давнишнее намерение заехать к своему другу Болконскому, которого он не видал два года.
Богучарово лежало в некрасивой, плоской местности, покрытой полями и срубленными и несрубленными еловыми и березовыми лесами. Барский двор находился на конце прямой, по большой дороге расположенной деревни, за вновь вырытым, полно налитым прудом, с необросшими еще травой берегами, в середине молодого леса, между которым стояло несколько больших сосен.
Барский двор состоял из гумна, надворных построек, конюшень, бани, флигеля и большого каменного дома с полукруглым фронтоном, который еще строился. Вокруг дома был рассажен молодой сад. Ограды и ворота были прочные и новые; под навесом стояли две пожарные трубы и бочка, выкрашенная зеленой краской; дороги были прямые, мосты были крепкие с перилами. На всем лежал отпечаток аккуратности и хозяйственности. Встретившиеся дворовые, на вопрос, где живет князь, указали на небольшой, новый флигелек, стоящий у самого края пруда. Старый дядька князя Андрея, Антон, высадил Пьера из коляски, сказал, что князь дома, и проводил его в чистую, маленькую прихожую.
Пьера поразила скромность маленького, хотя и чистенького домика после тех блестящих условий, в которых последний раз он видел своего друга в Петербурге. Он поспешно вошел в пахнущую еще сосной, не отштукатуренную, маленькую залу и хотел итти дальше, но Антон на цыпочках пробежал вперед и постучался в дверь.
– Ну, что там? – послышался резкий, неприятный голос.
– Гость, – отвечал Антон.
– Проси подождать, – и послышался отодвинутый стул. Пьер быстрыми шагами подошел к двери и столкнулся лицом к лицу с выходившим к нему, нахмуренным и постаревшим, князем Андреем. Пьер обнял его и, подняв очки, целовал его в щеки и близко смотрел на него.
– Вот не ждал, очень рад, – сказал князь Андрей. Пьер ничего не говорил; он удивленно, не спуская глаз, смотрел на своего друга. Его поразила происшедшая перемена в князе Андрее. Слова были ласковы, улыбка была на губах и лице князя Андрея, но взгляд был потухший, мертвый, которому, несмотря на видимое желание, князь Андрей не мог придать радостного и веселого блеска. Не то, что похудел, побледнел, возмужал его друг; но взгляд этот и морщинка на лбу, выражавшие долгое сосредоточение на чем то одном, поражали и отчуждали Пьера, пока он не привык к ним.
При свидании после долгой разлуки, как это всегда бывает, разговор долго не мог остановиться; они спрашивали и отвечали коротко о таких вещах, о которых они сами знали, что надо было говорить долго. Наконец разговор стал понемногу останавливаться на прежде отрывочно сказанном, на вопросах о прошедшей жизни, о планах на будущее, о путешествии Пьера, о его занятиях, о войне и т. д. Та сосредоточенность и убитость, которую заметил Пьер во взгляде князя Андрея, теперь выражалась еще сильнее в улыбке, с которою он слушал Пьера, в особенности тогда, когда Пьер говорил с одушевлением радости о прошедшем или будущем. Как будто князь Андрей и желал бы, но не мог принимать участия в том, что он говорил. Пьер начинал чувствовать, что перед князем Андреем восторженность, мечты, надежды на счастие и на добро не приличны. Ему совестно было высказывать все свои новые, масонские мысли, в особенности подновленные и возбужденные в нем его последним путешествием. Он сдерживал себя, боялся быть наивным; вместе с тем ему неудержимо хотелось поскорей показать своему другу, что он был теперь совсем другой, лучший Пьер, чем тот, который был в Петербурге.
– Я не могу вам сказать, как много я пережил за это время. Я сам бы не узнал себя.
– Да, много, много мы изменились с тех пор, – сказал князь Андрей.
– Ну а вы? – спрашивал Пьер, – какие ваши планы?
– Планы? – иронически повторил князь Андрей. – Мои планы? – повторил он, как бы удивляясь значению такого слова. – Да вот видишь, строюсь, хочу к будущему году переехать совсем…
Пьер молча, пристально вглядывался в состаревшееся лицо (князя) Андрея.
– Нет, я спрашиваю, – сказал Пьер, – но князь Андрей перебил его:
– Да что про меня говорить…. расскажи же, расскажи про свое путешествие, про всё, что ты там наделал в своих именьях?
Пьер стал рассказывать о том, что он сделал в своих имениях, стараясь как можно более скрыть свое участие в улучшениях, сделанных им. Князь Андрей несколько раз подсказывал Пьеру вперед то, что он рассказывал, как будто всё то, что сделал Пьер, была давно известная история, и слушал не только не с интересом, но даже как будто стыдясь за то, что рассказывал Пьер.
Пьеру стало неловко и даже тяжело в обществе своего друга. Он замолчал.
– А вот что, душа моя, – сказал князь Андрей, которому очевидно было тоже тяжело и стеснительно с гостем, – я здесь на биваках, и приехал только посмотреть. Я нынче еду опять к сестре. Я тебя познакомлю с ними. Да ты, кажется, знаком, – сказал он, очевидно занимая гостя, с которым он не чувствовал теперь ничего общего. – Мы поедем после обеда. А теперь хочешь посмотреть мою усадьбу? – Они вышли и проходили до обеда, разговаривая о политических новостях и общих знакомых, как люди мало близкие друг к другу. С некоторым оживлением и интересом князь Андрей говорил только об устраиваемой им новой усадьбе и постройке, но и тут в середине разговора, на подмостках, когда князь Андрей описывал Пьеру будущее расположение дома, он вдруг остановился. – Впрочем тут нет ничего интересного, пойдем обедать и поедем. – За обедом зашел разговор о женитьбе Пьера.
– Я очень удивился, когда услышал об этом, – сказал князь Андрей.
Пьер покраснел так же, как он краснел всегда при этом, и торопливо сказал:
– Я вам расскажу когда нибудь, как это всё случилось. Но вы знаете, что всё это кончено и навсегда.
– Навсегда? – сказал князь Андрей. – Навсегда ничего не бывает.
– Но вы знаете, как это всё кончилось? Слышали про дуэль?
– Да, ты прошел и через это.