Дорогие друзья!

В декабрьском номере журнала Intelligent Enterprise Крис Дейт завершил публикацию своей серии из трех заметок, посвященных первым двум статьям Эдгара Кодда про реляционную модель данных. В завершающей заметке Дейт анализирует одну из наиболее известных статей Кодда, напечатанную в 1970-м году в журнале Communications of the ACM (в 1995 г. перевод этой статьи был опубликован в разделе "Первоисточники" журнала "СУБД). Весьма рекомендую всем прочитать первоисточник и любопытные и познавательные заметки Кристофера Дейта.

С уважением, Сергей Кузнецов

---

Intelligent Enterprise

Vol. 1, No 3, December 1998

The Birth of the Relational Model (Part 3 of 3)

C.J. Date

Оригинал статьи можно найти по адресу http://www.intelligententerprise.com/9812/online1.shtml

В прошлом месяце я завершил свой ретроспективный обзор самой первой статьи Кодда, посвященной реляционному подходу. Теперь я хочу обратиться к следующей по счету статье "A Relational Model of Data for Large Shared Data Banks", вероятно, самой знаменитой статье в истории управления базами данных. Она появилась в Communications of the ACM на следующий год после выхода первой статьи. Как я объяснял в начале этой серии, вторая статья являлась прежде всего пересмотренным вариантом первой, но в ней были введены дополнительные понятия, которые заслуживают комментария.

Статья 1970-го года

Статья 1970-го года состоит из двух основных частей, разбитых на разделы следующим образом:

1. Реляционная модель и нормальная форма
   1.1. Введение
   1.2. Зависимости данных в существующих системах
   1.3. Реляционное представление данных
   1.4. Нормальная форма
   1.5. Некоторые лингвистические аспекты
   1.6. Выражаемые, именованные и хранимые отношения
2. Избыточность и согласованность
   2.1. Операции над отношениями
   2.2. Избыточность
   2.3. Согласованность
   2.4. Заключение

По сравнению со статьей 1969-го года появились два существенных новых разделов: 1.2 и 1.4. Кроме того, раздел статьи 1969-го года "Производность, избыточность и согласованность" разбит на два (2.2 и 2.3) и добавлено заключение. Обратите внимание на изменение направленности статьи, о чем свидетельствует изменение название (и аннотации) и появление нового раздела 1.2; в статье 1969-го года подчеркивалась значимость понятий избыточности данных и связанных с этим аспектов, а новая статья концентрируется на реляционной модели как таковой, в особенности на полезности этой модели для обеспечения независимости данных (понимая, прежде всего, физическую независимость данных). Обсуждаются также польза и преимущества отношений, введенных в статье 1969-го года.

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

Зависимости данных в существующих системах

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

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

Это говорит о том, как далеко мы ушли! С точки зрения пользователей решением проблемы зависимости от упорядочивания (в терминах SQL) является раздел ORDER BY; пользователи не ограничены предопределенным упорядочиванием, а в состоянии потребовать в динамике любое желательное упорядочивание. И если пользователи требуют упорядочивания, не отражаемого напрямую в хранимом варианте данных, то система должна быть в состоянии динамически сортировать или индексировать данные.

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

Подобно этому, решение проблемы зависимости от путей доступа заключается в том, чтобы исключить все пути доступа из пользовательского представления данных (как делается в реляционных системах, но не в системах типа IMS и IDS). Современных читателей может озадачить проводимое Коддом различие между зависимостями от индексации и от путей доступа; в конце концов, индекс - это всего лишь специальный случай пути доступа. Однако вот что имел в виду Кодд: данные, которые пользователь видит в иерархической или сетевой системе, включают некоторые конструкции (иногда зазываемые связями - links), которые -- неважно, что говорят их защитники -- на самом деле, были действительно путями доступа. Эти пути неизменно служили и путями физического доступа. Например, если такой "логический" путь доступа удалялся, то некоторые приложения могли бы перестать работать.

Нормальная форма

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

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

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

Как кажется, второе утверждение является первым явным упоминанием Кодда того факта, что реляционная модель строго исключает использование указателей -- факта, который, как вы должны знать, впоследствии стал предметом многих споров. "Применение реляционной модели данных ... дает возможность разработки универсального подъязыка данных, основанного на прикладном исчислении предикатов. Если набор отношений находится в нормальной форме, оказывается достаточным исчисление предикатов первого порядка." Это важный момент! -- и в нем отражается основной отход от статьи 1969-го года, в которой обсуждалось исчисление предикатов второго порядка, а не первого. Для читателей, которые могут быть не знакомы с этими понятиями, позвольте мне сказать (в реляционных терминах) лишь то, что "первый порядок" означает, что мы квантифицируем только строки отношений, а "второй порядок" дает возможность расставлять кванторы над отношениями. Логика первого порядка позволяет формулировать такие запросы как "Существует ли поставщик S1 в отношении поставщиков?" Логика второго порядка дает возможность формулировать запросы типа "Существует ли поставщик S1 в каком-либо отношении?"

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

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

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

Логика, производительность и другие вопросы

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

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

Статья также включает следующее замечание по поводу производительности: "Система данных должна обеспечивать средства трансляции запросов пользователей... в ... эффективные ... действия над текущим хранимым представлением. Для языка данных высокого уровня это представляет сложную техническую проблему. Тем не менее, эта проблема должна быть решена. По мере возрастания числа пользователей, имеющих конкурентный доступ к большому банку данных ответственность за эффективное обеспечение ответов и за расход ресурсов переносится с ... пользователя на систему данных". Пророческие слова! Кодд отмечает необходимость в компоненте оптимизации СУБД и молчаливо полагает, что в этой области могут существовать некоторые интересные исследовательские вопросы.

Кодд обсуждает также ловушку связи (connection trap). "Отсутствие понимания [семантики реляционных операций] привело нескольких разработчиков систем к тому, что можно назвать ловушкой связи . [Например, предположим, что у нас имеется нереляционная система, в которой] каждое описание каждого поставщика связывается указателями с описаниями каждой детали, поставляемой этим поставщиком, и описание каждой детали аналогичным образом связывается с описанием каждого проекта, в котором используется эта деталь. Из этого можно сделать заключение, которое, вообще говоря, является ошибочным: если все возможные детали поставляются данным поставщиком через [соответствующие] детали ... для проектов, в которых используются эти детали, то можно получить законный набор всех проектов, обеспечиваемых деталями от данного поставщика. Такое заключение корректно только в очень специальном случае, когда целевое отношение между проектами и проставщиками по-существу является естественной композицией двух других отношений."

Чтобы попасть в ловушку связи, нам не обязательно иметь указатели; к сожалению, можно создать такую же логическую ошибку и в чисто реляционной системе. И в самом деле, многие авторы критикуют реляционные системы в точности за эту возможность. (См. [5].) Я полагаю, что подобная критика неосновательна, поскольку выдает печальное отсутствие понимания реляционной модели.

Снова применяя принцип уравновешенного вгляда в историю, я замечу, что несмотря на свой заголовок, в статье 1970-го года не предлагаются краткие определения ни термина "реляционная модель", ни термина "модель данных". Это странно, поскольку в статье вводится и это последнее понятие. Напротив, из этой статьи следует, что реляционная модель включает только структурные аспекты; другими словами, исключаются манипуляционный и целостный аспекты. (Часть статьи, называемая "Избыточность и согласованность" включает реляционные операции, но они не включены в часть "Реляционная модель данных и нормальная форма".) Кроме того, в статье идет речь о "реляционной модели ... для банка данных", из чего, к сожалению, следует, что термин "реляционная модель" относится к абстрактному представлению данных в конкретной базе данных, а не означает абстрактное представление данных вообще. Оба упомянутые неправильные представления к прискорбию по-прежнему распространены в литературе о базах данных. Та идея, что "реляционная модель - это всего лишь структура" -- иногда выражаемая в форме "реляционная модель - это только плоские файлы" -- является основным неверным представлением.

Наконец, еще одно замечание из области истории. Недавно мне встретилась статья, датированная 1966 г. (!), с заголовком "A Relational Model for Information Retrieval and the Processing of Linguistic Data" [6]. Статья посвящена проблемам обработки естественных языков, а "реляционная модель" в заголовке - это формализм для представления некоторых английских фраз. Например, фраза "Джон любит Мери" можно было представить выражением "j L m". (Все отношения в статье - бинарные.) Эти идеи имеют точки соприкосновения с реляционной моделью Кодда. (Что естественно, поскольку они базируются на том же логическом основании.) Однако я думаю, что было справедливо сказать, что мы должны отдать должное Кодду за открытие реляционной модели данных в том смысле, как мы теперь ее понимаем.

Литература

1. Codd, E.F. "Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks." IBM Research Report RJ599, August 19, 1969.
2. Codd, E.F. "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. (Перевод на русский язык опубликован в журнале "СУБД", No 1, 1995, www.osp.ru/dbms/1995/01/source/codd.htm).
3. Darwen, Hugh and C.J. Date. "The Third Manifesto." ACM SIGMOD Record 24, No 1, March 1995. (Перевод на русский язык опубликован в журнале "СУБД", No 1, 1996,).
4. Darwen, Hugh. "Relational-Valued Arributes; or, Will the Real First Normal Form Please Stand Up?" in C.J. Date and Hugh Darwen, Relational Database Writings 1989-1991. Addison-Weslwy, 1992.
5. Martin, James. "Semantic Disintegrity in Relational Operations". Fourth-Generation Languages Volume I: Principles . Prentice-Hall, 1985.
6. Bell, Colin J. "A Relational Model for Information Retrieval and the Processing of Linguistic Data". IBM Research Report RC1705, November 3, 1996.