Реляционная алгебра

В этом разделе на ряде примеров рассматриваются операции реляционной алгебры [11]. Для представления каждой операции будем использовать терминологию как алгебры, так и исчисления. Последняя базируется на системе понятий, использованной Коддом. Пять операций являются основными:

– проекция;

– объединение;

– разность;

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

– селекция.

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


P(D 1	D2,	D3)	Q(D4	D5)	R(M,	P,	Q,	T)	S(A,	B)
1	11	x	x	1	x	101	5	a	5	a
2	11	у	x	2	y	105	3	a	10	b
3	11	z	y	1	z	500	9	a	15	c
4	12	x			w	50	1	b	2	d
					w	10	2	b	6	a
					w	300	4	b	1	b

Описание каждого отношения состоит из имени отношения, за которым в круглых скобках следует список атрибутов (это описание называется интенсионалом или схемой отношения). Под описанием приведено некоторое заполнение кортежей отношения (экстенсинал отношения). В последующих примерах буквы R и S

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

Проекция

Алгебра		Исчисление
R[A]		{t[A] t ?R}

Операция проекции представляет собой выборку из каждого кортежа отношения значений атрибутов, входящих в A, и удаление из полученного отношения повторяющихся строк. В исчислении t обозначает «кортежную» переменную, значениями которой являются кортежи исходного отношения R, a t[A] – часть кортежа R с атрибутами из A.
В соответствии с определением отношения неявно предполагается удаление дубликатов кортежей результирующего отношения.

Пример

Объединение

Алгебра	Исчисление
R S	{t\| t ?R ?t ?S}

Для того чтобы объединение было возможным, отношения-операнды (R и S) должны быть совместимы по объединению, т.е. их атрибуты должны быть определены над совместными данными.

Пример

Разность

Алгебра	Исчисление
R –S	{t\| t ?R ?t ?S}

Пример

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

Алгебра	Исчисление
R S	{(r\|\|s) \| r ?R ?r ?S}

Из обозначений видно, что операция декартова произведения осуществляется между кортежами отношений-аргументов, а результатом является конкатенация (обозначаемая ||) соответствующих кортежей. При этом

Степень(R

S)= Степень(R)+Степень(S),

Мощность(R

S)= Мощность(R)× Мощность(S).

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

RA=R[M,T] и RB=R[Q,T]

S,

т.е.

Тогда

Степень результирующего отношения равна 4(2+2), а мощность – 8 (2×4).

Селекция (Ограничение)

Алгебра	Исчисление
(a) R[A?v]	{t\| t ?R ?(t[A]?v)}
(б) R[A?B]	{t\| t ?R ?(t[A]?t[B])}

В приведенном определении v обозначает константу, а В – атрибут отношения R, отличный от А. Символ ?

используется для обозначения одной из операций сравнения (<, ?, =, ?, ?, >).

Примеры

P[D1>D2]=Ø (пустое множество) поскольку в отношении отсутствуют кортежи, где D1>D2.

Пересечение

Алгебра	Исчисление
R S	{t\| t ?R ?t ?S}

Пересечение R

S=R-(R-S), что соответствует области, отмеченной звездочкой на диаграмме Венна для операции разности.

Пример

Соединение

Алгебра	Исчисление
R[A?B]S	{(r\|\|s) \| r ?R ?s ?S ?(r[A]?s[B])}

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

Имеется несколько вариантов операции соединения:

а) тета- и эквисоединение. При этой операции A и B являются совместимыми атрибутами соединения, а степень результирующего отношения равна сумме степеней отношений-операндов. Такое соединение называется ?-соединением (тета-соединением). В случае сравнения на равенство соединение называется экви-соединение;

б) естественное соединение. В этом случае атрибуты соединения имеют общие (одинаковые) домены, и после соединения один из атрибутов отбрасывается. Степень результирующего отношения на единицу меньше суммы степеней отношений-операндов;

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

Примеры

Тета-соединение R[Q>A]S

При выполнении соединения необходимо для каждого кортежа из R взять значение атрибута Q и сравнить его со значением атрибута A из каждого кортежа S. В результате получим

Следует отметить, что кортеж <w 50 1 b> отношения R не вошел в результирующее отношение.

Естественное соединение P[D3 =D4]Q

Деление

Алгебра	Исчисление
R[A÷B]S	{r[ ] \| r ?R ?s ?S[B] gR(r[ ])}

Атрибуты A и

B являются совместимыми и/или общими атрибутами деления. Для упрощения объяснения можно считать R бинарным отношением, состоящим из A и дополнения A, которое обозначается

и содержит атрибуты, отличные от A. Для каждого раздела из R[

], т.е. для каждого уникального кортежа r[

], необходимо выполнить следующее:

• выбрать допустимые строки кортежей r[

]

из R[

], обозначив полученное множество кортежей через T=gR(r[

]). Множество T называется также множеством-образом;

• в результирующее отношение входят кортежи r, для которых выполняется S[B]HgR(r[

]).

Примеры

Р[D3>÷D4]=Ø (пустое множество), так как

Следовательно, подходящие

отсутствуют.

Содержание раздела