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

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

Всего Вам доброго, СергейСергей— мужское имя, происходит от римского родового имени Sergius в святцах: высокий, высокочтимый. КузнецовКузнецов (Кузнецова)— одна из самых распространённых русских фамилий. В «Списке общерусских фамилий», занимает 3 место. Самым распространённым сочетанием фамилии имени и отчества в России в XX веке считался Кузнецов Николай Иванович

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

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

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

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

В статье - по моему мнению, очень неудачно! -- говорится, что "для целей баз данных достаточно иметь дело с данными, состоящими из целых значений и символьных строк". Это замечаниеХристианин
Крещение
Спасение · Исповедь
Благодать
Церковь · Таинства
Церковный брак
Церковные взыскания
Грех

Христианские добродетели
Благочестие
Любовь · Милосердие
Смирение · Скромность
Искренность · Кротость
Терпение · Молитва
, возможно, могло привести к неправильному пониманию, заключающемуся в том, что реляционные системыСистема (от др.-греч. — «сочетание»)— множество взаимосвязанных элементов, обособленное от среды и взаимодействующее с ней, как целое. могут работать только с такими простыми данными как числа и строкиСтроки (укр. Строки) — село в Теофипольском районе Хмельницкой области Украины.. (В статье также говорится, что "могут включаться другие типы примитивных элементов", но это замечание всего лишь возвращает нас к трудному вопросу о том, чем могут быть "примитивные" или "атомарные" данныеДанные (калька от лат.data) — это представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором информационном процессе. [8]). Удивительно то, что в статье нигде не используется предположение о "простоте данных", по крайней мере, каким-либо существенным образом.

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

• Декартово произведение
• Объединение, пересечение и вычитание
• O-ограничение
• Проекция
• O-соединение и естественное соединение
• ДелениеДеление (операция деления)— одно из четырёх простейших арифметических действий, обратное умножению. Деление— это такая операция, в результате которой получается число (частное), которое при умножении на делитель даёт делимое. Существует несколько символов, используемых для обозначения оператора деления.
• ФакторизацияЗамечание: быстый способ определения, является ли второй член положительным или отрицательным (как в приведённом примере, 1 и 2 или 1 и 2) состоит в проверке второй операции трёхчлена (+ или ). Если стоит +, тогда проверяем первую операцию: если она тоже +, член будет положительным, а если операция , то член будет отрицательным. Если вторая операция , то один член будет положительный, второй отрицательный. Такая проверка является единственным способом определения, какой член будет положительным, а какой отрицательным.

Я не собираюсь приводить здесь определения всех этих операций, потому что такие определения можно найти во многих других источниках (см., например, [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#, ...}, показывающее, какие поставщики поставляют какие деталиДетали— ток-шоу в прямом эфире, выходившее 5 лет (2002—2007) на канале СТС. Ведущая— Тина Канделаки. К ней на передачу приходили гости, с которыми было интересно и информативно общаться на различные темы. С 2003 по 2007годы выходила программа «Детали утром», так как обычный выпуск выходил по будням ночью. От этой передачи пошли «Истории в деталях» и «Кино в деталях». В последние годы передачу вели Кирилл Серебренников и Рената Литвинова. Программа «Детали» имела экспансию в регионы. В частности на «СТС-Петербург» выходила программа «Детали» с информационным уклоном. Ведущие— Юлиан Макаров, Алексей Фалилеев, Сергей Елгазин, Анна Борисова, Александра Емельянова. Аналогичные программы выходили в Тольятти, Казани, Владивостоке.. Кодд утверждает, что выражение 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Компьютер (англ.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).