Операции реляционной алгебры
В соответствии с Chambers Twentieth Century Dictionary алгебра - это "некоторая система, в которой используются символы и осмысленным образом применяются связи и операции". Более конкретно, алгебра состоит из набора объектов и набора операций, удовлетворяющих некоторым аксиомам или законам (таким, как замкнутость, коммутативность или ассоциативность). Слово "алгебра" в конечном счете происходит от арабского "al-jebr", означающего сборку (чего-либо разобранного) или комбинирование.
В реляционной алгебре объектами являются отношения; определяются такие операции как ограничение, проекция и соединение, и имеется несколько аксиом или законов, включающих замыкание - исключительно важную аксиому. Результатом любой реляционной операции всегда является другое отношение. Как я всегда говорю (например, см. [4]), важным следствием замкнутости реляционной алгебры является возможность составлять вложенные реляционные выражения.
Алгебраические операции предназначены только для чтения. (Все они служат для образования некоторого отношения из других отношений.) Следовательно, они оперируют точно определенным образом над значениями отношений. С точки зрения реляционной алгебры нет нужды в реляционных переменных - и не предполагается их существование. Конечно, в реальном языке баз данных потребуются и операции обновления, а потому также и реляционные переменные, но это не является частью реляционной алгебры.
Для "удобства обозначений и пояснений" в статье Кодда предполагается, что "домены отношений" - на самом деле он имеет в виду атрибуты или столбцы - идентифицируются порядковой позицией, а не именем (хотя он понимает, что на практике лучше использовать имена). В результате он не ставит вопрос об именах столбцов результата, что является важным аспектом замкнутости, и не обсуждает потребность в операции переименования столбца. (Подробное обсуждение этих проблем см. в [4].) Далее я буду использовать имена столбцов, а не их номера.
В статье - по моему мнению, очень неудачно! -- говорится, что "для целей баз данных достаточно иметь дело с данными, состоящими из целых значений и символьных строк".
Это замечание, возможно, могло привести к неправильному пониманию, заключающемуся в том, что реляционные системы могут работать только с такими простыми данными как числа и строки. (В статье также говорится, что "могут включаться другие типы примитивных элементов", но это замечание всего лишь возвращает нас к трудному вопросу о том, чем могут быть "примитивные" или "атомарные" данные [8]). Удивительно то, что в статье нигде не используется предположение о "простоте данных", по крайней мере, каким-либо существенным образом.
Кодд определяет следующие алгебраические операции:
Я не собираюсь приводить здесь определения всех этих операций, потому что такие определения можно найти во многих других источниках (см., например, [4]). Однако в комментариях к соответствующим частям раздела я отмечу несколько расхождений между определениями Кодда и теми определениями, которые обычно используются сегодня.
Декартово произведение: Строго говоря, Декартово произведение двух отношений есть множество пар в виде (a, b), где a - это кортеж первого отношения-операнда, а b - кортеж второго отношения-операнда. (Статья о полноте, как кажется, была первой, в которой Кодд использует термин "кортеж" в качестве аббревиатуры для термина "n-кортеж".) Однако для достижения замкнутости мы хотим, чтобы результат являлся отношением. Кодд определяет расширенный вариант Декартова произведения, которое производит множество кортежей, а не множество пар. Более точно, там, где обычное Декартово произведение дало бы пару (a, b), расширенный вариант производит кортеж, состоящий из всех компонентов a вместе со всеми компонентами b. Операция расширенного произведения - в отличие от обычной - коммутативна и ассоциативна, из чего следует, что мы можем однозначно говорить о произведении n отношений для любого n. (Можно даже допустить нулевое значение n, хотя Кодд явно не обсуждает такие возможности.)
Объединение, пересечение, вычитание: Эта статья была первой, в которой обращалось внимание на специальные реляционные варианты этих операций. Требовалась "совместимость по объединению" операндов (опять же, чтобы результат всегда являлся отношением). Объединение и пересечение (но не вычитание) коммутативны и ассоциативны.
O-ограничение: "O" означает любую используемую операцию сравнения (=, Заметим, что это определение отличается от того, которое приводится в [2].
Заметим также, что допускаются "составные" атрибуты - например, простые атрибуты STREET, CITY. STATE и ZIP можно рассматривать как составной атрибут ADDR - хотя Кодд не поднимает вопрос о том, что означает сравнение "A < B", если A и B - составные в этом смысле атрибуты.
Проекция: Кодд делает важное замечание о том, что проекция представляет собой алгебраического двойника квантора существования реляционного исчисления.
Замечание: В статье предполагается, что результатом проекции отношения R на пустой набор атрибутов является R. Это соглашение неудачно, поскольку результатом такой проекции должно быть отношение нулевой степени - конкретно, TABLE_DEE или TABLE_DUM [5].
O-соединение и естественное соединение: Кодд определяет естественное соединение в терминах O-соединения (более точно, как проекцию эквисоединения). Сегодня у нас имеется тенденция относиться к естественному соединению как к более фундаментальной операции (настолько фундаментальной, что неуточненный термин "соединение" обычно используется в смысле естественного соединения). Действительно, вы могли бы заметить, что "O-соединения" даже и не упоминались в первых двух статьях Кодда [1, 2]. Далее, Кодд отмечает, что можно определить O-соединение в терминах O-ограничения, так что это не примитивная операция. (На самом деле, верно и обратное - т.е. можно определить O-ограничение в терминах O-соединения. Выбор набора примитивных операций в некоторой степени произвольно зависит от нашей позиции.
В один из общепринятых наборов примитивов входят ограничение, проекция, произведение, объединение и вычитание.) Подобно операциям (расширенного) произведения, объединения и пересечения, естественное соединение коммутативно и ассоциативно.
Деление: В статье о полноте впервые упоминалась эта операция. В действительности, понятно, что Кодд ввел ее как "алгебраического двойника квантора всеобщности". Он говорит, что операция не является примитивной; ее можно определить в терминах уже описанных операций. (На самом деле, определение не совсем такое, какое мы используем сегодня, но различия незначительны. Можно определить вариант операции - отличающийся от определяемого в статье - допускающий деление любого отношения на любое другой; см. [6].)
Не интересует ли вас, почему операция называется "делением"? Причину демонстрирует следующее тождество:
( R TIMES S ) DIVIDEBY S = R
Деление - это операция, в некотором смысле обратная Декартову произведению, и это не только двойник квантора существования, чем, как казалось, она являлась. С операцией связаны проблемы пустых множеств и связанные с ними [6]. На самом деле, Кодд предлагает пример, иллюстрирующий проблему: Пусть имеется отношение SP {S#, P#, ...}, показывающее, какие поставщики поставляют какие детали. Кодд утверждает, что выражение SP {S#, P#} DIVIDEBY SP {P#} выдаст номера поставщиков, поставляющих все детали. Однако, если не имеется никаких деталей, это выражение выдаст неверный результат. (Не будет выдано ни одного номера поставщика, хотя следует выдать их все.)
Более хорошую основу для обхождения с теми разновидностями проблем, для решения которых было предназначено реляционное деление, дают реляционные сравнения - но исходная реляционная модель, определенная Коддом, вообще не включает таких сравнений [7].
Факторизация: Эта операция (сегодня более часто называемая гнездованием [nesting]) преобразует нормализованное отношение в ненормализованную форму. Например, для заданного отношения EMP с атрибутами EMP# и DEPT# можно было бы использовать эту операцию для получения ненормализованного отношения с атрибутами DEPT# и SET_OF_EMPS, в котором каждый кортеж содержит номер отдела и множество всех соответствующих номеров служащих.Эта операция не используется в основной части статьи; Кодд выносит ее в приложение, полагая, что это может быть полезно "для целей презентации". Наше понимание истинной природы нормализации нормализации улучшилось с 1971 г.; мы теперь относимся ко всем отношениям как к нормализованным. "Ненормализованное отношение" является противоречивым сочетанием терминов. Однако на самом деле отношения, включающие значения-отношения, часто являются противопоказанными.
