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

Реляционная алгебра – это теоретический язык операций, который на основе одного или нескольких отношений позволяет создавать другое отношение без изменения исходных данных [1, 4, 6, 7, 9, 10, 12].

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

Реляционная алгебра является языком последовательного использования отношений, в котором все кортежи, взятые даже из разных отношений, обрабатываются одной командой без организации циклов. Для команд реляционной алгебры предложено несколько вариантов синтаксиса. Далее мы воспользуемся общепринятыми символическими обозначениями для этих команд и представим их в неформальном виде. Более детально этот вопрос для заинтересованных читателей рассмотрен в работах Ульмана (Ullman, 1988).

Существует несколько вариантов выбора операций, которые включаются в реляционную алгебру. Сначала Кодд предложил восемь операторов, но впоследствии к ним были добавлены и некоторые другие. Пять основных операций реляционной алгебры, а именно выборка (selection), проекция (projection), декартово произведение (cartesian product), объединение (union) и разность (set difference), выполняют большинство операций извлечения данных, которые могут представлять для нас интерес. На основании пяти основных операций можно получить дополнительные (соединения (join), пересечения (intersection) и деления (division) рис. 5.1).

Рис. 5.1. Схематическое представление функций операторов реляционной алгебры

Операции выборки и проекции являются унарными, поскольку они работают с одним отношением. Другие операции работают с парами отношений, и поэтому их называют бинарными операциями. В приведенных ниже определениях R и S – это два отношения, определенные над атрибутами A = (a₁, a₂, …, a_n) и B = (b₁, b₂, …, b_n) соответственно. Для иллюстрации результатов выполнения операций мы воспользуемся отношениями БД «БИБЛИОТЕКА» (приложение В).

σпредикат(R)

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

ПРИМЕР 5.1

Составьте список библиотекарей, у которых табельный номер превышает 80.

σ_ClockNumber > 80 (Librarians)

Здесь исходным отношением является отношение Librarians, а предикатом – выражение ClockNumber>80. Операция выборки определяет новое отношение, содержащее только те кортежи отношения Librarians, в которых значение атрибута ClockNumber превышает 80 (табл. 5.1). Более сложные предикаты могут быть созданы с помощью логических операторов AND, OR и NOT.

Таблица 5.1

5.3. Операция проекции

Патр 1, …, атр n (R)

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

ПРИМЕР 5.2

Составьте список библиотекарей с указанием табельного номера (ClockNumber), фамилии (FamilyNamе), имени (Name), отчества (Patronymic) и номера домашнего телефона (HomePhone).

В этом примере операция проекции определяет новое отношение, которое будет содержать только атрибуты ClockNumber, FamilyNamе, Name, Patronymic и HomePhone отношения Librarians, размещенные в указанном порядке (табл. 5.2).

Таблица 5.2

5.4. Операция декартового произведения

R × S

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

Операция выборки и проекции позволяют извлечь информацию только из одного отношения. Возможно возникновение и таких ситуаций, когда нужна некоторая комбинация данных из нескольких отношений. Оператор декартового произведения умножает два отношения. В результате создаётся другое отношения, где есть все возможные пары кортежей обоих отношений. Следовательно, если одно отношение имеет I кортежей и N атрибутов, а другое – J кортежей и M атрибутов, то отношение с их декартовым произведением будет содержать (I × J) кортежей и (N + M) атрибутов. Исходные отношения могут содержать атрибуты с одинаковыми именами. В таком случае одноименные атрибуты будут содержать названия отношений в виде префиксов. Это обеспечит уникальность имен атрибутов в результирующем отношении.

ПРИМЕР 5.3

Создайте список всех читателей, которые когда-либо брали книги в библиотеке, используя следующие атрибуты отношения Readers: Code, FamilyName, Name и отношения BookGiveOutRecord: Code, ReaderCode, InventoryCode.

Результатом выполнения такой операции будет отношение, содержащее 120 кортежей и 6 атрибутов. Приводить его в полном объеме не имеет смысла. Посмотрите на его первые 12 кортежей (табл. 5.3). Первые 10 - все возможные комбинация первого кортежа отношения Readers с десятью кортежами отношения BookGiveOutRecord. Последние два приведены для того чтобы вы сравнили их значение с первыми двумя. Это первые две возможные комбинации второго кортежа отношения Readers с первыми двумя кортежами отношения BookGiveOutRecord. Следующим будет третья возможная комбинации второго кортежа отношения Readers с третьим кортежем отношения BookGiveOutRecord. И так до сто двадцатого кортежа.

Таблица 5.3

В таком виде (120 кортежей) это отношение содержит больше информации, чем необходимо. Например, первый кортеж этого отношения содержит разные значения атрибутов Readers.Code и ReaderCode. Для получения искомого списка (табл. 5.4) необходимо для этого отношения произвести операцию выборки с извлечением только тех кортежей, для которых выполняется равенство Readers.Code = ReaderCode. Полностью эта операция выглядит так, как показано ниже:

Таблица 5.4

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

R ∪ S

Операция объединения отношений R и S с кортежами I и J происходит в результате их конкатенации с образованием одного отношения с максимальным количеством кортежей (I + J), если кортежи-дубликаты исключены. При этом отношения R и S должны быть совместимыми по объединению.

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

ПРИМЕР 5.4

Дайте список фамилии всех пользователей, занесенных в БД.

Для создания совместимых по объединению отношений сначала следует применить операцию проекции, чтобы выделить из отношений Readers и Librarians столбцы с атрибутами FamilyName, исключая в случае необходимости дубликаты. Затем для комбинирования полученных промежуточных отношений следует использовать операцию объединения (табл. 5.5).

Таблица 5.5

R - S

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

ПРИМЕР 5.5

Определите индивидуальные коды читателей, которые ни разу не брали книг в библиотеке.

В этом случае аналогично предыдущему примеру следует создать совместимые по объединению отношения Readers и BookGiveOutRecord, выполнив их проекцию по атрибутам Code и ReaderCode. Далее следует использовать операцию разницы (табл. 5.6).

Таблица 5.6

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

Рассмотрим следующие типы соединений:

1. Тета-соединение (Θ-join).
2. Соединение по эквивалентности (equi-join) - отдельный вид тета-соединения.
3. Естественное соединение (natural join).
4. Внешнее соединение (outer join).
5. Полусоединение (semi-join).

5.7.1. Операция тета-соединения

R►◄FS

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

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

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

ПРИМЕР 5.6

Создайте список читателей, которые когда-либо брали книги в библиотеке (табл. 5.4).

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

5.7.2. Операция естественного соединения

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

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

ПРИМЕР 5.7

Создайте список читателей, которые когда-либо брали книги в библиотеке (табл. 5.7).

Таблица 5.7

5.7.3. Операция внешнего соединения

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

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

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

ПРИМЕР 5.8

Определите индивидуальные коды читателей, их фамилии, имена, отчества и информацию о книгах, которые они брали в библиотеке (табл. 5.8).

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

Таблица 5.8

5.7.4. Операция полусоединения

R►FS	Операция полусоединения определяет отношение, содержащее те кортежи отношения R, которые входят в соединение отношений R и S.

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

Здесь A - набор всех атрибутов в отношении R. На самом деле, это полутета-соединение, причем следует отметить, что существуют полусоединения по эквивалентности и полуестественные соединения.

ПРИМЕР 5.9

Создайте полный отчет, о всех читателей с именем «Дмитрий», которые когда-либо брали книги в библиотеке (табл. 5.9).

Таблица 5.9

R ∩ S

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

Операцию пересечения можно записать, используя операции разницы между отношениями: R ∩ S= R – (R – S).

ПРИМЕР 5.10

Создайте список библиотекарей, которые являются одновременно читателями. Добавить их код паспорта, фамилия, имя и отчество.

Для выполнения условия совместимости отношений по объединению были выполнены соответствующие операции проекции.

Данные, которые входят в отношений «ЧИТАТЕЛИ» и «БИБЛИОТЕКОРИ» (прил. В) свидетельствуют, что результатом их пересечения является пустое множество, то есть ни один из библиотекарей не является читателем.

Операция деления может быть полезной в запросах особого типа, которые очень часто выполняются к БД. Предположим, что отношение R определенное на множестве атрибутов A, а отношение S - на множестве атрибутов B, причем B ⊆ A (т.е. B является подмножеством A). Пусть C =A - B, то есть C является множеством атрибутов отношения R, которое не являются атрибутами отношения S. Тогда определение оператора деления будет таким:

R ÷ S

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

Операция деления эквивалентна ряду других основных операций:

T₁ = П_C(R)

T₂ = П_C((S × T₁) – R)

T = T₁ – T₂

ПРИМЕР 5.11

Создайте список имён, фамилий, отчеств и кодов паспортов читателей, родившихся после 1 декабря 1960 года.

Для решения поставленной задачи сначала необходимо получить отношение R. Для этого выполнена проекция отношения Readers (табл. 5.10). Затем определить отношение S. Для этого получена проекцию отношении PasportData. В нём с помощью оператора выборки найдены все коды паспортов с датой рождения после 31 декабря 1960 года (табл. 5.11). Теперь получим результат деления отношения R на S (табл. 5.12).

Таблица 5.10

Таблица 5.11

Таблица 5.12

1. Какие особенности и свойства реляционной алгебры Вам известны
2. Какие операции реляционной алгебры Вы знаете?
3. Какая существует разница между операциями выборки и проекции?
4. В каком из двух отношений количество атрибутов и кортежей будет больше, если первое является результатом операции декартова произведения отношений R с I кортежей и N атрибутов и S с J кортежей и M атрибутов, а второе - результатом операции объединения тех же отношений?
5. В чем заключается сущность операций реляционной алгебры, которые требуют совместных с объединением исходных отношений?
6. Какие операции реляционной алгебры являются производными от операции декартова произведения?
7. Какой из операторов сравнения превращает Θ-соединения в натуральное?
8. В чем разница между внешним и другими типами соединений?
9. Как формируется отношение, которое является результатом работы известных Вам типов внешних соединений?