Замкнутость реляционной алгебры

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

R = f (R1 (r₁₁, r₁₂, …, r_1n ), R2(r₂₁, r₂₂, …, r_2n))

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

R = f (f₁ (R₁₁, R₁₂ ), f₂ (R₂₁, R₂₂ ))

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

Существуют 8 реляционных операторов, которые объединяются в 2 группы:

1. теоретико-множественные операторы:

• объединение

• пересечение

• сочетание

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

2. специальные реляционные операторы:

• выборка

• проекция

• соединение

• деление

Операторы второй группы выражаются через операторы первой группы.

Для использования этих операторов существует понятие «совместимость отношений».

Будем называть отношения совместимыми по типу, если:

1. для любого атрибута в одном отношении найдется атрибут с таким же наименованием в другом отношении;

2. атрибуты с одинаковыми именами определены на одних и тех же доменах (совпадает тип значений столбцов).

1. Оператор переименования атрибутов:

R RENAME Atr1, Atr2, … , Atrn AS NewAtr1, NewAtr2,…, NewAtrn.

2. Объединениемдвух совместимых по типу отношенийAиBназывается отношение с тем же заголовком, что и отношения А и В и телом, состоящим из кортежей, принадлежащих или А, или В, или обоим отношениям.

A UNION B

Замечание:

Объединение, как и любое отношение, не может содержать одинаковых кортежей. Поэтому, если некоторый кортеж входит и в А, и в В, то в объединение он входит только один раз.

А В

NO	Фамилия	ЗП
1	Иванов	100
2	Петров	200
3	Сидоров	300

NO	Фамилия	ЗП
1	Иванов	100
2	Пушников	250
4	Сидоров	300

Объединение А и В

NO	Фамилия	ЗП
1	Иванов	100
2	Петров	200
3	Сидоров	300
2	Пушников	250
4	Сидоров	300

3. Пересечение

A INTERSECT B

Пересечением двух совместимых по типу отношений А и В является отношение с тем же заголовком, что и отношения А и В, и телом, состоящим из кортежей принадлежащих одновременно обоим отношениям.

NO	Фамилия	ЗП
1	Иванов	100

4. Вычитание

A MINUS B

Вычитание В из А:

NO	Фамилия	ЗП
2	Петров	200
3	Сидоров	300

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

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

ATIMESB

Декартовым произведением двух отношений А (А1, А2, … , Аn) и В (В1, В2, … , Вm) называется отношение, заголовок которого является сцеплением заголовков отношений А и В (А1, А2, …, Аn, В1, В2, …, Вm), а тело состоит из кортежей, являющихся сцеплением кортежей отношения А и В:

(а1, а2, …, аn,b1,b2, …,bm)

(а1, а2, …, аn)A

(b1, b2, …, bm)B

Мощность декартова произведения равна произведению мощностей отношений А и В.

6. Выборка

Выборкой на отношении А с некоторым условием С называется отношение с тем же заголовком, что и отношение А и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие С дают значение ИСТИННО.

«С» представляет собой логическое выражение, в которое могут входить атрибуты отношения А и/или скалярное выражение. В простейшем случае С имеет вид:

XY, где— один из операторов сравнения (=,, >, <,,),

X,Y— атрибуты отношения А или скалярное выражение.

A WHERE C

A WHERE X  Y

Пример:Отношение А

WHEREЗП >= 300;

7. Проекция отношения А по атрибутамX,Y,Z, где каждый из атрибутов принадлежит отношению А — это отношение с заголовкомX,Y,Zи телом, содержащим множество кортежей видаx,y,z, таких, для которых в отношении А найдутся кортежи с атрибутомX=x,Y=y,Z=z.

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

A[X, Y, Z]

8. Соединение

Эта операция делится на 4 типа:

• Общая операция соединения

•  - соединение

• экви-соединение

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

Общая операция соединенияотношения А и В по условию С — это отношение вида:

(A TIMES B) WHERE C

где С представляет собой логическое выражение, в которое могут входить атрибуты А и В и/или скалярное выражение.

Все остальные операции соединения являются частными случаями.

 - соединение:

Пусть отношение А содержит атрибут X, а отношение В содержит атрибутY,— один из операторов сравнения, тогда- соединением отношения А по атрибутуXи отношения В по атрибутуYназывается:

(A TIMES B) WHERE XY

Экви-соединение:

Это частный случай - соединения, гдебудет являться знаком равенства (=), т.е.

(A TIMES B) WHERE X=Y

Замечание:

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

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

Пусть даны отношения А(A1,A2, …,An,X1,X2, …,Xp),B(X1,X2, …,Xp,B1,B2, …,Bm). Тогда естественным соединением А и В называется отношение с заголовком (A1,A2, …,An,X1,X2, …,Xp,B1,B2, …,Bm) и телом, содержащим множество кортежей (a1,a2, …,an,x1,x2, …,xp,b1,b2, …,bm) и каждый кортеж

(a1, a2, …, an, x1, x2, …, xp)A

(b1, b2, …, bm)B

A JOIN B

Лекция №11 (18.04.02)

Следствие:

В синтаксисе операции естественного соединения не указываются атрибуты, по которым производится склеивание. Склеивание производится по всем одинаковым атрибутам.

Естественное соединение эквивалентно следующей последовательности реляционных операций:

1. Переименовать одинаковые атрибуты в отношении;

2. Выполнить декартово произведение в отношении;

3. Выполнить выборку по совпадающим значениям атрибутов с одинаковыми именами;

4. выполнить проекцию, удалив совпадающие атрибуты;

5. Переименовать атрибуты, вернув им первоначальные имена.

Операция «естественное соединение» обладает свойством ассоциативности:

(A JOIN B) JOIN C = A JOIN (B JOIN C) = A JOIN B JOIN C

Пример:

Есть три отношения: «Поставщики», «Детали», «Поставки».

P (Поставщики)

PNUM	PNAME
1	Иванов
2	Петров
3	Сидоров

D (Детали)

DNUM	DNAME
1	SB
2	Video
3	HDD

PD(Поставки)

PNUM	DNUM	VOLUME
1	1	10
1	2	20
1	3	30
2	1	15
2	2	25
3	1	10

Какие детали поставляются поставщиками? Т.е. надо получить PNAMEиDNAME.

Для этого есть два способа:

1. сделать два экви-соединения

P [PNUM^P = PNUM^PD] PD

D [DNUM^P = DNUM^PD] PD

2. Выполнить естественное соединение:

P JOIN PD JOIN D

9. Деление

Пусть даны отношения А и В:

А(X1,X2, …,Xn,Y1,Y2, …,Ym)

В(Y1,Y2, …,Ym)

Делением отношения А на отношение В называется отношение с заголовком (X1,X2, …,Xn) и телом, содержащим множество кортежей

<x1,x2, …,xn> таких, что для всех кортежей <y1,y2, …,ym>Bсуществует кортеж <x1,x2, …,xn,y1,y2, …,ym>А.

Отношение а называется делимым, отношение В — делителем.

Пример:

На основе отношений P,PD,Dнайти тех поставщиков, которые поставляют все детали.

PD DEVIDED BY D