Теоретико – множественные операции

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

 

 

Пример. Даны два отношения C и D, совместимые по типу:

С

S	Название завода	Рейтинг	Город
S1	3BU		Москва
S4	Салют		Москва

 

 

D

S	Название завода	Рейтинг	Город
S1	3BU		Москва
S2	Динамо		Тула

 

 

1. Объединение - если даны отношения С и D одного и того же типа, то объединение этих отношений (С UNION D) является отношение того же типа с телом, состоящим из всех кортежей t, присутствующих в С или D или в обоих отношениях.

(С UNION D)

S	Название завода	Рейтинг	Город
S1	3BU		Москва
S2	Динамо		Тула
S4	Салют		Москва

 

Повторяющиеся кортежи удаляются по определению.

 

2. Разность – если даны два отношения С и D одного и того же типа, то разность этих отношений С MINUS D является отношение того же типа с телом состоящим из всех кортежей t таких, что t присутствует в С, но не в D.

 

С MINUS D

S	Название завода	Рейтинг	Город
S4	Салют		Москва

 

D MINUS С

S	Название завода	Рейтинг	Город
S2	Динамо		Тула

 

3. Пересечение – если даны отношения С и D одного и того же типа, то пересечением этих отношений С INTERSECT D является отношение того же типа с телом, состоящих из всех кортежей t таких, что t присутствует одновременно в С и D. Повторяющиеся кортежи удаляются по определению отношения.

 

 

С INTERSECT D

S	Название завода	Рейтинг	Город
S1	3BU		Москва

 

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

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

Даны отношения С и D:

S

S1

S2

S3

D C

Р

Р1

Р2

Р3

 

Декартово произведение отношений С и D:

С TIMES D

S	Р
S1	Р1
S1	Р2
S1	Р3
S2	Р1
S2	Р2
S2	Р3
S3	Р1
S3	Р2
S3	Р3

 

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

 

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

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

Пример1. Показать имена и статус всех поставщиков.

 

S {SNAME, STATUS}

SNAME	STATUS
Smith
Jones
Black

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

P {All BUT WGT}

 

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

D WHERE X  literal

В качестве операций могут быть указаны операции сравнения (>,<,= и др.). Выбор дает горизонтальное подмножество кортежей. Литерал – это значение, указанное непосредственно в тексте программы.

Пример2. Показать всю информацию о деталях красного цвета.

 

P WHERE COLOR= Red’

P	PNAME	COLOR	WGT	City
P1	Nut	Red		London
P4	Screw	Red		London

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

- соединение (соединение по условию).

- соединением отношения С по атрибуту Х с отношением D по атрибуту Y называется результат вычисления следующего выражения

(С TIMES D) WHERE X  Y

Если  «>», то выбирать строки, где X > Y. Такое  - соединение называется “ больше,чем”.

Даны два отношения C и D. Выполнить  - соединение отношений C и D по условию B < X.

С D

X	Y

А	В	С

 

 

(C TIMES D) WHERE B < X

A	B	C	X	Y

 

Эквисоединение (равносоединение).

Эквисоединение – это тета соединение, основанное на равенстве значений определенных столбцов. Здесь оператор  равен «=»

 

(C TIMES D) WHERE X=Y

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

Естественным соединением (C JOIN D) отношений C и D, имеющих множество атрибутов X,Y и Y,Z соответственно, где Y общее подмножество атрибутов из C и D, определенных на одних и тех же доменах, называется отношение с заголовком { X,Y,Z } и телом, содержащим множество кортежей таких, для которых в отношении C значение атрибута X равно x, а Y равно y, и в отношении D значение атрибута Z равно z.

Пример естественного соединения отношений C и D:

C D

Y	Z
B1	C1
B2	C1
B3	C2

X	Y
A1	B1
A2	B1
A3	B2

 

 

C JOIN D

 

X	Y	Z
A1	B1	C1
A2	B1	C1
A3	B2	C1

 

 

Пример3. Получить всю информацию о поставщиках и поставках. Выполнить естественное соединение (S JOIN SP) отношений S и SP.

 

Найдем сначала декартово произведение отношений S и SP. Перед выполнением этой операции необходимо переименовать атрибуты отношений так, чтобы у них не было одинаковых атрибутов. Переименуем атрибуты S# в отношении SP в атрибут SPS #

S TIMES (SP RENAME S# As SPS#)

S#	SNAME	STATUS	CITY	SPS#	P#	QTY
S1	Smith		London	S1	P1
S1	Smith		London	S1	P2
S1	Smith		London	S1	P3
S1	Smith		London	S2	P1
S1	Smith		London	S2	P2
S1	Smith		London	S3	P2
S2	Jones		Paris	S1	P1
S2	Jones		Paris	S1	P2
S2	Jones		Paris	S1	P3
S2	Jones		Paris	S2	P1
S2	Jones		Paris	S2	P2
S2	Jones		Paris	S3	P2
S3	Black		Paris	S1	P1
S3	Black		Paris	S1	P2
S3	Black		Paris	S1	P3
S3	Black		Paris	S2	P1
S3	Black		Paris	S2	P2
S3	Black		Paris	S3	P2

Таблица1. Декартово произведение отношений S и SP.

 

Выполним эквисоединение отношений S и SP.

(S TIMES (SP RENAME S# As SPS#)) WHERE S# = SPS#

Из предыдущей таблицы выберем строки, в которых значения атрибутов S# и SPS# равны. Получим следующее отношение.

 

S#	SNAME	STATUS	CITY	SPS#	P#	QTY
S1	Smith		London	S1	P1
S1	Smith		London	S1	P2
S1	Smith		London	S1	P3
S2	Jones		Paris	S2	P1
S2	Jones		Paris	S2	P2
S3	Black		Paris	S3	P2

Таблица 2. Эквисоединение отношений S и SP.

 

Если в этом отношении (Таблица 2) опустить один атрибут, например SPS#

 

((S TIMES (SP RENAME S# As SPS#)) WHERE S# = SPS#){All BUT SPS#}, (А)

 

то получим естественное соединение отношений S и SP.

(S JOIN SP) (В)

 

S#	SNAME	STATUS	CITY	P#	QTY
S1	Smith		London	P1
S1	Smith		London	P2
S1	Smith		London	P3
S2	Jones		Paris	P1
S2	Jones		Paris	P2
S3	Black		Paris	P2

Таблица 3. Естественное соединение отношений S и SP.

Выражения (А) и (В) эквивалентны.

Пример4. Определить имена поставщиков детали ‘P3’.

Сначала выполняется естественное соединение отношений S и SP по общему атрибуту S#. Затем в результате соединения выбираются кортежи, в которых P# = ‘P3’ Получаем всю информацию о поставщиках и поставках детали ‘P3’.

 

(S JOIN SP) WHERE P = ‘P3’ (С)

S#	SNAME	STATUS	CITY	P#	QTY
S1	Smith		London	P3
S2	Jones		Paris	P3
S3	Black		Paris	P3

 

Далее выполняется проекция по атрибуту SNAME полученной выборки:

 

((S JOIN SP) WHERE P# = ‘P3’){SNAME} (D)

 

Результат запроса:

 

SNAME

Smith

 

Предыдущее выражение (D) можно преобразовать в логически эквивалентное и более рациональное выражение следующего вида:

((SP WHERE P# = ‘P3’) JOIN S){SNAME} (F)

 

Реляционная алгебра может служить хорошим основанием для оптимизации.

 

Деление. Пусть отношения С и D имеют заголовки {X1, X2, …, XM} {Y1, Y2, …, YN} соответственно. Заголовки не пересекаются. Пусть имеется отношение Z с заголовком {X1, X2, …, XM, Y1, Y2,…, YN}. Результат деления отношения С на отношение D по отношению Z (C DIVIDEBY D PER Z, где отношение С - делимое, отношение D - делитель, Z - отношение-посредник) называется отношение, содержащее такие значения Х из отношения С, для которых соответствующие значения Y из Z включают все значения Y из D.

Z

S#	P#
S1	P1
S1	P2
S1	P3
S2	P1
S2	P2
S3	P2

С

S#

S1

S2

S3

 

D

P1

P2

P3

 

C DIVIDEBY D PER Z

 

S#

S1

 

Лекция 5. Реляционное исчисление.

 

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