Алгебра Кодда

Реляционные операции

Совместимость отношений

Отношения, совместимые по объединению

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

Отношения называются совместимыми по объединению, если

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

Некоторые отношения не являются совместимыми по объединению, но становятся таковыми после переименования некоторых атрибутов.

Отношения, совместимые по взятию расширенного декартова произведения

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

Операция переименования атрибутов

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

Синтаксис:
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

Проекция

Проекция в реляционной алгебре — унарная операция, которая позволяет получить «вертикальное» подмножество данного отношения, или таблицы, то есть такое подмножество, которое получается выбором специфицированных атрибутов с последующим исключением, если это необходимо, избыточных дубликатов кортежей. Пусть дана таблица <math>T</math> с именами атрибутов <math>A_1,\;A_2,\;\ldots,\;A_n</math>, то есть <math>T(A_1,\;A_2,\;\ldots,\;A_n)</math> и некоторое подмножество множества имен атрибутов <math>\{A_{i_1},\;A_{i_2},\;\ldots,\;A_{i_k}\}</math>. Результатом проекции таблицы по выбранным именам атрибутов называется новая таблица <math>T(A_{i_1},\;A_{i_2},\;\ldots,\;A_{i_k})</math>, полученная из исходной таблицы вычеркиванием атрибутов, не входящих в выбранное множество, с последующим возможным удалением избыточных дубликатов кортежей.

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

Соединение

Операция соединения есть результат последовательного применения операций декартового произведения и выборки. Если в отношениях и имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать.
Синтаксис:
(A TIMES B) WHERE c

Деление

Отношение с заголовком (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

Зависимость реляционных операторов

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

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

Оператор соединения определяется через операторы декартового произведения и выборки следующим образом: (A TIMES B) WHERE X=Y где X и Y атрибуты соответственно отношений A и B с первоначально равными именами.

• Оператор пересечения

Оператор пересечения выражается через вычитание следующим образом: A INTERSECT B = A MINUS (A MINUS B)

• Оператор деления

Оператор деления выражается через операторы вычитания, декартового произведения и проекции следующим образом: A DIVIDEBY B = A[X] MINUS ((A[X] TIMES B) MINUS A)[X]

Примитивные реляционные операторы

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

• Оператор декартового произведения

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

• Оператор проекции

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

• Оператор выборки

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

• Операторы объединения и вычитания

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

Отрывок, характеризующий Алгебра Кодда

Но прежде чем он договорил эти слова, князь Андрей, чувствуя слезы стыда и злобы, подступавшие ему к горлу, уже соскакивал с лошади и бежал к знамени.
– Ребята, вперед! – крикнул он детски пронзительно.
«Вот оно!» думал князь Андрей, схватив древко знамени и с наслаждением слыша свист пуль, очевидно, направленных именно против него. Несколько солдат упало.
– Ура! – закричал князь Андрей, едва удерживая в руках тяжелое знамя, и побежал вперед с несомненной уверенностью, что весь батальон побежит за ним.
Действительно, он пробежал один только несколько шагов. Тронулся один, другой солдат, и весь батальон с криком «ура!» побежал вперед и обогнал его. Унтер офицер батальона, подбежав, взял колебавшееся от тяжести в руках князя Андрея знамя, но тотчас же был убит. Князь Андрей опять схватил знамя и, волоча его за древко, бежал с батальоном. Впереди себя он видел наших артиллеристов, из которых одни дрались, другие бросали пушки и бежали к нему навстречу; он видел и французских пехотных солдат, которые хватали артиллерийских лошадей и поворачивали пушки. Князь Андрей с батальоном уже был в 20 ти шагах от орудий. Он слышал над собою неперестававший свист пуль, и беспрестанно справа и слева от него охали и падали солдаты. Но он не смотрел на них; он вглядывался только в то, что происходило впереди его – на батарее. Он ясно видел уже одну фигуру рыжего артиллериста с сбитым на бок кивером, тянущего с одной стороны банник, тогда как французский солдат тянул банник к себе за другую сторону. Князь Андрей видел уже ясно растерянное и вместе озлобленное выражение лиц этих двух людей, видимо, не понимавших того, что они делали.
«Что они делают? – думал князь Андрей, глядя на них: – зачем не бежит рыжий артиллерист, когда у него нет оружия? Зачем не колет его француз? Не успеет добежать, как француз вспомнит о ружье и заколет его».
Действительно, другой француз, с ружьем на перевес подбежал к борющимся, и участь рыжего артиллериста, всё еще не понимавшего того, что ожидает его, и с торжеством выдернувшего банник, должна была решиться. Но князь Андрей не видал, чем это кончилось. Как бы со всего размаха крепкой палкой кто то из ближайших солдат, как ему показалось, ударил его в голову. Немного это больно было, а главное, неприятно, потому что боль эта развлекала его и мешала ему видеть то, на что он смотрел.
«Что это? я падаю? у меня ноги подкашиваются», подумал он и упал на спину. Он раскрыл глаза, надеясь увидать, чем кончилась борьба французов с артиллеристами, и желая знать, убит или нет рыжий артиллерист, взяты или спасены пушки. Но он ничего не видал. Над ним не было ничего уже, кроме неба – высокого неба, не ясного, но всё таки неизмеримо высокого, с тихо ползущими по нем серыми облаками. «Как тихо, спокойно и торжественно, совсем не так, как я бежал, – подумал князь Андрей, – не так, как мы бежали, кричали и дрались; совсем не так, как с озлобленными и испуганными лицами тащили друг у друга банник француз и артиллерист, – совсем не так ползут облака по этому высокому бесконечному небу. Как же я не видал прежде этого высокого неба? И как я счастлив, я, что узнал его наконец. Да! всё пустое, всё обман, кроме этого бесконечного неба. Ничего, ничего нет, кроме его. Но и того даже нет, ничего нет, кроме тишины, успокоения. И слава Богу!…»


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