Уважаемые читатели!

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

Всего Вам доброго, Сергей Кузнецов

---

Intelligent Enterprise, No 1, January 1999
Codd's Relational Algebra
C.J. Date
(www.intelligententerprise.com/990501/online.shtml)

Статья Кодда "о полноте" может быть источником недопонимания "простых данных" в реляционных системах.

В 1972 г. Кодд опубликовал еще одну знаменитую статью "Relational Completeness of Data Base Sublanguages" [3]. Заметим, что теперь он говорит о "базах данных", а не о "банках данных", хотя и не объединяет database в одно слово. (Это продолжалось до 1979 г.) В этой статье Кодд приводит формальные определения и реляционной алгебры, и реляционного исчисления; он также определяет понятие реляционной полноты, приводит алгоритм преобразования произвольного выражения исчисления в эквивалентное алгебраическое выражение (доказывая тем самым, что реляционная алгебра реляционно полна) и приводит аргументы в пользу исчисления как основы практического языка баз данных. Достаточно много для такой сравнительно короткой статьи (всего 36 страниц плюс аннотация).

Обзор

Эта статья - которую я буду теперь называть "статьей о полноте" - является, по всей видимости, наиболее формальной статьей Кодда. Определенно, она наиболее трудна для среднего читателя. Однако она фундаментальна, поскольку обобщает материал первых двух статей [1, 2], определяя то, что теперь мы считаем исходным реляционным образом действий.

Подобно предшествующим статьям [1, 2], в статье о полноте по-прежнему полагается, что реляционная модель содержит только структурные аспекты: "В предыдущих статьях ... мы предложили реляционную модель данных ..." пишет Кодд. "[Теперь] мы определяем набор операций над отношениями ...". Другими словами, эти операции не считаются частью самой реляционной модели. Конечно, сегодня мы считаем эти операции составной частью модели; в статье о полноте предлагаются альтернативные, но эквивалентные формализмы для этой части.

Что достигается в статье о полноте? Цитируем аннотацию: "В близком будущем мы можем ожидать появления величайшего разнообразия [предложений языков баз данных]. В этой статье [обеспечивается] теоретический базис, который может использоваться для определения того, насколько полные возможности выборки предоставляются в [таком языке]". Этим теоретическим базисом является "реляционная полнота" из названия статьи; язык является реляционно полным, если он обладает такой же мощностью, что и реляционное исчисление (говоря несколько вольно). Позже в статье Кодд категорически заявляет, что любой язык баз данных общего назначения должен обладать не меньшей мощностью; в частности, он отмечает, что используя такой язык вы должны иметь возможность формулировать запросы без использования "программных циклов и любых других видов ветвления - важное соображение для работы с базой данных с терминала" (и как мы все теперь знаем, для доступа из прикладных программ).

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

Статья состоит из пяти основных разделов:

• Введение
• Реляционная алгебра
• Реляционное исчисление
• Редукция
• Сравнение исчисления и алгебры

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

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

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

В соответствии с Chambers Twentieth Century Dictionary алгебра - это "некоторая система, в которой используются символы и осмысленным образом применяются связи и операции". Более конкретно, алгебра состоит из набора объектов и набора операций, удовлетворяющих некоторым аксиомам или законам (таким, как замкнутость, коммутативность или ассоциативность). Слово "алгебра" в конечном счете происходит от арабского "al-jebr", означающего сборку (чего-либо разобранного) или комбинирование.

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

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

Для "удобства обозначений и пояснений" в статье Кодда предполагается, что "домены отношений" - на самом деле он имеет в виду атрибуты или столбцы - идентифицируются порядковой позицией, а не именем (хотя он понимает, что на практике лучше использовать имена). В результате он не ставит вопрос об именах столбцов результата, что является важным аспектом замкнутости, и не обсуждает потребность в операции переименования столбца. (Подробное обсуждение этих проблем см. в [4].) Далее я буду использовать имена столбцов, а не их номера.

В статье - по моему мнению, очень неудачно! -- говорится, что "для целей баз данных достаточно иметь дело с данными, состоящими из целых значений и символьных строк". Это замечание, возможно, могло привести к неправильному пониманию, заключающемуся в том, что реляционные системы могут работать только с такими простыми данными как числа и строки. (В статье также говорится, что "могут включаться другие типы примитивных элементов", но это замечание всего лишь возвращает нас к трудному вопросу о том, чем могут быть "примитивные" или "атомарные" данные [8]). Удивительно то, что в статье нигде не используется предположение о "простоте данных", по крайней мере, каким-либо существенным образом.

Кодд определяет следующие алгебраические операции:

• Декартово произведение
• Объединение, пересечение и вычитание
• O-ограничение
• Проекция
• O-соединение и естественное соединение
• Деление
• Факторизация

Я не собираюсь приводить здесь определения всех этих операций, потому что такие определения можно найти во многих других источниках (см., например, [4]). Однако в комментариях к соответствующим частям раздела я отмечу несколько расхождений между определениями Кодда и теми определениями, которые обычно используются сегодня.

Декартово произведение: Строго говоря, Декартово произведение двух отношений есть множество пар в виде (a, b), где a - это кортеж первого отношения-операнда, а b - кортеж второго отношения-операнда. (Статья о полноте, как кажется, была первой, в которой Кодд использует термин "кортеж" в качестве аббревиатуры для термина "n-кортеж".) Однако для достижения замкнутости мы хотим, чтобы результат являлся отношением. Кодд определяет расширенный вариант Декартова произведения, которое производит множество кортежей, а не множество пар. Более точно, там, где обычное Декартово произведение дало бы пару (a, b), расширенный вариант производит кортеж, состоящий из всех компонентов a вместе со всеми компонентами b. Операция расширенного произведения - в отличие от обычной - коммутативна и ассоциативна, из чего следует, что мы можем однозначно говорить о произведении n отношений для любого n. (Можно даже допустить нулевое значение n, хотя Кодд явно не обсуждает такие возможности.)

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

O-ограничение: "O" означает любую используемую операцию сравнения (=, <). Если A и B - атрибуты отношения R, O-ограничение R на A и B определяется как отношение с теми же атрибутами как у R и содержащее только те кортежи R, для которых условие "A O B" истинно.

Заметим, что это определение отличается от того, которое приводится в [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 г.; мы теперь относимся ко всем отношениям как к нормализованным. "Ненормализованное отношение" является противоречивым сочетанием терминов. Однако на самом деле отношения, включающие значения-отношения, часто являются противопоказанными.

Литература

• E.F. Codd: "Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks." IBM Research Report RJ599 (August 19th, 1969).
• E.F. Codd: "A Relational Model of Data for Large Shared Data Banks." CACM 13, No. 6 (June 1970). Republished in Milestones of Research - Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26, No. 1 (January 1983).
• E.F. Codd: "Relational Completeness of Data Base Sublanguages" (presented at Courant Computer Science Symposia Series 6, "Data Base Systems", New York City, N.Y., May 24th-25th, 1971). IBM Research Report RJ987 (March 6th, 1972). Republished in Randal J. Rustin (ed.), Data Base Systems: Courant Computer Science Symposia Series 6, Englewood Cliffs, N.Y.: Prentice-Hall (1972).
• C.J. Date: "An Introduction to Database Systems (6th edition). Reading, Mass.: Addison-Wesley (1995).
• C.J. Date: "Tables with No Columns". Database Programming & Design 6, No. 3 (March 1993). Republished in Relational Database Writings 1991-1994, Reading, Mass.: Addison-Wesley (1995).
• C.J. Date: "Divide-and Conquer?". Database Programming & Design 7, No. 4 (April 1994). Republished in Relational Database Writings 1991-1994, Reading, Mass.: Addison-Wesley (1995).
• C.J. Date: "Relations Beyond Compare". Database Programming & Design 7, No. 5 (May 1994). Republished (as "Relational Comparisons") in Relational Database Writings 1991-1994, Reading, Mass.: Addison-Wesley (1995).
• C.J. Date: "Nested Relations". Part 1, Database Programming & Design 8, No. 3 (March 1995); Part 2, Database Programming & Design 8, No. 4 (April 1995).