Введение

Сейчас язык SQL является стандартным языком реляционных (и не только чисто реляционных!) СУБД. Интерфейсы, основанные на SQL, поддерживаются почти во всех используемых СУБД, далеко не все из которых первоначально разрабатывались как реляционные системы. Язык SQL является реляционно-полным [1], что является основанием для его применимости в БД, основанных на реляционной модели, имеющей твердое обоснование, начиная с работ д-ра Кодда [1]. Вместе с тем, язык SQL не является “полностью реляционным”, многие его черты, начиная с самых первых его вариантов, противоречили принципам реляционной модели данных, заложенным Коддом. Не сильно выступая против истины, сделаем утверждение, что спецификация языка SQL, по своей сути, является завершенной спецификацией модели данных, которая в практических приложениях сегодня играет роль суррогата реляционной модели.

Однако, раз уж мы упомянули о реляционной модели, нам придется кратко описать ее суть, причем мы сделаем это исходя из современных представлений.

Что представляет собой реляционная модель

Реляционный подход к организации баз данных был заложен в конце 1960-х гг. д-ром Эдгаром Коддом в его знаменитой работе "A Relational Model of Data for Large Shared Data Banks" [1]. В то время Кодд писал, что реляционный подход состоит из "четырех основных компонентов":

1. До предела упростить типы структур данных, используемых в принципиальной схеме (или общем представлении)
2. Ввести мощные операции, обеспечивающие и программистов и непрограммистов возможностями хранения и выборки данных без потребности "навигации"
3. Ввести диалоговую поддержку естественного языка (например, английского) для обеспечения эффективного взаимодействия с базой данных случайных (возможно, далеких от мира компьютеров) пользователей
4. Выражать требования авторизации и ограничения целостности отдельно от структур данных (поскольку они подвержены изменениям).

И добавлял, что обсуждения реляционного подхода часто замыкаются на первом из них в ущерб остальным трем. Для обоснования этого подхода все четыре компонента должны рассматриваться в одном пакете" [2].

В дальнейшем ходе работы Кодда его представления о несколько менялись изменялись, что отражалось в последующих статьях Кодда. В конце 80-х он потратил много времени на пересмотр и расширение исходной реляционной модели, которую он назвал “реляционной моделью версии 1” (RM/V1). Версия 2 реляционной модели (RM/V2) была опубликована им в работе [3].

Все это дало возможность Майклу Стоунбрейкеру заметить [4], что "можно видеть четыре разных версии" модели Кодда:

• Версия 1: Определена в статье в CACM в 1970 г. [1]
• Версия 2: Определена в статье по поводу Тьюринговской премии в 1981 г.
• Версия 3: Определена 12-ю правилами Кодда и оценочной системой [5]
• Версия 4: Определена в книге Кодда [3].

Дальнейшее развитие модели связано с именем одного из крупнейших специалистов по БД Кристофера Дейта, и, в последнее время, его соавтора Хьюго Дарвена. Дейтом был предложен свой вариант реляционной модели, отталкивающийся от RM/V1, в работах [6,7]. Последняя на сегодняшний день и наиболее полная версия реляционной модели опубликована в ряде работ Дейта и Дарвена под названием “Третий Манифест” [8-10].

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

Реляционная алгебра Дейта и Дарвена

Переосмысляя положения классической реляционной алгебры Кодда, Дейт и Дарвен пришли к, как они считают, более логичной (в математическом смысле) формулировке реляционной алгебры, названной ими “Алгеброй А” [10].

Название A представляет собой двойной рекурсивный акроним от ALGEBRA, что дополнительно раскрывается авторами Манифеста как A Logical Genesis Explains Basic Relational Algebra. Как видно из развернутого названия, алгебра A построена таким образом, чтобы подчеркнуть, возможно, более отчетливо, чем это получалось в предыдущих алгебрах, насколько тесно реляционная алгебра связана с дисциплиной логики предикатов.

Базисом предложенной Кристофером Дейтом и Хьюго Дарвеном Алгебры A являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения, объединения отношений и т. д. Путем комбинирования базовых операций выражаются операции переименования атрибутов, соединения общего вида, взятия разности отношений. Алгебра A позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Кодда. Даже сами авторы Алгебры A, Дейт и Дарвен, в своем учебном языке Tutorial D используют не Алгебру A напрямую, а некоторое ее надмножество, в большей степени напоминающее алгебру Кодда.

Отметим особо, что в Алгебре А отсутствуют понятия совместимости по операциям, присущее РА Кодда, что делает Алгебру А алгеброй в математическом смысле.

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

Реляционная модель “Третьего Манифеста”

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

Начнем с того, что переосмыслению подверглось само понятие “база данных”. Если во времена RM/V1 БД трактовалась как некоторое множество отношений, что делало БД статическим объектом, то Дейтом [10] разделены понятия отношения и “переменной отношения” (relvar), изменяющейся со временем, и БД трактуется как набор переменных отношений, что подчеркивает ее изменчивость.

В РМ Кодда существовало понимание того, что РМ имеет дело только с простыми встроенными типами данных, такими как числа или строки. Значения переменных этих типов данных и понимались как атомарные в контексте первой нормальной формы. В [10] по этому поводу отмечается, что в РМ нигде не устанавливается, какие типы разрешены, и это позволяет включить развитую систему типов данных, или доменов. Понятие домена в реляционной модели [10] полностью отождествляется с понятием типа данных. (Однако понятие домена в реляционной модели и в языке SQL – различно)

Соответственно атомарными в контексте 1 НФ считаются типизированные значения, причем они могут принадлежать типам данных произвольной сложности, включая ТД, определенные пользователем.

Рассмотрим этот вопрос подробнее. В РМ Третьего Манифеста [10], отношение состоит из заголовка и тела, где заголовок – это заголовок кортежа, согласно его определению, а тело – множество кортежей, соответствующих этому заголовку. Каждое отношение по определению содержит в точности одно значение для каждого атрибута в каждом кортеже своего тела. Другими словами, любое отношение по определению находится в 1 НФ.

В классической интерпретации реляционной модели 1 НФ часто неформально трактовали как “никаких отношений внутри отношений”. Дейт и Дарвен, однако, отмечают [10], что, в сущности, 1 НФ прежде никогда не определялась очень точно, поскольку опиралось на понятие атомарности значения данных, которое тоже не определялось достаточно точно. Соответственно, определив понятие атомарности через типизацию, Дейт и Дарвен вполне допускают, чтобы отношение включало атрибуты, значениями которых являются кортежи и даже отношения.

Поддержка пользовательских ТД включает поддержку определяемых пользователями операций и поддержку наследования ТД (подтипы и супертипы).

NULL - проблема

Одной из наиболее серьезных теоретических проблем реляционной модели была проблема представления отсутствующей информации. Кодд предложил подход к ее решению, ныне широко известный практикам баз данных. Для представления отсутствующей информации используются специальные маркеры, называемые NULL - значениями. Идея заключается в следующем: если данный кортеж имеет NULL – маркер в данной позиции атрибута, то это означает, что в таком кортеже значение атрибута по некоторой причине отсутствует (причины этого могут быть различны, например, “отсутствует” или “не применимо”).

В свою очередь, Дейт и Дарвен подвергают критике такой подход, в частности, указывая, что “NULL – значения” вообще не являются реальными значениями в обычном смысле этого термина (это не то же самое, что, например, пробелы или числовые нули).

Попробуем кратко проследить логику рассуждений Дейт и Дарвена.

Рассмотрим подробнее семантику неопределенных значений. Результатом скалярных операций сравнения, в которых хотя бы один из операндов является величиной NULL, будет логическое значение unknown.

Приведем другой пример. В определение столбца может входить одно из ограничений: ограничение первичного ключа (PRIMARY KEY) или ограничение возможного ключа (UNIQUE). Включение в определение столбца любого из этих ограничений означает требование уникальности значений определяемого столбца, т. е. во все время существования определяемой таблицы во всех ее строках значения данного столбца должны быть различны. В этом случае SQL опирается на семантику неопределенных значений, отличную от используемой в большинстве других случаев. Считается, что (NULL = NULL) = true и что (a = NULL) = (NULL = a) = false для любого значения a, отличного от NULL.

Третий пример. Вычисление функции COUNT(*) производится путем подсчета числа строк в заданном мультимножестве. Все строки считаются различными, даже если они состоят из одного столбца со значением NULL во всех строках. Это еще один вид различения строк в SQL и еще одна скрытая интерпретация неопределенного значения. COUNT(*) работает так, как если бы выполнялось соотношение (NULL=NULL) = false.

Тем самым, в SQL применяются все три возможных интерпретации NULL. При вычислении логических выражений полагается (NULL=NULL) = unknown; при определении строк-дубликатов неявно считается, что (NULL=NULL) = true; наконец, при вычислении агрегатной функции COUNT(*) неявно полагается, что (NULL=NULL) = false.

Критика Дейтом и Дарвеном подхода, основанного на использовании NULL – значений, основывается на следующей логике. Значение, по определению, является элементом некоторого домена. Пусть имеется домен, один из элементов которого мы решили представить символом NULL. Но тогда мы должны определить все операции, которые доступны в связи с этим доменом, включая, конечно, операцию сравнения. Но есть одна вещь, которую запрещено делать: это говорить, что NULL является чем-то отличным от этого символа. То есть говорить, что сравнение NULL = NULL когда-либо возвращает что-либо, кроме true. И “что-либо, кроме true” может быть “что-либо, кроме false” [10]. И, как только мы понимаем, что NULL не являются значениями, считают Дейт и Дарвен, оказывается, что “отношения”, содержащие NULL, вовсе не являются отношениями, как они определены в реляционной модели, и, используя их, мы тем самым отказываемся от реляционной модели. Таким образом, NULL разрушают реляционную модель, и должны быть оттуда исключены.

В результате Дейт и Дарвен приходят к выводу, что наличие в реляционной модели NULL-значений разрушает реляционную модель и теоретически неприемлемо. В Третьем Манифесте [10] NULL-значения не поддерживаются.

Те, кто помнят институтский курс теории реляционных баз данных, скорее всего, согласится с обоснованностью такой критики, но вместе с тем, те, кто сталкивается с реляционными БД на практике, обязательно потребуют представить альтернативное применению NULL – значений решение. Дейт и Дарвен действительно предоставляют альтернативное решение, которое мы и попытаемся продемонстрировать.

Горизонтальная декомпозиция

Поясним сущность метода. Широко распространенный метод декомпозиции отношений, основанный на 1 – 5 НФ, БКНФ и даже 6 НФ, введенной в работе [13], заключается в декомпозиции отношений на два или более отношений таким образом, что предикат, соответствующий первоначальному отношению, “разбивается” с помощью удаления конъюнкций. Обратный оператор соединения таблиц JOIN – это реляционный аналог логического оператора AND (конъюнкции). Грубо говоря, “линии”, разделяющие отношение, расположены вертикально между атрибутами отношения. Назовем такую декомпозицию вертикальной.

Рассуждая по аналогии, можно предположить способ декомпозиции такой, что предикат, соответствующий первоначальному отношению, “разбивается” с помощью удаления дизъюнкций. Тогда реляционным аналогом логического оператора OR (дизъюнкции) будет оператор UNION. В этом случае “линии”, разделяющие отношение, расположены горизонтально между кортежами отношения. Назовем такую декомпозицию горизонтальной.

Как мы уже отмечали, отсутствующая информация может быть нескольких различных видов, например, “неизвестно”, “отсутствует” и “не применимо”, которые в настоящее время обозначаются одним способом с помощью маркера NULL. С помощью горизонтальной декомпозиции отношение, содержащее отсутствующую информация различного рода, декомпозируется на несколько отношений, одно из который не содержит отсутствующей информации, второе – содержит значения “не применимо”, третье – “отсутствует”, четвертое - “неизвестно” и т.д. Обратная композиция в “традиционный’ вид осуществляется с помощью оператора UNION. Поясним на примере некоторой ведомости, приведенном на рис. 1.

Как видно из примера, таблица содержит два вида отсутствующей информации - “неизвестно” в случае с должностью Семенова и размером жалования Борисова, и “не применимо” в случае должности и жалования Давиденко (по условиям задачи, он - безработный).

Предикат отношения PERSONAL_INFO мог бы выглядеть так: “человек, идентифицируемый как 1034, имеет фамилию Анин, занимает должность юриста и имеет жалование 100 000 руб.”. В то же время предикат “человек, идентифицируемый как 1036, имеет фамилию Семенов, занимает должность ? и имеет жалование 50 000 руб.” не имеет явного смысла. Кроме того, неизвестно даже точно, какому типу данных принадлежит этот “?”, поскольку, как отмечают Дейт и Дарвен, NULL не принадлежит никакому домену (типу данных), и не является значением в общепринятом контексте этого понятия.

Первая стадия включает вертикальную декомпозицию этого отношения, как показано на рис. 2.

Теперь отношение PERSONAL_INFO декомпозировано на три отношения: CALLED, DOES_JOB, EARNS. Каждое из полученных в результате отношений характеризуется определенным предикатом. Предикат отношения CALLED выглядит так: “человек, идентифицируемый как ID, имеет фамилию NAME ”. Предикат отношения DOES_JOB : “человек, идентифицируемый как ID, занимает должность JOB ”. Предикат отношения EARNS: “человек, идентифицируемый как ID, имеет жалование SAL”. Но предикаты отношений DOES_JOB и EARNS все еще не до конца приемлемы.

Вторая стадия – горизонтальная декомпозиция (рис. 3, 4).

В окончательном варианте нами получены отношения DOES_JOB, JOB_UNK, UNEMPLOYED, EARNS, SAL_UNK, UNSALARIED, удовлетворяющие реляционной модели Третьего Манифеста [10]. Им соответствуют предикаты: “человек, идентифицируемый как ID, занимает конкретную должность JOB”, “ человек, идентифицируемый как ID, занимает некоторую должность, но мы не знаем, какую”, “ человек, идентифицируемый как ID, является безработным”, “ человек, идентифицируемый как ID, имеет определенное жалование SAL”, “ человек, идентифицируемый как ID, имеет некоторое жалование, но неизвестно, какое”, “ человек, идентифицируемый как ID, не получает жалования”.

Сделаем ряд комментариев к проделанному:

1. В приведенном примере нами рассматривались только два вида отсутствующей информации, но метод допускает обобщение на большее их число.
2. Проведенная декомпозиция сохраняет первичные и внешние ключи и ограничения целостности.
3. Возможен и другой вариант горизонтальная декомпозиция отношений, в некоторых практических случаях более удобный, так как позволяет сократить количество результирующих отношений. Он изображен на рис. 5, 6.

Определение традиционно выглядящего представления на основе полученных таблиц представлена на рис. 7, его внешний вид – на рис. 8.

CREATE VIEW r1
AS
SELECT  tmp.* FROM (
     (SELECT earns.id, CAST(earns.sal AS varchar(40)) AS SAL FROM earns)
      UNION
     (SELECT sal_unk.id, CAST(sal_unk.reason AS varchar(40)) FROM sal_unk)
) AS tmp
GO

CREATE VIEW r2
AS
SELECT  tmp.* FROM (
     (SELECT does_job.id, does_job.job AS JOB FROM does_job)
      UNION
     (SELECT job_unk.id, job_unk.reason FROM job_unk)
) AS tmp
GO

CREATE VIEW personal_info_v
AS
  SELECT r1.id, called.name, r2.job, r1.sal
  FROM ((r1 JOIN r2 ON r1.id = r2.id) JOIN called ON r2.id = called.id)
GO              

DROP VIEW r1

DROP VIEW r2

Действуя по этой технологии, таблица publishers БД Pubs, начальный вариант которой рассмотрен на Рис. 9, превратится в набор таблиц:

• PUBLISHERS { pub_id, pub_name, city, country }
• STATE { pub_id, state }
• STATE_UNK { pub_id }
• STATE_NONE { pub_id }.

Каверзные вопросы

Похоже, продемонстрированная методика декомпозиции Дарвена действительно решает многие теоретические вопросы, о которых мы писали в разделе “NULL - проблема”. Но, с другой стороны, оказывается, что она порождает новые, не менее интересные вопросы.

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

Заключение

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

Литература

1. Codd, E.F. "A Relational Model of Data for Large Shared Data Banks." CACM 13(6), June 1970. Republished in Milestones of Research -- Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26(1), January 1983.
2. Codd, E.F. "Interactive Support for Nonprogrammers: The Relational and Network Approaches." IBM Research Report RJ1400 (June 6th, 1974). Republished in Randall J. Rustin (ed.), Proc. ACM SIGMOD Workshop on Data Description, Access, and Control, Vol. II, Ann Arbor, Michigan, May 1974. Also in C.J. Date, Relational Database: Selected Writings. Reading, Mass.: Addison-Wesley, 1986.
3. Codd, E.F. The Relational Model For Database Management Version 2. Reading, Mass.: Addison-Wesley, 1990.
4. Stonebraker, Michael. Introduction to Chapter 1 ("The Roots"). Readings in Database Systems (2nd edition). San Mateo, Calif.: Morgan Kaufmann, 1994.
5. Codd, E.F. "Is Your DBMS Really Relational?"; "Does Your DBMS Run By The Rules?" Computerworld (October 14th, 1985; October 21st, 1985).
6. Date C. J. Notes Toward a Reconstitued Definition of the Relational Model Version 1 (RM/V1). In: Date C. J. (with Darwen H. ) Relational Databases: Selected Writings 1989-1991. Reading, Mass.: Addison-Wesley, 1992.
7. Date C. J. The Relational Model. In: Date C. J. An Introduction to Database Systems (7^th Ed.), Reading, Mass.: Addison-Wesley, 2000.
8. Darwen H. , Date C. J. The Third Manifesto. //ACM SIGMOD Record 24, No. 1, 1995.
9. Darwen H. , Date C. J. The Third Manifesto: Foundation for Object/Relational Databases. In: Date C. J. (with Darwen H. and McGoveran D.) Relational Databases: Selected Writings 1994-1997. Reading, Mass.: Addison-Wesley, 1998.
10. Дейт К., Дарвен Х. Основы будущих систем баз данных. Третий манифест. 2-е изд. (под ред. С. Д. Кузнецова). М.: Янус-К, 2004.
11. Darwen H. , Date C. J. The Second Life of Relational Model. // DB/M Magazine, No. 1, 1995; DB/M Magazine, No. 2, 1995.
12. Codd E. F. Extending the Relational Database Model to Capture More Meaning. // ACM TODS, No. 4, 1970.
13. Date C. J., Darwen H., Lorentzos N. A. Temporal Data and The Relational Model. Reading, Mass.: Addison-Wesley, 2003.

• Можем ли мы сделать операционные системы надежными и безопасными
• Регулярные выражения в Perl
• Хорошие идеи: взгляд из Зазеркалья
• Руководство GNU по обеспечению конфиденциальности