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

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

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

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

Выборка Проекция R S RxS

=

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

Объединение Пересечение Разность (множеств)

R R R

S S S

Деление R¸S

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

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

Проекция

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

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

RxS - Операция декартова произведения определяет новое отношение, которое является результатом конкатенации (т.е. сцепления) каждого кортежа из отношения R с каждым кортежем из отношения S. Операторы выборки и проекции извлекают информацию только из одного отно­шения, но возможно нужны данные из нескольких отношений, тогда предварительно применяется оператор произведения. Он умножает два отношения, что в результате приводит к созданию другого отношения, состоящего из всех возможных пар кортежей обоих отношений. Следовательно, если одно отношение имеет I кортежей и N атрибутов, а другое - J кортежей и М атри­бутов, то отношение с их декартовым произведением будет содержать (IxJ) кортежей и (NxM) атрибутов. Исходные отношения могут содержать атрибуты с одинаковыми именами. В таком случае имена атрибутов будут содержать названия отношений в виде префиксов для обеспечения уникальности имен атрибутов в новом отношении.