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

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

Пример языка запросов, основанного на реляционной алгебре – ISBL (Information System Base Language – базовый язык информационных систем). В современных СУБД такие языки распространения не получили.

Вариант РА, предложенный Коддом, включает следующие основные операции: объединение, разность (вычитание), пересечение, декартово (прямое) произведение (или произведение), выборка (селекция, ограничение), проекция, деление и соединение. Графически эти операции представлены на рис. 4.7.

Объединение

Разность

Пересечение

Проекция

Выборка

Произведение

Деление

Соединение (естественное)

Рис. 4.7. Основные операции реляционной алгебры

Дейт заметил, что реляционная алгебра Кодда обладает несколькими недостатками. С одной стороны, восемь перечисленных операций по охвату функций избыточны, т.к. минимальный набор составляют пять операций: объединение, вычитание, произведение, проекция и выборка, остальные могут быть определены через них. А, с другой стороны, восемь операций Кодда недостаточно для построения реальной СУБД на принципах реляционной алгебры. Требуются операции переименования атрибутов, образования новых вычислительных атрибутов, вычисления итоговых функций, построения сложных алгебраических выражений, присвоения, сравнения и т.д.

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

Операции реляционной алгебры Кодда можно разделить на две группы: базовые теоретико-множественные и специальные реляционные. Первая группа операций включает в себя классические операции теории множеств: объединение, разность, пересечение и произведение. Вторая группа представляет собой развитие теоретико-множественных операций в направлении к реальным задачам манипулирования данными. Ее составляют операции проекции, селекции, деления и соединения.

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

Совместимость структур отношений означает совместимость атрибутов и типов соответствующих доменов. Частный случай совместимости – идентичность (совпадение).

Объединением двух совместимых отношений R1 и R2 одинаковой размерности (R1 UNION R2) является отношение R, содержащее все элементы исходных отношений с исключением повторений.

Пример 1. Объединение отношений. К списку поставщиков из Москвы добавляется список поставщиков необходимой детали Р1.

R1 – множество поставщиков из Москвы

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва
S4	Николай	20	Москва

R2 – множество поставщиков детали Р1

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва
S2	Иван	10	Иркутск

Тогда R – множество поставщиков из Москвы, или поставщиков детали Р1, либо поставщиков детали Р1 из Москвы (R1 UNION R2)

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва
S2	Иван	10	Иркутск
S4	Николай	20	Москва

Вычитание совместимых отношений R1 и R2 одинаковой размерности (R1 MINUS R2) есть отношение, тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих отношению R2.

Для приведенных отношений R1 и R2 отношение R будет представлять множество поставщиков из Москвы, не поставляющих деталь Р1, т.е. R ={(S4,Николай, 20, Москва)}.

П#	Имя	Статус	Город_п
S4	Николай	20	Москва

Очевидно, что результат операции зависит от порядка следования операндов, т.е. (R1 MINUS R2) и (R2 MINUS R1) – не одно и тоже.

Пересечение двух совместимых отношений R1 и R2 одинаковой размерности (R1 INTERSECT R2) порождает отношение R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отношениям.

Для приведенных отношений R1 и R2 отношение R будет представлять множество поставщиков из Москвы, поставляющих деталь Р1, т.е.

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва

Произведение отношения R1 степени k1 и отношения R2 степени k2 (R1 TIMES R2), не имеющих одинаковых имен атрибутов, есть отношение R степени k1+k2, заголовок которого представляет собой сцепление заголовков отношений R1 и R2.

Тело отношения R имеет такие кортежи, что первые k1 элементов кортежей принадлежат множеству R1, а последние k2 элементов кортежей принадлежат множеству R2. При необходимости получить произведение двух отношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция переименования RENAME.

Пример 2. Произведение отношений.

Пусть отношение R1 – множество номеров всех текущих поставщиков {S1, S2, S3, S4, S5}, а отношение R2 – множество номеров всех текущих деталей {P1, P2, P3, P4, P5, P6}. Результатом операции R1 TIMES R2 является множество всех возможных пар типа «поставщик-деталь», т.е. {(S1,P1), (S1,P2), (S1,P3), (S1,P4), (S1,P5), (S1,P6), (S2,P1),…, (S5,P6)}.

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

Для записи формулы f используются операнды – имена атрибутов (или номера столбцов), константы, логические операции (AND – И, OR – ИЛИ, NOT - НЕ), операции сравнения и скобки.

Пример 3. Выборки.

1) из отношения Р выбрать кортежи, в которых вес деталей меньше 14.

P WHERE Вес < 14

Д#	Название	Тип	Вес	Город_Д
Р1	Гайка	Каленый	12	Москва
Р5	палец	твердый	12	Иркутск

2)Из отношения Поставщик_Детали выбрать кортежи о поставке детали Р1 поставщиком S1.

SP WHERE п# = «S1» and Д# = «Р1»

П#	Д#	Количество
S1	P1	300

Проекция отношения А на атрибуты X,Y,…,Z (A[X,Y,…,Z]), где множество {X,Y,…,Z} является подмножеством полного списка атрибутов заголовка отношения А, представляет собой отношение с заголовком X,Y,…,Z и телом, содержащим кортежи отношения А, за исключением повторяющихся кортежей. Повторение одинаковых атрибутов в списке запрещается.

Операция проекции допускает следующие дополнительные варианты записи:

• Отсутствие списка атрибутов (R без скобок) означает указание всех атрибутов (операция тождественной проекции);

• Выражение вида R[] означает пустую проекцию, результатом которой является пустое множество;

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

Пример 4. Проекции.

1. из отношения Р выделить столбцы Тип и Город_Д и исключить повторения;

2. из отношения S выделить поставщиков, провающих в Иркутске.

1) Р [Тип, Город_Д] 2) (S WHERE Город_П=«Иркутск») [П#]

Тип	Город_Д		П#	Город_П
Каленый	Москва		S2	Иркутск
Мягкий	Иркутск		S3	Иркутск
Твердый	Ангарск
Твердый	Иркутск

Результатом деления отношения R1 с атрибутами А и В на отношение R2 с атрибутами В (R1 DIVIDEBY R2), где А и В простые или составные атрибуты, причем атрибут В – общий атрибут, определенный на одном и том же домене (множестве доменов составного атрибута), является отношение R с заголовком А и телом, состоящим из кортежей r таких, что в отношении R1 имеются кортежи (r,s), причем множество значений s включает множество значений атрибутов В отношения R2.