Автор работы: Пользователь скрыл имя, 06 Января 2014 в 21:03, лекция
Системы управления базами данных (СУБД) – это специализированные программные продукты, позволяющие:
1) постоянно хранить сколь угодно большие (но не бесконечные) объемы данных;
2) извлекать и изменять эти хранящиеся данные в том или ином аспекте, используя при этом так называемые запросы;
И последнее свойство, которое мы рассмотрим, – это свойство монотонности. Интересно заметить, что при любых условиях все три оператора монотонны;
3) свойство монотонности:
а) для операции выборки: r 1 ⊆ r 2 ⇒ σ <P > r 1 ⇒ σ <P >r 2;
б) для операции проекции: r 1 ⊆ r 2 ⇒ r 1[S' ] ⊆ r 2 [S' ];
в) для операции переименования: r 1 ⊆ r 2 ⇒ ρ <φ >r 1 ⊆ ρ <φ >r 2;
Понятие монотонности в реляционной алгебре аналогично этому же понятию из алгебры обычной, общей. Поясним: если изначально отношения r 1 и r 2 были связаны между собой таким образом, что r ⊆ r 2, то и после применения любого их трех операторов выборки, проекции или переименования это соотношение сохранится.
У любых операций есть свои правила применимости, которые необходимо соблюдать, чтобы выражения и действия не теряли смысла. Бинарные теоретико-множественные операции объединения, пересечений и разности могут быть применены только к двум отношениям обязательно с одной и той же схемой отношения. Результатом таких бинарных операций будут являться отношения, состоящие из кортежей, удовлетворяющих условиям операций, но с такой же схемой отношения, как и у операндов.
1. Результатом операции объединения двух отношений r 1(S ) и r 2(S ) будет новое отношение r 3(S ), состоящее из тех кортежей отношений r 1(S ) и r 2(S ), которые принадлежат хотя бы одному из исходных отношений и с такой же схемой отношения.
Таким образом, пересечение двух отношений – это:
r 3(S ) = r 1(S ) ∪ r 2(S ) = {t (S ) | t ∈r 1 ∪t ∈r 2};
Для наглядности, приведем пример в терминах таблиц:
Пусть даны два отношения:
r 1(S ):
r 2(S ):
Мы видим, что схемы первого и второго отношений одинаковы, только имеют различной количество кортежей. Объединением этих двух отношений будет отношение r 3(S ), которому будет соответствовать следующая таблица:
r3 (S ) = r 1(S ) ∪ r 2(S ):
Итак, схема отношения S не изменилась, только выросло количество кортежей.
2. Перейдем к рассмотрению следующей бинарной операции – операции пересечения двух отношений. Как мы знаем еще из школьной геометрии, в результирующее отношение войдут только те кортежи исходных отношений, которые присутствуют одновременно в обоих отношениях r 1(S ) и r 2(S ) (снова обращаем внимание на одинаковую схему отношения).
Операция пересечения двух отношений будет выглядеть следующим образом:
r 4(S ) = r 1(S ) ∩ r 2(S ) = {t (S ) | t ∈ r 1 & t ∈ r 2};
И снова рассмотрим действие этой операции над отношениями, представленными в виде таблиц:
r 1(S ):
r 2(S ):
Согласно определению операции пересечением отношений r 1(S ) и r 2(S ) будет новое отношение r 4(S ), табличное представление которого будет выглядеть следующим образом:
r 4(S ) = r 1(S ) ∩ r 2(S ):
Действительно, если посмотреть на кортежи первого и второго исходного отношений, общий среди них только один: {b, 2}. Он и стал единственным кортежем нового отношения r 4(S ).
3. Операция разности двух отношений определяется аналогичным с предыдущими операциями образом. Отношения-операнды, так же, как и в предыдущих операциях, должны иметь одинаковые схемы отношения, тогда в результирующее отношение войдут все те кортежи первого отношения, которых нет во втором, т. е.:
r5(S) = r1(S) \ r2(S) = {t(S) | t ∈ r1 & t ∉ r2};
Уже хорошо знакомые нам отношения r 1(S ) и r 2(S ), в табличном представлении выглядящие следующим образом:
r 1(S ):
r 2(S ):
Мы рассмотрим как операнды в операции пересечения двух отношений. Тогда, следуя данному определению, результирующее отношение r5 (S ) будет выглядеть следующим образом:
r 5(S ) = r 1(S ) \ r 2(S ):
Рассмотренные бинарные операции являются базовыми, на них основываются другие операции, более сложные.
Операция декартового произведения и операция естественного соединения являются бинарными операциями типа произведения и основываются на операции объединения двух отношений, которую мы рассматривали ранее.
Хотя действие операции декартова произведения многим может показаться знакомым, начнем мы все-таки с операции естественного произведения, так как она является более общим случаем, нежели первая операция.
Итак, рассмотрим операцию естественного соединения. Следует сразу заметить, что операндами этого действия могут являться отношения с разными схемами в отличие от трех бинарных операций объединения, пересечения и переименования.
Если рассмотреть два отношения с различными схемами отношений r 1(S 1) и r 2(S 2 ), то их естественным соединением будет новое отношение r 3(S 3), которое будет состоять только из тех кортежей операндов, которые совпадают на пересечении схем отношений. Соответственно, схема нового отношения будет больше любой из схем отношений исходных, так как является их соединением, «склеиванием». Кстати, кортежи, одинаковые в двух отношениях-операндах, по которым и происходит это «склеивание», называются соединимыми .
Запишем определение операции естественного соединения на языке формул систем управления базами данных:
r 3(S 3) = r 1(S 1) × r 2(S 2) = {t (S 1 ∪S 2) | t [S 1] ∈ r 1 & t (S 2) ∈ r 2};
Рассмотрим пример, хорошо иллюстрирующий работу естественного соединения, его «склеивание». Пусть дано два отношения r 1(S 1) и r 2(S 2), в табличной форме представления соответственно равные:
r 1(S 1):
r 2(S 2):
Мы видим, что у этих отношений присутствуют кортежи, совпадающие при пересечении схем S 1 и S 2 отношений. Перечислим их:
1) кортеж {a, 1} отношения r 1(S 1) совпадает с кортежем {1, x} отношения r 2(S 2);
2) кортеж {b, 1} из r 1(S 1) также совпадает с кортежем {1, x} из r 2(S 2);
3) кортеж {c, 3} совпадает с кортежем {3, z}.
Значит, при естественном соединении новое отношение r 3(S 3) получается «склеиванием» именно на этих кортежах. Таким образом, r 3(S 3) в табличном представлении будет выглядеть следующим образом:
r 3(S 3) = r 1(S 1) × r 2(S 2):
Получается по определению: схема S 3 не совпадает ни со схемой S 1, ни со схемой S 2, мы «склеили» две исходные схемы по пересекающимся кортежам, чтобы получить их естественное соединение.
Покажем схематично, как происходит соединение кортежей при применении операции естественного соединения.
Пусть отношение r 1 имеет условный вид:
А отношение r 2 – вид:
Тогда их естественное соединение
будет выглядеть следующим
Видим, что «склеивание» отношений-операндов происходит по той самой схеме, что мы приводили ранее, рассматривая пример.
Операция декартового соединения является частным случаем операции естественного соединения. Если конкретнее, то, рассматривая действие операции декартового произведения на отношения, мы заведомо оговариваем, что в этом случае может идти речь только о непересекающихся схемах отношений. В результате применения обеих операций получаются отношения со схемами, равными объединению схем отношений-операндов, только в декартово произведение двух отношений попадают всевозможные пары их кортежей, так как схемы операндов ни в коем случае не должны пересекаться.
Таким образом, исходя из всего вышесказанного запишем математическую формулу для операции декартового произведения:
r 4(S 4) = r 1(S1 ) × r 2(S 2) = {t (S 1 ∪ S 2) | t [S 1] ∈ r 1 & t (S 2) ∈ r 2}, S 1 ∩ S 2= ∅ ;
Теперь рассмотрим пример, чтобы показать, какой вид будет иметь результирующая схема отношения, при применении операции декартового произведения.
Пусть даны два отношения r 1(S1 ) и r 2(S 2), которые в табличном виде представляются следующим образом:
r 1(S 1):
r 2(S 2):
Итак, мы видим, что ни один из кортежей отношений r 1(S 1) и r 2(S 2), действительно, не совпадает в их пересечении. Поэтому в результирующее отношение r 4(S 4) попадут всевозможные пары кортежей первого и второго отношений-операндов. Получится:
r 4(S 4) = r 1(S1 ) × r 2(S 2):
Получилась новая схема отношения r 4(S 4) не «склеиванием» кортежей как в предыдущем случае, а перебором всех возможных различных пар несовпадающих в пересечении исходных схем кортежей.
Снова, как и в случае естественного соединения, приведем схематичный пример работы операции декартового произведения.
Пусть r 1 задано следующим условным образом:
А отношение r 2 задано:
Тогда их декартовое произведение схематично можно изобразить следующим образом:
Именно таким образом и получается результирующее отношение при применении операции декартового произведения.
Из приведенных выше определений бинарных операций объединения, пересечения, разности, декартового произведения и естественного соединения следуют свойства.
1. Первое свойство, как и в случае унарных операций, иллюстрирует соотношение мощностей отношений:
1) для операции объединения:
|r 1 ∪ r 2| ≤ |r 1| + |r 2|;
2) для операции пересечения:
|r 1 ∩ r 2 | ≤ min (|r 1|, |r 2|);
3) для операции разности:
|r 1 \ r 2| ≤ |r 1|;
4) для операции декартового произведения:
|r 1 × r 2| = |r 1| · |r 2|;
5) для операции естественного соединения:
|r 1 × r 2| ≤ |r 1| · |r 2|.
Соотношение мощностей, как мы помним, характеризует, как меняется количество кортежей в отношениях после применения той или иной операции. Итак, что мы видим? Мощность объединения двух отношений r 1 и r 2 меньше суммы мощностей исходных отношений-операндов. Почему это происходит? Все дело в том, что при объединении совпадающие кортежи исчезают, накладываясь друг на друга. Так, обратившись к примеру, который мы рассматривали по прохождении этой операции, можно заметить, что в первом отношении было два кортежа, во втором – три, а в результирующем – четыре, т. е. меньше, чем пять (сумма мощностей отношений-операндов). По совпадающему кортежу {b, 2} эти отношения «склеились».
Мощность результата пересечения двух отношений меньше или равна минимальной мощности исходных отношений-операндов. Обратимся к определению этой операции: в результирующее отношение попадают только те кортежи, которые присутствуют в обоих отношениях исходных. А значит, мощность нового отношения никак не может превышать мощности того отношения-операнда, число кортежей которого наименьшее из двух. А равной этой минимальной мощности мощность результата быть может, так как всегда допускается случай, когда все кортежи отношения с меньшей мощностью совпадают с какими-то кортежами второго отношения-операнда.
В случае операции разности все достаточно тривиально. Действительно, если из первого отношения-операнда «вычесть» все кортежи, присутствующие также во втором отношении, то их количество (а следовательно, мощность) уменьшится. В том случае, если ни один кортеж первого отношения не совпадет ни с одним кортежем отношения второго, т. е. «вычитать» будет нечего, мощность его не уменьшится.
Интересно, что в случае применения операции декартового произведения мощность результирующего отношения в точности равна произведению мощностей двух отношений-операндов. Понятно, что это происходит потому, что в результат записываются все возможные пары кортежей исходных отношений, а ничего не исключается.
И, наконец, операцией естественного соединения получается отношение, мощность которого больше или равна произведения мощностей двух исходных отношений. Опять-таки это происходит потому, что отношения-операнды «склеиваются» по совпадающим кортежам, а несовпадающие – из результата исключаются вовсе.
2. Свойство идемпотентности:
1) для операции объединения: r ∪ r = r ;
2) для операции пересечения: r ∩ r = r ;
3) для операции разности: r \ r ≠ r ;
4) для операции декартового произведения (в общем случае, свойство не применимо);
5) для операции естественного соединения: r × r = r .
Интересно, что свойство идемпотентности верно не для всех операций из приведенных, а для операции декартового произведения оно и вовсе не применимо. Действительно, если объединить, пересечь или естественно соединить какое-либо отношение само с собой, оно не изменится. А вот если отнять от отношения точно равное ему отношение, в результате получится пустое отношение.
3. Свойство коммутативности:
1) для операции объединения:
r 1 ∪ r 2 = r 2 ∪ r 1;
2) для операции пересечения:
r ∩ r = r ∩ r ;
3) для операции разности:
r 1 \ r 2 ≠ r 2 \ r 1;
4) для операции декартового произведения:
r 1 × r 2 = r 2 × r 1;
5) для операции естественного соединения: