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

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

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

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

Вариант реляционной алгебры, предложенный Коддом, включает следующие основные операции:

· объединение; +

· разность; +

· пересечение;

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

· селекция (выборка); +

Рекомендуемые материалы

· проекция; +

· деление;

· соединение.

Реляционная алгебра Кодда обладает следующими недостатками:

1) восемь перечисленных операций избыточны, т.к. минимальный набор может включать пять операций: объединение, вычитание, произведение, проекция и выборка. Три остальные операции: пересечение, соединение и деление можно определить через пять минимальных. Так, например, соединение – это проекция выборки произведения.

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

Все операции реляционной алгебры Кодда можно разделить на две группы:

1) базовые теоретико-множественные – это классические операции теории множеств: объединение, разность, пересечение и произведение;

2) специальные реляционные – расширение теоретико-множественных операций: проекция, селекция, деление и соединение. 

Графически операции можно представить так.

Объединение                                               Разность                                Пересечение

Произведение                                  Выборка                                Проекция

Деление                                            Соединение

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

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

Пример 1. Пусть отношение R1 множество поставщиков из Лондона, а отношения R2 – множество поставщиков, которые поставляют деталь Р1. Тогда отношение R (R1 UNION R2) означает поставщиков, находящихся в Лондоне, или поставщиков, поставляющих деталь Р1, либо тех и других.

R1

R2

R (R1 UNION R2)

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

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

R (R1 MINUS R2)

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

R (R2 MINUS R1)

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

R (R1 INTERSECT R2)

4. Произведение  отношения R1 степени к1 и отношения R2 степени к2 R (R1 TIMES R2), которые не имеют одинаковых имен атрибутов, есть такое отношение R степени (к1+к2), заголовок которого представляет сцепление заголовков отношений R1 и R2, а тело имеет кортежи такие, что первые к1 элементов кортежей принадлежат множеству R1, а последние к2 элементов – множеству R2. При необходимости получить произведение двух отношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция переименования RENAME.

Пример 2. Пусть отношение R1 представляет множество номеров текущих поставщиков {S1, S2}, а отношение R2 -  множество номеров всех текущих деталей {Р1, Р2, Р3}. Результатом операции R1 TIMES R2 является множество всех пар типа «поставщик-деталь», то есть {(S1,P1), (S1,P2), (S1,P3), (S2,P1), (S2,P2),(S2,P3)}.

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

R1

R2

R (R1 TIMES R2)

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

Пример 3. Пусть дано отношение P – детали. Выбрать выборку R (P WHERE Вес < 14) из отношения P.

P

P WHERE Вес < 14

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

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

· отсутствие списка атрибутов подразумевает указание всех атрибутов (операция тождественной проекции);

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

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

Пример 4. Вычислить проекцию отношения Р.

P [Тип, Город_Д]

Вычислить проекцию выборки из отношения S

S

(S WHERE Город_П= ”Краснодар”) [П#]

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

Пример 5. Пусть имеется отношения SP – поставки. R1 – проекция SP[П#, Д#], а R2 – отношение с заголовком Д# и телом {P2, P4}], тогда результатом деления R1на R2 будет отношение R с заголовком П# и телом {S1, S4}.

SP

R1                                                                  R2                               R1 DIVIDEBY R2

8. Соединение С_f(R1, R2) отношений R1 и R2 по условию, заданному формулой f, представляет собой отношение R, которое можно получить путем Декартова произведения отношений R1 и R2 с последующим применением к результату операции выборки по формуле f. Правила записи формулы f так же , как и для операции селекции.

Другими словами, соединением отношения R1 по атрибуту А с отношением R2 по атрибуту В (отношения не имеют общих имен атрибутов) является результатом выполнения операции вида:  (R1 TIMES R2) WHERE A Q B,

где Q – логическое выражение над атрибутами, определенными на одном (нескольких – для составного атрибута) домене. Соединение С_f(R1, R2), где формула f имеет произвольный вид, называют также Q-соединением.

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

Операция естественного соединения (операция JOIN) применяется к двум отношениям, имеющим общий атрибут (простой или составной). Этот атрибут в отношениях имеет одно и то же имя (совокупность имен) и определен на одном и том же домене (доменах).

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

Пример 6. Необходимо найти Q-соединение отношений S и P по атрибутам Город_П и Город_Д соответственно, причем кортежи результирующего отношения должно удовлетворять отношению «больше» (в смысле лексикографического порядка – по алфавиту).

(S TIMES P) WHERE Город_П > Город_Д

S

P

Эквисоединение.

(S TIMES P) WHERE Город_П > Город_Д

Пусть необходимо найти естественное соединение отношений S и P по общему атрибуту, характеризующему город (в отношении S – это Город_П, а в отношении P – Город_Д). Поскольку условие операции требует одинаковости имен атрибутов, по которым выполняется соединение, то применяется операция RENAME переименование атрибутов.

(S RENAME Город_П AS Город) JOIN (P RENAME Город_Д AS Город)