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

Разность.

Разностью двух отношений называется отношение, содержащее кортежи, входящие в первое отношение, и отсутствующие во втором.

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

На рисунке 3.3 показано схема операции разности.

Рис. 3.3 Разность отношений.

Прежде, чем давать определение декартову произведению отношений, определим операцию конкатенации кортежей.

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

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

Теперь мы можем дать определение декартова произведения отношений.

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

То есть, предположим, у нас есть отношение, имеющее три атрибута и содержащее десять кортежей, и отношение, имеющее четыре атрибута и содержащее двадцать кортежей. В результате декартова произведения этих отношений мы получим отношение с семью атрибутами (3 + 4), содержащее двести кортежей (10 * 20).

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

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

В качестве определения сокращения приведем более обобщенную версию, данную Дейтом в [1].

Предположим, что отношение А имеет атрибуты X, Y,..., Z (и, возможно, другие атрибуты), а Р является функцией с истинностными значениями, формальные параметры которой представляют собой строгое подмножество атрибутов X, Y,..., Z. В таком случае сокращение А в соответствии с Р, является отношением с тем же заголовком, что и в А, и с телом, состоящим из всех кортежей отношения А, таких, что функция Р принимает значение TRUE для рассматриваемого кортежа.

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

Операцию проекции можно определить следующим образом. Предположим, у нас имеется отношение А, обладающее атрибутами X, Y и Z. Тогда проекцией А по атрибутам X и Z будет являться отношение, обладающее атрибутами X и Z, но без атрибута Y. При этом значения атрибутов X и Z в каждом кортеже остаются теми же, какими были в исходном отношении.

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

Операция соединения достаточно многообразна, но чаще всего под соединением понимают, так называемое, естественное соединение. Именно его мы и рассмотрим.

Предположим, что имеются два отношения – А {X₁, X₂, …, X_n, Y₁, Y₂, …, Y_n} и B {Y₁, Y₂, …, Y_n, Z₁, Z₂, …, Z_n}. При этом, атрибуты Y₁, Y₂, …, Y_n в обоих отношениях совпадают по составу, а среди остальных атрибутов совпадений нет.

Тогда соединением А и В будет отношение, с заголовком { X₁, X₂, …, X_n, Y₁, Y₂, …, Y_n, Z₁, Z₂, …, Z_n}, кортежи которого составляются из кортежей исходных отношений, так, чтобы значения атрибутов Y₁, Y₂, …, Y_n в них были равны между собой (несколько неформальное описание, но, как представляется, адекватно передающее суть).

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

Соединение можно иначе определить, как результат последовательного выполнения декартова произведения исходных отношений, затем выполнения над исходным отношением операции сокращения, условием отбора в которой является совпадение значений атрибутов использованных для соединения, и выполнения над результатом сокращения проекции, которая исключает из него дублирующиеся атрибуты Y₁, Y₂, …, Y_n. Соответственно, если множество атрибутов, по которому производится соединение, пусто, то соединение вырождается в обычное декартово произведение. В случае, если набор атрибутов в исходных отношениях полностью совпадает, то соединение вырождается в операцию пересечения.

Деление – пожалуй, наиболее сложная для восприятия операция. Эта операция наименее очевидна из всех операций реляционной алгебры и поэтому нуждается в более подробном объяснении. Пусть заданы два отношения - A с заголовком {a₁, a₂,..., a_n, b₁, b₂,..., b_m} и B с заголовком {b₁, b₂,..., b_m}. Будем считать, что атрибут b_i отношения A и атрибут b_i отношения B не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {a_j} составным атрибутом a, а множество атрибутов {b_j} - составным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения A(a,b) на унарное отношение B(b).

Результатом деления A на B является унарное отношение C(a), состоящее из кортежей v таких, что в отношении A имеются кортежи <v, w> такие, что множество значений {w} включает множество значений атрибута b в отношении B.

Звучит достаточно сложно, но можно проиллюстрировать на следующем примере. Предположим, у нас есть организация, занимающаяся разработкой программного обеспечения. И отношение А – это список сотрудников и языков программирования, которыми они владеют, с кортежами вида {Иванов, C++}. Для каждого сотрудника имеется столько записей, сколько языков он знает. Допустим далее, что для нового проекта нам нужны сотрудники, владеющие некоторым набором языков. Список нужных языков – это как раз и будет отношение B. В результате деления А на В мы получим отношение, содержащее список сотрудников, владеющих всеми требуемыми языками. Если таковые найдутся, конечно.

Мы рассмотрели все основные операции реляционной алгебры. На практике применять их непосредственно приходится, прямо скажем, нечасто – подавляющее большинство СУБД поддерживает язык SQL и операции реляционной алгебры в чистом виде там применить негде.