 |
Свойства бинарных операций
|
|
|
|
Из приведенных выше определений бинарных операций объединения, пересечения, разности, декартового произведения и естественного соединения следуют свойства.
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) для операции естественного соединения:
r 1 × r 2 = r 2 × r 1.
Свойство коммутативности выполняется для всех операций, кроме операции разности. Это легко понять, ведь от перестановки отношений местами их состав (кортежи) не меняется. А при применении операции разности важно, какое из отношений‑операндов стоит на первом месте, потому что от этого зависит, кортежи какого отношения примутся за эталонные, т. е. с какими кортежами будут сравниваться другие кортежи на предмет исключения.
4. Свойство ассоциативности:
1) для операции объединения:
(r 1 ∪ r 2) ∪ r 3 = r 1 ∪(r 2 ∪ r 3);
2) для операции пересечения:
(r 1 ∩ r 2) ∩ r 3 = r 1 ∩ (r 2 ∩ r 3);
3) для операции разности:
(r 1 \ r 2) \ r 3 ≠ r 1 \ (r 2 \ r 3);
4) для операции декартового произведения:
(r 1 × r 2) × r 3 = r 1 × (r 2 × r 3);
5) для операции естественного соединения:
(r 1 × r 2) × r 3 = r 1 × (r 2 × r 3).
И снова мы видим, что свойство выполняется для всех операций, кроме операции разности. Объясняется это таким же образом, как и в случае применения свойства коммутативности. По большому счету, операциям объединения, пересечения, разности и естественного соединения все равно в каком порядке стоят отношения‑операнды. Но при «отнимании» отношений друг от друга порядок играет главенствующую роль.
На основании вышеприведенных свойств и рассуждений можно сделать следующий вывод: три последних свойства, а именно свойство идемпотентности, коммутативности и ассоциативности, верны для всех рассмотренных нами операций, кроме операции разности двух отношений, для которой не выполнилось вообще ни одно из трех означенных свойств, и только в одном случае свойство оказалось неприменимым.
Варианты операций соединения
Используя как основу рассмотренные ранее унарные операции выборки, проекции, переименования и бинарные операции объединения, пересечения, разности, декартова произведения и естественного соединения (все они в общем случае называются операциями соединения), мы можем ввести новые операции, выведенные с помощью перечисленных понятий и определений. Подобная деятельность называется составлением вариантов операций соединения.
|
|
|
Первым таким вариантом операций соединения является операция внутреннего соединения по заданному условию соединения.
Операция внутреннего соединения по какому‑то определенному условию определяется как производная операция от операций декартового произведения и выборки.
Запишем формульное определение этой операции:
r 1(S 1) × P r 2(S 2) = σ < P > (r 1 × r 2), S 1 ∩ S 2 = ∅;
Здесь P = P < S 1 ∪ S 2> – условие, накладываемое на объединение двух схем исходных отношений‑операндов. Именно по этому условию и происходит отбор кортежей из отношений r 1 и r 2 в результирующее отношение.
Следует отметить, что операция внутреннего соединения может применяться к отношениям с разными схемами отношений. Эти схемы могут быть любыми, но они ни в коем случае не должны пересекаться.
Кортежи исходных отношений‑операндов, попавшие в результат операции внутреннего соединения, называются соединимыми кортежами.
Для наглядного иллюстрирования работы операции внутреннего соединения, приведем следующий пример.
Пусть нам даны два отношения r 1(S 1) и r 2(S 2) с различными схемами отношения:
r 1(S 1):
r 2(S 2):
Следующая таблица даст результат применения операции внутреннего соединения по условию P = (b1 = b2).
r 1(S 1) × P r 2(S 2):
Итак, мы видим, что действительно «слипание» двух таблиц, представляющих отношения, произошло именно по тем кортежам, в которых выполняется условие операции внутреннего соединения P = (b1 = b2).
Теперь на основании уже введенной операции внутреннего соединения мы можем ввести операцию левого внешнего соединения и правого внешнего соединения. Поясним.
Результатом операции левое внешнее соединение является результат внутреннего соединения, пополненный несоединимыми кортежами левого исходного отношения‑операнда. Аналогично результат операции правого внешнего соединения определяется как результат операции внутреннего соединения, пополненный несоединимыми кортежами стоящего справа исходного отношения‑операнда.
|
|
|
Вопрос, чем же пополняются результирующие отношения операций левого и правого внешнего соединения, вполне ожидаем. Кортежи одного отношения‑операнда дополняются на схеме другого отношения‑операнда Null‑значениями.
Стоит заметить, что введенные таким образом операции левого и правого внешнего соединения являются производными операциями от операции внутреннего соединения.
Чтобы записать общие формулы для операций левого и правого внешнего соединений, проведем некоторые дополнительные построения.
Пусть нам даны два отношения r 1(S 1) и r 2(S 2) с различными схемами отношений S 1 и S 2, не пересекающимися друг с другом.
Так как мы уже оговаривали, что операции левого и правого внутреннего соединения являются производными, то мы можем получить следующие вспомогательные формулы для определения операции левого внешнего соединения:
1) r 3 (S 2 ∪ S 1) ≔ r 1(S 1) × P r 2(S 2);
r 3 (S 2 ∪ S 1) – это просто результат внутреннего соединения отношений r 1(S 1) и r 2(S 2). Левое внешнее соединение является производной операцией именно от операции внутреннего соединения, поэтому мы и начинаем наши построения с нее;
2) r 4(S 1) ≔ r 3(S 2 ∪ S 1) [ S 1];
Таким образом, с помощью унарной операции проекции, мы выделили все соединимые кортежи левого исходного отношения‑операнда r 1(S 1). Результат обозначили r 4(S 1) для удобства применения;
3) r 5 (S 1) ≔ r 1(S 1) \ r 4(S 1);
Здесь r 1(S 1) – все кортежи левого исходного отношения‑операнда, а r 4(S 1) – его же кортежи, только соединимые. Таким образом, при помощи бинарной операции разности, в отношении r 5(S 1) у нас получились все несоединимые кортежи левого отношения‑операнда;
4) r 6(S 2)≔ {∅(S 2)};
{∅(S 2)} – это новое отношение со схемой (S 2), содержащее всего один кортеж, причем составленный из Null‑значений. Для удобства мы обозначили это отношение r 6(S 2);
5) r 7 (S 2 ∪ S 1) ≔ r 5(S 1) × r 6(S 2);
Здесь мы взяли полученные в пункте три, несоединимые кортежи левого отношения‑операнда (r 5(S 1)) и дополнили их на схеме второго отношения‑операнда S 2 Null‑значениями, т. е. декартово умножили отношение, состоящее из этих самых несоединимых кортежей на отношение r 6(S 2), определенное в пункте четыре;
6) r 1(S1) →× P r 2(S 2) ≔ (r 1 × P r 2) ∪ r 7 (S 2 ∪ S 1);
|
|
|
Это и есть левое внешнее соединение, полученное, как можно видеть, объединением декартового произведения исходных отношений‑операндов r 1 и r 2 и отношения r 7 (S 2 ∪ S 1), определенного в пункте пятом.
Теперь у нас имеются все необходимые выкладки для определения не только операции левого внешнего соединения, но по аналогии и для определения операции правого внешнего соединения. Итак:
1) операция левого внешнего соединения в строгом формулярном виде выглядит следующим образом:
r 1(S 1) →× P r 2(S 2) ≔ (r 1 × P r 2) ∪ [(r 1 \ (r 1 × P r 2) [ S 1]) × {∅(S 2)}];
2) операция правого внешнего соединения определяется подобным образом операции левого внешнего соединения и имеет следующий вид:
r 1(S 1) →× P r 2(S 2) ≔ (r 1 × P r 2) ∪ [(r 2 \ (r 1 × P r 2) [ S 2]) × {∅(S 1)}];
Эти две производные операции имеют всего два свойства, достойные упоминания.
1. Свойство коммутативности:
1) для операции левого внешнего соединения:
r 1(S 1) →× P r 2(S 2) ≠ r 2(S 2) →× P r 1(S 1);
2) для операции правого внешнего соединения:
r 1(S 1) ←× P r 2(S 2) ≠ r 2(S 2) ←× P r 1(S 1)
Итак, мы видим, что свойство коммутативности не выполняется для этих операций в общем виде, но при этом операции левого и правого внешнего соединения взаимно обратны друг другу, т. е. выполняется:
1) для операции левого внешнего соединения:
r 1(S 1) →× P r 2(S 2) = r 2(S 2) →× P r 1(S 1);
2) для операции правого внешнего соединения:
r 1(S 1) ←× P r 2(S 2) = r 2(S 2) ←× P r 1(S 1).
2. Основным свойством операций левого и правого внешнего соединения является то, что они позволяют восстановить исходное отношение‑операнд по конечному результату той или иной операции соединения, т. е. выполняются:
1) для операции левого внешнего соединения:
r 1(S1) = (r 1 →× P r 2) [ S 1];
2) для операции правого внешнего соединения:
r 2(S 2) = (r 1 ←× P r 2) [ S 2].
Таким образом, мы видим, что первое исходное отношение‑операнд можно восстановить из результата операции левого правого соединения, а если конкретнее, то применением к результату этого соединения (r 1 × r 2) унарной операции проекции на схему S 1, [ S 1].
И аналогично второе исходное отношение‑операнд можно восстановить применением к результату операции правого внешнего соединения (r 1 × r 2) унарной операции проекции на схему отношения S 2.
Приведем пример для более подробного рассмотрения работы операций левого и правого внешних соединений. Введем уже знакомые нам отношения r 1(S 1) и r 2(S 2) с различными схемами отношения:
r 1(S 1):
r 2(S 2):
Несоединимый кортеж левого отношения‑операнда r 2(S 2) – это кортеж {d, 4}. Следуя определению, именно им следует дополнить результат внутреннего соединения двух исходных отношений‑операндов.
Условие внутреннего соединения отношений r 1(S 1) и r 2(S 2) также оставим прежнее: P = (b1 = b2). Тогда результатом операции левого внешнего соединения будет следующая таблица:
r 1(S 1) →× P r 2(S 2):
Действительно, как мы можем видеть, в результате воздействия операции левого внешнего соединения, произошло пополнение результата операции внутреннего соединения несоединимыми кортежами левого, т. е. в нашем случае первого отношения‑операнда. Пополнение кортежа на схеме второго (правого) исходного отношения‑операнда по определению произошло при помощи Null‑значений.
И аналогично результатом правого внешнего соединения по тому же, что и раньше, условию P = (b1 = b2) исходных отношений‑операндов r 1(S 1) и r 2(S 2) является следующая таблица:
r 1(S 1) ←× P r 2(S 2):
Действительно, в этом случае пополнять результат операции внутреннего соединения следует несоединимыми кортежами правого, в нашем случае второго исходного отношения‑операнда. Такой кортеж, как не трудно видеть, во втором отношении r 2(S 2) один, а именно {2, y}. Далее действуем по определению операции правого внешнего соединения, дополняем кортеж первого (левого) операнда на схеме первого операнда Null‑значениями.
И, наконец, рассмотрим третий вариант приведенных ранее операций соединения.
Операция полного внешнего соединения. Эту операцию вполне можно рассматривать не только как операцию, производную от операций внутреннего соединения, но и как объединение операций левого и правого внешнего соединения.
Операция полного внешнего соединения определяется как результат пополнения того же самого внутреннего соединения (как и в случае определения левого и правого внешних соединений) несоединимыми кортежами одновременно и левого, и правого исходных отношений‑операндов. Исходя из этого определения дадим формулярный вид этого определения:
r 1(S 1) ↔× P r 2(S 2) = (r 1 →× P r 2) ∪ (r 1 ←× P r 2);
У операции полного внешнего соединения также имеется свойство, сходное с аналогичным свойством операций левого и правого внешних соединений. Только за счет изначальной взаимно‑обратной природы операции полного внешнего соединения (ведь она была определена как объединение операций левого и правого внешних соединений) для нее выполняется свойство коммутативности:
r 1(S 1) ↔× P r 2(S 2) = r 2(S 2) ↔ × P r 1(S 1);
И для завершения рассмотрения вариантов операций соединения, рассмотрим пример, иллюстрирующий работу операции полного внешнего соединения. Введем два отношения r 1(S 1) и r 2(S 2) и условие соединения.
Пусть
r 1(S 1)
r 2(S 2):
И пусть условием соединения отношений r 1(S 1) и r 2(S 2) будет: P = (b1 = b2), как и в предыдущих примерах.
Тогда результатом операции полного внешнего соединения отношений r 1(S 1) и r 2(S 2) по условию P = (b1 = b2) будет следующая таблица:
r 1(S 1) ↔× P r 2(S 2):
Итак, мы видим, что операция полного внешнего соединения наглядно оправдала свое определение как объединения результатов операций левого и правого внешних соединений. Результирующее отношение операции внутреннего соединения дополнено одновременно несоединимыми кортежами как левого (первого, r 1(S 1)), так и правого (второго, r 2(S 2)) исходного отношения‑операнда.
Производные операции
Итак, мы рассмотрели различные варианты операций соединения, а именно операции внутреннего соединения, левого, правого и полного внешнего соединения, которые являются производными восьми исходных операций реляционной алгебры: унарных операций выборки, проекции, переименования и бинарных операций объединения, пересечения, разности, декартова произведения и естественного соединения. Но и среди этих исходных операций есть свои примеры производных операций.
1. Например, операция пересечения двух отношений является производной от операции разности этих же двух отношений. Покажем это.
Операцию пересечения можно выразить следующей формулой:
r 1(S) ∩ r 2(S) = r 1 \ r 1 \ r 2
или, что дает тот же результат:
r 1(S) ∩ r 2(S) = r 2 \ r 2 \ r 1;
2. Еще одним примером, производной базовой операции от восьми исходных операций является операция естественного соединения. В самом общем виде эта операция является производной от бинарной операции декартового произведения и унарных операций выборки, проекции и переименования атрибутов. Однако, в свою очередь, операция внутреннего соединения является производной операцией от той же операции декартового произведения отношений. Поэтому, чтобы показать, что операция естественного соединения – производная операция, рассмотрим следующий пример.
Сравним приведенные ранее примеры для операций естественного и внутреннего соединений.
Пусть нам даны два отношения r 1(S 1) и r 2(S 2) которые будут выступать в качестве операндов. Они равны:
r 1(S 1):
r 2(S 2):
Как мы уже получали ранее, результатом операции естественного соединения этих отношений будет являться таблица следующего вида:
r 3(S 3) ≔ r 1(S 1) × r 2(S 2):
А результатом внутреннего соединения этих же отношений r 1(S 1) и r 2(S 2) по условию P = (b1 = b2) будет следующая таблица:
r 4(S 4) ≔ r 1(S 1) × P r 2(S 2):
Сравним эти два результата, получившиеся новые отношения r 3(S 3) и r 4(S 4).
Ясно, что операция естественного соединения выражается через операцию внутреннего соединения, но, что главное, с условием соединения специального вида.
Запишем математическую формулу, описывающую действие операции естественного соединения как производную операции внутреннего соединения.
r 1(S 1) × r 2(S 2) = { ρ < ϕ 1> r 1 × E ρ < ϕ 2> r 2}[ S 1 ∪ S 2],
где E – условие соединимости кортежей;
E = ∀ a ∈ S 1 ∩ S 2 [ IsNull (b 1) & IsNull (2) ∪ b 1 = b 2];
b 1 = ϕ 1 (name (a)), b 2 = ϕ 2 (name (a));
Здесь одна из функций переименования ϕ 1 является тождественной, а другая функция переименования (а именно – ϕ 2) переименовывает атрибуты, на которых наши схемы пересекаются.
Условие соединимости E для кортежей записывается в общем виде с учетом возможных появлений Null‑значений, ведь операция внутреннего соединения (как уже было сказано выше) является производной операцией от операции декартового произведения двух отношений и унарной операции выборки.
|
|
|
