Соединение

Выбор

Проекция

Специальные операции

К специальным операциям реляционной алгебры относятся:

- проекция

- выбор (или селекция)

- соединение

- деление

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

Данная операция является унарной операцией на отношениях, т.е. в этой операции участвует только одно отношение.

Определение

Проекцией отношения r(R), R = {A_i}, на некоторый список имен атрибутов (подмножество атрибутов) L из R, L Í R, называется отношение s = p_L(r), для которого:

- схема отношения определяется списком L,

- реализация отношения есть множество кортежей, полученных из кортежей отношения r путем вычеркивания элементов, соответствующих атрибутам R – L и исключением дубликатов.

Формальная запись:

Дано r(R), R(A₁, A₂, …, A_m), r = {<t₁ : A₁, t₂ : A₂…, t_m : A_m >}

s(L) = p_L(r), L Í R, L(B₁, B₂, …, B_k), B_i Í R, s = {<u₁: B₁, u₂: B₂, …, u_k: B_k> | таких, что u_i = t_j, если B_i º A_j}

Пример:

r	(A	B	C	D)		L = (A,B)	pL(r)	(A	B)
	a1	b1	c2	d1				a1	b1
	a1	b1	c1	d2				a2	b1
	a2	b1	c3	d2

Проекция дает вертикальное подмножество отношения.

Свойство проекции:

Если Y Í X Í R, то p_Y(p_X(r)) º p_Y(r)

Данную операцию называют еще ограничением и селекцией.

Также является унарной операцией над отношением.

Определение

Выбором из отношения r(R) по условию F называется отношение s = s_F(r), для которого:

- схема отношения совпадает со схемой R,

- реализация отношения есть множество кортежей из r, удовлетворяющих условию F.

Формальная запись:

Дано r(R), r = {t_i}

s(R) = s_F(r), s = {u₁ | u_i Î R и F(u) – истинно}

Условие (предикат) F записывается в соответствии со следующими правилами:

- в качестве операндов могут быть указаны атрибуты отношения и/или константы;

- в качестве операций могут быть использованы операции отношения (=, ¹ и т.д.) и логические операции (Ù, Ú, Ø).

Для указания порядка вычисления предиката F в нем могут быть использованы круглые скобки.

Пример:

r	(A	B	C)		s = sA = ‘a1’ Ù C = ‘c1’(r)	(A	B	C)
	a1	b1	c1			a1	b1	c1
	a1	b2	c1			a1	b2	c1
	a2	b1	c2

Выбор дает горизонтальное подмножество отношения.

Свойства операции:

коммутативна – s_F1(s_F2(r)) = s_F2(s_F1(r)) = s_{F1Ù F2} (r)

дистрибутивна относительно операций g = (Ù, Ú, –):

s_F (r g s) = s_F (r) g s_F (s)

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

В реляционной алгебре рассматриваются две модификации данной операции: естественное соединение и соединение по условию (или q – соединение).

Естественное соединение

Определение

Естественным соединением отношений r₁(R₁), R₁ = XY, и r₂(R₂), R₂ = YZ, где Y – общее подмножество атрибутов из R₁ и R₂, определенных на одних и тех же доменах, называется отношение
s(R) = r₁ r₂, для которого:

- схема отношения R = R₁ È R₂ = XYZ,

- реализация отношения есть множество кортежей {t}, для которых p_XY(t) Î r₁ и p_YZ(t) Î r₂.

Формальная запись:

Даны r₁(R₁), R₁ = XY, и r₂(R₂), R₂ = YZ.

s(R) = r₁ r₂, R = R₁ È R₂ = XYZ, s = {t | таких, что p_XY(t) Î r₁ и p_YZ(t) Î r₂}

Пример:

r1

(A

B

C)

r2

(B

C

D)

s = r1 r2

(A

B

C

D)

a

b

c

b

c

d

a

b

c

d

d

b

c

b

c

e

a

b

c

e

b

b

f

a

d

b

d

b

c

d

c

a

d

d

b

c

e

c

a

d

b

Соединение по условию

Определение

Даны два отношения r₁(R₁) и r₂(R₂), для которых в R₁ и R₂ нет атрибутов с одинаковыми именами, т.е. R₁ Ç R₂ = 0. Пусть атрибут A Î R₁ сравним по условию q с атрибутом B Î R₂ (условие q определяется так же, как предикат F в операции выбора). Тогда соединением отношений r₁(R₁) и r₂(R₂) по условию q называется отношение s(R) = r_{1A qB} r₂, для которого:

- схема отношения R = R₁ È R₂,

- реализация отношения есть множество сцеплений кортежей из r₁ и r₂, удовлетворяющих условию A q B.

Формальная запись:

Даны r₁(R₁) и r₂(R₂), R₁ Ç R₂ = 0.

s(R) = r_{1A qB} r₂, R = R₁ È R₂, s = {uv | таких, что u Î r₁, v Î r₂ и для u и v выполняется условие q}.

Атрибуты A и B могут быть составными, т.е. A = {A₁, A₂, …, A_n}, B = {B₁, B₂, …, B_n}. Тогда
A q B = [A₁ q₁ B₁, A₂ q₂ B₂, …, A_n q_n B_n]. Операции q_i могут быть разными. Например, пусть даны r1(A1, A2, A3) и r2(B1, B2, B3), и все атрибуты определены на числовых доменах. Тогда можно получить соединение по условию: s = r_{1 A1 < B1, A2 = B2, A3 ³ B3} r₂

Пример:

r1

(A

B

C)

r2

(X

Y)

s = r1 B < X r2

(A

B

C

X

Y)

Если в качестве операции q используется операция =, такое соединение по условию называется эквисоединением.