Коллектив Авторов - Базы данных: конспект лекций Страница 6

И последнее свойство, которое мы рассмотрим, – это свойство монотонности. Интересно заметить, что при любых условиях все три оператора монотонны;

3) свойство монотонности:

а) для операции выборки: r1 ⊆ r2 ⇒ σ<P> r1 ⇒ σ <P>r2;

б) для операции проекции: r1 ⊆ r2 ⇒ r1[S'] ⊆ r2 [S'];

в) для операции переименования: r1 ⊆ r2 ⇒ ρ<φ>r1 ⊆ ρ <φ>r2;

Понятие монотонности в реляционной алгебре аналогично этому же понятию из алгебры обычной, общей. Поясним: если изначально отношения r1 и r2 были связаны между собой таким образом, что r ⊆ r2, то и после применения любого их трех операторов выборки, проекции или переименования это соотношение сохранится.

Лекция № 5. Реляционная алгебра. Бинарные операции

1. Операции объединения, пересечения, разности

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

1. Результатом операции объединения двух отношений r1(S) и r2(S) будет новое отношение r3(S), состоящее из тех кортежей отношений r1(S) и r2(S), которые принадлежат хотя бы одному из исходных отношений и с такой же схемой отношения.

Таким образом, пересечение двух отношений – это:

r3(S) = r1(S) ∪ r2(S) = {t(S) | t ∈r1 ∪t ∈r2};

Для наглядности, приведем пример в терминах таблиц:

Пусть даны два отношения:

r1(S):

r2(S):

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

r3(S) = r1(S) ∪ r2(S):

Итак, схема отношения S не изменилась, только выросло количество кортежей.

2. Перейдем к рассмотрению следующей бинарной операции – операции пересечения двух отношений. Как мы знаем еще из школьной геометрии, в результирующее отношение войдут только те кортежи исходных отношений, которые присутствуют одновременно в обоих отношениях r1(S) и r2(S) (снова обращаем внимание на одинаковую схему отношения).

Операция пересечения двух отношений будет выглядеть следующим образом:

r4(S) = r1(S) ∩ r2(S) = {t(S) | t ∈ r1 & t ∈ r2};

И снова рассмотрим действие этой операции над отношениями, представленными в виде таблиц:

r1(S):

r2(S):

Согласно определению операции пересечением отношений r1(S) и r2(S) будет новое отношение r4(S), табличное представление которого будет выглядеть следующим образом:

r4(S) = r1(S) ∩ r2(S):

Действительно, если посмотреть на кортежи первого и второго исходного отношений, общий среди них только один: {b, 2}. Он и стал единственным кортежем нового отношения r4(S).

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

r5(S) = r1(S) \ r2(S) = {t(S) | t ∈ r1 & t ∉ r2};

Уже хорошо знакомые нам отношения r1(S) и r2(S), в табличном представлении выглядящие следующим образом:

r1(S):

r2(S):

Мы рассмотрим как операнды в операции пересечения двух отношений. Тогда, следуя данному определению, результирующее отношение r5(S) будет выглядеть следующим образом:

r5(S) = r1(S) \ r2(S):

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

2. Операции декартового произведения и естественного соединения

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

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

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

Если рассмотреть два отношения с различными схемами отношений r1(S1) и r2(S2), то их естественным соединением будет новое отношение r3(S3), которое будет состоять только из тех кортежей операндов, которые совпадают на пересечении схем отношений. Соответственно, схема нового отношения будет больше любой из схем отношений исходных, так как является их соединением, «склеиванием». Кстати, кортежи, одинаковые в двух отношениях-операндах, по которым и происходит это «склеивание», называются соединимыми.

Запишем определение операции естественного соединения на языке формул систем управления базами данных:

r3(S3) = r1(S1) × r2(S2) = {t(S1 ∪S2) | t[S1] ∈ r1 & t(S2) ∈ r2};

Рассмотрим пример, хорошо иллюстрирующий работу естественного соединения, его «склеивание». Пусть дано два отношения r1(S1) и r2(S2), в табличной форме представления соответственно равные:

r1(S1):

r2(S2):

Мы видим, что у этих отношений присутствуют кортежи, совпадающие при пересечении схем S1 и S2 отношений. Перечислим их:

1) кортеж {a, 1} отношения r1(S1) совпадает с кортежем {1, x} отношения r2(S2);

2) кортеж {b, 1} из r1(S1) также совпадает с кортежем {1, x} из r2(S2);

3) кортеж {c, 3} совпадает с кортежем {3, z}.

Значит, при естественном соединении новое отношение r3(S3) получается «склеиванием» именно на этих кортежах. Таким образом, r3(S3) в табличном представлении будет выглядеть следующим образом:

r3(S3) = r1(S1) × r2(S2):

Получается по определению: схема S3 не совпадает ни со схемой S1, ни со схемой S2, мы «склеили» две исходные схемы по пересекающимся кортежам, чтобы получить их естественное соединение.