Элементы реляционной алгебры

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

Считается, что в реляционной алгебре используется 8 операций, из которых 5 основные, а остальные дополнительные. Дополнительные могут получаться на основе комбинации основных операций.

Основные операции:

· Выборка,

· Проекция,

· Декартово произведение,

· Объединение,

· Разность.

Дополнительные операции:

· Соединение,

· Пересечение,

· Деление.

Операции выборки и проекции унарные, остальные – бинарные.

Пусть R и S – отношения. Рассмотрим схематично отношение в виде прямоугольника. В этом прямоугольнике будем отмечать горизонтально кортежи отношения, а вертикально – атрибуты. Тогда некоторые операции реляционной алгебры можно схематично представить, как показано на рис.25 (серым указывают полученные в результате выполнения операции данные).

 

Операции реляционной алгебры

Выборка (или ограничение)

Обозначение операции: s _{предикат} (R).

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

 

 

Проекция

Обозначение операции: П_{атр1, …, атрN}(R).

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

 

 

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

Обозначение операции: R ´ S.

Операция декартового произведения определяет новое отношение, которое является результатом конкатенации (т.е. сцепления) каждого кортежа из отношения R с каждым кортежем из отношения S.

 

 

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

Как правило, пользователей интересует лишь некоторая часть всех комбинаций кортежей декартового произведения, которая удовлетворяет заданному условию. По­этому вместо декартового произведения обычно используется одна из самых важных операций реляционной алгебры — операция соединения. В результате ее выполнения на базе двух исходных отношений создается некоторое новое отношение. Операция соединения является производной от операции декартового произведения, так как она эквивалентна операции выборки из декартового произведения двух операндов-отношений тех кортежей, которые удовлетворяют условию, указанному в предикате соединения. С точки зрения эффективной реализации в реляционных СУБД, эта операция является одной из самых трудных и часто оказы­вается одной из основных причин, вызывающих проблемы с производительностью, свойственные всем реляционным системам.

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

· Тета-соединение (q-join);

· Соединение по эквивалентности (equi-join), которое является частным видом тета-соединения;

· Естественное соединение (natural join);

· Внешнее соединение (outer join);

· Полусоединение (semi-join).

Тета-соединение (q-join)

Обозначение операции: .

Операция тета-соединения определяет отношение, которое содержит кортежи из декартового произведения отношений R и S, удовлетворяющие предикату F. Предикат F имеет вид R.a_i q S.b_i, где вместо q может быть указан один из операторов сравнения (<, <=, >, >=, = или ~=).

Обозначение тета-соединения можно переписать на основе базовых операций выборки и декартового произведения: .

Так же, как и в случае с декартовым произведением, степенью тета-соединения называется сумма степеней операндов-отношений R и S. Если предикат F содержит только оператор равенства (=), то соединение называется соединением по эквивалентности (equi-join).

Пример. Создать список всех съемщиков, которые осматривали объекты недвижимости с указанием их имен и сделанных ими комментариев:

П_{СкNo,Имя, Фамилия}(Съемщик) П_{СкNo,ЖNo,Комментарий}(Осмотр).

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

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

Обозначение операции: .

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

Степенью естественного соединения называется сумма степеней операндов-отношений R и S минус количество атрибутов x.

Внешнее соединение

Обозначение операции: .

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

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

Для обозначения отсутствующих значений во втором отношении используется определитель NULL. Внешнее соединение становится все более распространенным в реляционных СУБД, к тому же в настоящее время оно является оператором, включенным в новый стандарт SQL. Преимуществом внешнего соединения является то, что при таком соединении сохраняется исходная информация, т.е. внешнее соединение сохраняет кортежи, которые были бы утрачены при использовании других типов соединения.

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

Пример. Пусть даны два отношения T₁, T₂:

Т1 A B C a1 b1 C1 a2 b2 C2 a3 b3 C3 a4 b4 c4	T2 A D E a4 d1 e1 a3 d2 e2 a5 d3 e3 a6 d4 e4
Рис***. Исходные отношения T1, T2

Тогда получаем:

левое внешнее соединение L=T1 T2: A B C D E a1 b1 c1 NULL NULL a2 b2 c2 NULL NULL a3 b3 c3 d2 e2 a4 b4 c4 d1 e1	Пправое внешнее соединение P=Т1 Т2: A B C D E a4 b4 c4 d1 e1 a3 b3 с3 d2 e2 a5 NULL NULL d3 e3 a6 NULL NULL d4 e4
Рис.***. Пример нахождения левого и правого внешнего соединений

Таким образом, можно сделать следующие заключения.

Полное внешнее соединение – это объединение левого и правого внешних соединений, т.е L P.

Естественное соединение – это пересечение левого и правого внешних соединений,
т.е. L  P.