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

Начальный обзор; традиционные операции над множествами; специальные реляционные операции; операции расширения и подведения итогов; операторы обновления; реляционные сравнения.

Формальной основой реляционной модели БД являются реляционная алгебра, основанная на теории множеств и рассматривающая специальные операторы над отношениями, и реляционное исчисление, базирующееся на математической логике.

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

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

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

Основная идея реляционной алгебры состоит в том. Что средства манипулирования отношениями, рассматриваемыми как множества, основаны на традиционных множественных операциях, дополненных некоторыми специфичными операциями для БД.

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

- выборка отношения;

- проекция отношения;

- объединения отношений;

- пересечение отношений;

- вычитание отношений;

- произведение отношений.

- соединение отношений;

- деление отношений.

Эти операции можно объяснить следующим образом:

- результатом выборки отношения по некоторому условию является отношение, которое включает только те кортежи первоначального отношения, которые удовлетворяют этому условию;

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

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

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

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

- при выполнении прямого произведения двух отношений получается отношение, кортежи которого являются сочетанием кортежей первого и второго отношения;

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

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

Помимо вышеперечисленных, есть ряд особых операций, характерных для работы с БД:

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

- операция присваивания позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.

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

Начнем с операции объединения отношений, однако это в равной мере относится к операциям пересечения и вычитания. В реляционной алгебре результатом операции объединения должно являться отношение. Если допустить в реляционной алгебре возможность объединения произвольных двух отношений с разными наборами атрибутов, то результатом такой операции будет множество, однако множество разнотипных кортежей, то есть, вообще говоря, не отношение. Если исходить из требования замкнутости реляционной алгебры относительно понятия отношения, то такая операция объединения является бессмысленной. Это приводит к появлению понятия совместимости отношений по объединению: два отношения совместимы по объединению в том и только в том случае, когда обладают одинаковыми заголовками. Более точно это означает, что в заголовках обоих отношений содержится один и тот же набор имен атрибутов, и одноименные атрибуты определены на одном и том же домене.

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

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

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

Введем ряд операторов. Пусть UNION обозначает операцию объединения, INTERSECT - операцию пересечения, a MINUS - операцию вычитания. Для обозначения операции выборки будем использовать конструкцию A WHERE В, где А - отношение-операнд, а В - простое условие сравнения. Пусть С1 и С2 — два простых условия выборки. Тогда по определению:

A WHERE Cl AMD C2 обозначает то же самое, что и(A WHERE Cl) INTERSECT (A WHERE C2)

A WHERE Cl OR C2 обозначает то же.самое, что и (A WHERE Cl) UNION (A WHERE C2)

A WHERE NOT Cl обозначает то же самое, что и A MINUS (A WHERE Cl) .

С использованием этих определений можно реализовать операции выборки, в которых условием выборки является произвольное булевское выражение, составленное из простых условий с использованием логических связок AND (логическое И), OR (логическое ИЛИ), NOT (логическое НЕ) и скобок.

Операция соединения, называемая иногда соединением по ус­ловию, требует наличия двух операндов - соединяемых отноше­ний и третьего операнда - простого условия. Пусть соединяются отношения А и В. Как и в случае операции выборки, условие со­единения С имеет вид либо (a comp-op b), либо (а соmр-ор const), где а и b - имена атрибутов отношений А и В, const - литерально заданная константа, а соmр-ор - допустимая в данном контексте операция сравнения. Тогда по определению результатом операции соединения является отношение, получаемое путем выпол­нения операции ограничения по условию С прямого произведе­ния отношений А и В.

Имеется важный частный случай соединения - естествен­нее соединение. Операция соединения называется операцией естественного соединения, если условие соединения имеет вид (а = b), где а и b - атрибуты разных операндов соединения. Этот случай важен потому, что он особо часто встречается на практике и для него существуют эффективные алгоритмы реа­лизации в СУБД. Операция естественного соединения приме­няется к паре отношений А и В, обладающих общим атрибу­том R, то есть атрибутом с одним и тем же именем и опреде­ленным на одном и том же домене. Пусть ab обозначает объе­динение заголовков отношений А и В. Тогда естественное со­единение А и В - это спроектированный на ab результат со­единения А и В. Операция естественного соединения не вклю­чается прямо в состав набора операций реляционной алгебры, но она имеет очень важное практическое значение.

Операция деления отношений нуждается в более подробном объяснении, поскольку наиболее трудная для понимания. Пусть заданы два отношения - А и В. Будем полагать, что атрибут b, отношения А и атрибут b, отношения В обладают одним и тем же именем и определены на одном и том же домене. Назовем мно­жество атрибутов {aj} составным атрибутом а, множество атри­бутов {bj} - составным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения А(а,b) на унарное отношение В(b).

Результатом деления А на В является унарное отношение С(а), состоящее из таких кортежей v, что в отношении А имеются кортежи <v, w>, которые во множестве значений {w} включают множество значений атрибута b в отношении В.

Поскольку деление наиболее трудная операция, поясним ее примером. Пусть в БД студентов имеются два отношения: СТУ­ДЕНТЫ (ФИО, НОМЕР) и ИМЕНА (ФИО), причем унарное от­ношение ИМЕНА содержит все фамилии, которыми обладают студенты института. Тогда после выполнения операции реляци­онного деления отношения СТУДЕНТЫ на отношение ИМЕНА будет получено унарное отношение, содержащее номера студен­ческих билетов, принадлежащих студентам со всеми возможны­ми в этом институте фамилиями.