АНОМАЛИИ В РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ

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

Аномалии и нормализация схем отношений

Вопрос о проектировании "хороших" схем реляционных баз данных изучается в литературе уже свыше двадцати лет. К сожалению, к настоящему моменту так и не появилось общепринятой на практике методики проектирования схем. Описанная во всех учебниках нормализация схем отношений имеет серьезные ограничения в применении. С одной стороны, потому, что теория зависимостей, которая лежит в ее основе, изучала сложные типы ограничений, практически неприменяемые в практике проектирования баз данных (БД) (многозначные зависимости, зависимости соединения, транзитивные или TR-зависимости) [2]. Но даже такой естественный тип ограничений, как функциональные зависимости, редко применяется на практике. В первую очередь потому, что он не используется в широко распространенных семантических моделях описания предметных областей (ПрО) (например модели сущность-связь или ER-модели). С другой стороны, ограничения, связывающие различные отношения базы данных, в настоящий момент поддерживаемые СУБД (например внешние ключи) не рассматривались в рамках классической нормализации.

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

Доказательством этого утверждения служит тот факт, что широко распространенные CASE-средства так и не научились автоматически генерировать хорошие схемы БД. Чтобы получить эффективную систему требуются серьезная дополнительная работа опытного эксперта. Отметим, что похожая ситуация сложилась в области настройки (tuning) БД.

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

В работах Э.Ф. Кодда [3; 6] для устранения аномалий, возникающих при ведении БД, было введено понятие нормальных форм, которое широко обсуждалось в литературе. Формального определения понятию аномалии не было дано и обсуждение проблемы велось на интуитивном уровне. Одним из первых практических шагов по формализации понятия аномалии явилась работа Р. Фейджина [1].

Аномалии по Фейджину

В [1] Р. Фейджин впервые ввел формальное понятие аномалии, которое учитывало функциональные возможности СУБД. Он предложил среди множества ограничений, объявленных в схеме БД, выделить подмножество - ключи и ограничения домена, т.е. по сути ограничения, поддерживаемые СУБД. С момента написания статьи прошло уже более пятнадцати лет, и естественно, возможности СУБД по поддержанию ограничений целостности за это время расширились. Однако при описании подхода Фейджина мы рассмотрим только типы ограничений из оригинальной статьи.

Предположим, что задан атрибут с именем A и доменом (областью определения) Dom A. Ограничение домена, или Д-зависимость, используется для того, чтобы указать, что атрибут принимает значение из заданного подмножества домена. Введем обозначение

In (A, S), где A - имя атрибута, S Dom A.

В настоящее время реляционные СУБД поддерживают достаточно простой набор "программистских" доменов: целый, вещественный, текстовый, даты и т.д. Средств для работы с абстрактными типами данных в реляционных СУБД практически нет (они появляются в объектных или объектно-реляционных системах). Ограничения домена являются достаточно важным инструментом описания семантики ПрО средствами СУБД.

Примеры Д-зависимостей. Рассмотрим отношение СЛУЖАЩИЙ и его атрибут Возраст. Он задан на множестве целых чисел. Но для него выполняется Д-зависимость In (Возраст; 16 < Возраст < 75), ограничивающая возраст служащего. Границы определяются типом организации. Другой пример - атрибут Месяц, заданный как текстовое поле длиной до 8 символов. Д-зависимость определяет конкретные значения, которые может принимать этот атрибут: In (Месяц, {январь, февраль, март, .., декабрь}).

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

Например, для отношения СЛУЖАЩИЙ в качестве ключа может выступать атрибут Табельный_номер. Могут быть и другие ключи этого отношения - Номер_паспорта или Идентификационный_номер_плательщика. Все эти атрибуты однозначно идентифицируют служащего.

Всюду в дальнейшем под схемой отношения будем понимать выражение вида R(N,G), где R - имя отношения, N - множество имен атрибутов, G - множество ограничений целостности. Введем необходимые определения.

Определение 1. Пусть R(N, G ) - схема отношения и r - ее допустимое состояние - т.е. состояние, в котором выполнены все ограничения целостности. В том числе G включает Д- и К-зависимости. Пусть t - произвольный кортеж, заданный на множестве имен атрибутов N. Кортеж t называется совместимым (compatible) с состоянием r со схемой R(N, G), если

1) t [ P ] є r [ P ] для любого P, обьявленного ключом в схеме;

2) t [ A ] к In(A,S) для каждого A к N и каждой Д-зависимости, заданной в схеме.

Другими словами, кортеж t называется совместимым c r, если он может быть добавлен к отношению r без нарушения Д- и К-зависимостей, заданных в схеме.

Определение 2. Схема имеет аномалию по включению, если r - допустимое состояние, t - кортеж, совместимый с r, но r " {t} не является допустимым состоянием.

Пример 1. Пусть задана схема отношения СОТРУДНИК (ФИО, Ком, Тел; G), где ФИО - фамилия, имя, отчество сотрудника, Ком - номер комнаты, в которой находится рабочее место сотрудника, Тел - номер телефона, установленного в комнате. В схеме отношения объявлено также, что ФИО является ключом, а ограничений на домены нет.

G включает также две функциональные зависимости: "за каждым сотрудником закреплено место в одной комнате" (ФИО -> Ком) и "в каждой комнате находится один телефон" (Ком -> Тел). Пусть состояние отношения выглядит следующим образом:

Кортеж <Голосов А.О., 318, 4-00> является допустимым, поскольку все ограничения, поддерживаемые СУБД выполняются (значение ключа определено и не повторяется, значения атрибутов принадлежат соответствующим доменам). Однако этот кортеж нарушает ограничение, заданное в схеме (функциональную зависимость Ком -> Тел).

Определение 3. Схема отношения имеет аномалию по удалению, если существует допустимое состояние r и кортеж t, такой, что r-{t} не является допустимым состоянием.

Другими словами, существует такое подмножество строк отношения, которое нельзя удалить, не нарушив ограничений, поддерживаемых СУБД.

Пример 2. Пусть задана схема отношения ПОДЧИНЕННОСТЬ (Табельный_номер_ служащего, Табельный_номер_руководителя; G), где G включает ограничение Табельный_номер_руководителя Табельный_номер_служащего, означающее, что каждый руководитель одновременно является служащим. Пример состояния этой схемы приведен ниже,

где null означает неопределенное значение, семантика которого "значение свойства не присуще", служащий с номером 030 не имеет руководителя (является руководителем высшего уровня в данной организации).

В случае удаления третьей строки из таблицы (увольнение служащего с номером 020) нарушается указанное выше семантическое ограничение и состояние отношения становится недопустимым.

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

В примере 1 аномалии по удалению не возникают. Хотя удаление строки, содержащей данные о сотруднике, может привести к "потере" информации о телефоне в комнате (если это был единственный сотрудник в данной комнате). Отметим, что Э.Ф. Кодд рассматривает такой случай, как пример аномалии.

Таким образом, значение подхода, предложенного Фейджиным, состоит в том, что он впервые предложил при определении аномалии учитывать типы ограничений, поддерживаемых СУБД. Второй важный результат, хотя и не сформулированный явно, состоит в том, что аномалия - это есть противоречие между схемой отношения и подмножеством схемы, поддерживаемым СУБД. Отметим также, что Фейджин в своей работе ввел понятие нормальной формы DK/NF, которая устраняет рассмотренные им типы аномалий. В следующем параграфе мы рассмотрим обобщение понятия аномалии.

Обобщенное понятие аномалии в РБД

Мы предлагаем неформально определить аномалию как противоречие между концептуальной схемой ПрО и схемой БД. Концептуальная схема - это способ представления знаний о моделируемой ПрО. Схема БД - это формальный способ представления знаний о ПрО средствами выбранной СУБД. Аномалии возникают в том случае, когда наши знания о ПрО оказываются, по каким-то причинам, невыразимыми в схеме БД или входящими в противоречие с ней. Частным случаем является подход, рассмотренный в предыдущем параграфе. Схема отношения у Фейджина соответствует концептуальной схеме ПрО, а ограничения, поддерживаемые СУБД, - схеме БД. Аномалии возникают из-за того, что ограничения, входящие в схему отношения, невозможно выразить через ограничения, поддерживаемые СУБД.

Таким образом, чтобы дать более точное определение аномалии, нам надо выбрать достаточно общее понятие концептуальной схемы. Этим целям вполне соответствует подход к стандартизации понятий "концептуальная схема ПрО" и "информационная база", введенный в работах группы ISO/TC97/SC5/WG3 [7; 8]. В этих работах развита лингвистическая точка зрения на моделирование ПрО. Предметная область (Universe of Discourse) понимается как набор интересующих нас обьектов, которые существовали, существуют или потенциально могут существовать. Все знания о ПрО фиксируются в виде набора предложений естественного языка, выражающих утверждения об объектах, их взаимосвязях, классификации объектов, правилах и ограничениях. (Этот подход имеет много общего с работами в области моделирования бизнес-правил Б. фон Халле [9; 10].)

Под концептуальной схемой (КС) ПрО понимается согласованный набор предложений, выражающих утверждения, истинные для любого состояния ПрО.

Примеры предложений КС: "Сотрудник имеет рабочее место в комнате"; "В комнате находится телефон"; "Сотрудник имеет рабочее место ровно в одной комнате"; "В одной комнате находится не более одного телефона". Последние два предложения выражают наличие функциональной зависимости между объектами предметной области. Согласованность предложений КС означает, что не допускаются предложения, противоречащие друг другу. Например, предложения "Студент слушает не менее 6 курсов в семестре" и "Студент слушает не более 5 курсов в семестре" не могут одновременно входить в КС.

Информационная база (ИБ) - это набор предложений, согласованных друг с другом и с КС, выражающих утверждения, истинные для данного состояния ПрО и не входящие в КС.

Примеры предложений ИБ: "Сотрудник Безруков Д.И. имеет рабочее место в комнате 113"; "В комнате 113 находится телефон 123-43-32".

При проектировании информационной системы КС отображается в схему БД, а ИБ - в состояние БД. Этот процесс графически представлен на рис 1. Построение "хорошего" отображения - основная задача проектировщика БД.

Пусть L - множество всех возможных предложений ИБ. Каждому предложению приписывается оценка истинности (Истина или Ложь). Правила, входящие в КС, выделяют подмножество допустимых предложений ИБ L". Другими словами, L" - это множество предложений, которым в некотором состоянии ПрО может быть приписана оценка Истина. Предложения из L\L" являются тождественно ложными. На рис. 1 и 2 эта область изображена темным квадратом. Множество предложений, которым в текущем состоянии ПрО приписана оценка Истина, называются актуальными предложениями ИБ. Обозначим их LA. Предложения, принадлежащие множеству L"\LA, называются неактуальными предложениями ИБ. Движение пунктирной линии (1) на рис. 1 соответствует изменению состояния ИБ.

Пусть S - множество всех возможных предложений (записей) БД, описывающих ПрО. Ограничения в схеме БД, индуцированные КС, выделяют подмножество S" допустимых предложений БД. Предложения из подмножества S\S" (недопустимые предложения) изображены на рис. 1 и 2 темным квадратом.

Пусть SA - множество предложений БД, которым в текущем состоянии БД приписана оценка Истина. Предложения, принадлежащие SA, называются актуальными предложениями БД.

Предложения, принадлежащие множеству S"\SA, называются неактуальными предложениями БД.

Движение пунктирной линии (2) на рис. 1 и 2 соответствуют изменению состояния БД. Отображение КС в схему БД индуцирует отображение, которое переводит предложения ИБ в предложения БД.

Главный тезис настоящей работы - понятие аномалии неразрывно связано с понятием концептуальной схемы ПрО и ее информационной базы. Аномалия - это противоречие, возникающее при отображение информационной базы в базу данных, которое состоит в том, что некоторое допустимое состояние ИБ отображается в недопустимое состояние БД или обратное отображение переводит допустимое состояние БД в недопустимое состояние ИБ.

Подчеркнем, что аномалии возникают в результате операций над базой данных. Всякое изменение состояния ПрО приводит к необходимости внести изменение в БД, что и выполняется через операции.

Определение 4. Аномалией первого рода будем называть такое отображение ИБ в БД, при котором допустимое предложение ИБ отображается в недопустимое предложение БД.

Стрелка (1) на рис. 2 соответствует аномалии первого рода.

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

Определение 5. Аномалией второго рода будем называть такое отображение, при котором образ допустимого актуального предложения ИБ является допустимым актуальным предложением БД, а обратное отображение переводит его в неактуальное предложение ИБ. Стрелка (2) на рис. 2 соответствует аномалии второго рода.

Аномалии второго рода возникают в том случае, когда данные введены правильно, но операции над БД могут привести к неправильным результатам. Иллюстрацией этого рода аномалий является пример 2 из предыдущего раздела. Удаляя данные о сотруднике из БД, мы нарушаем ограничения КС, которые не поддерживаются СУБД.

Подход, предложенный Фейджиным, позволяет формализовать аномалии первого рода, но не учитывает аномалии второго рода, т.е. допустимое состояние БД может быть преобразовано в недопустимое состояние ИБ.

Отметим, что в системах управления базами знаний концептуальный уровень и уровень БД объединяются в один. Как следствие не возникает аномалий. Пример - системы, написанные на языке ПРОЛОГ.

Приведенное в настоящем разделе определение аномалии носит достаточно общий характер. Для рассмотрения конкретных примеров аномалий проектировщик может выбрать используемые им семантическую модель, СУБД и проанализировать, какие ограничения, заданные в модели, не поддерживаются СУБД.

Заключение

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

1) Выбрать концептуальную модель, с помощью которой будет построена концептуальная схема.

2) Построить точное описание семантических ограничений, поддерживаемых выбранной СУБД.

Для Oracle такая работа в настоящее время проводится [11;12].

3) Построить отображение выбранной концептуальной модели в модель данных, поддерживаемую СУБД.

4) Определить, что такое хорошая схема и описать методику ее построения.

Практическая методика построения хороших схем реляционных БД должна быть создана для каждой пары: концептуальная модель - СУБД.

Из всего сказанного можно сделать еще один практический вывод: нельзя вполне полагаться на мнение сторонников CASE-средств, утверждающих, что эти средства позволяют автоматически генерировать хорошие (нормализованные) схемы баз данных для промышленных СУБД, поддерживающих стандарт SQL.

Литература

1. Fagin R. A. Normal Form for Relational Databases That is Based on Domains and Keys// ACM Transactions on Database Systems.- 1981.- V.6, #.3.- pp.387-415.
2. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука, 1988.
3. Codd E.F. Normalized Data Base Structure: A Brief Tutorial//Proc. of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control.- N.-Y.: ACM, pp.1-17.
4. Ульман Дж. Основы систем баз данных.- М.: Финансы и статистика, 1983, 334с.
5. Date C.J. An Introduction to Database Systems.- Addison-Wesley, Sixth edition, 1995
6. Codd E.F. Further Normalization of the Data base Relational Model // Data Base Systems.- N.J.: Prentice-Hall, 1972, pp.33-64.
7. Jardine D.A. Concepts and Terminology for the Conceptual Schema and Information Base// Computers and Standards, 1984, V.3, pp.3-17.
8. Jardine D.A., Reuber A.R. Information Semantics and the Conceptual Schema // Information Systems.- V.9, # 2.- 1984, pp.147-156.
9. B. von Halle Back to Business Rule Basics //Database Programming & Design, 1994, v. 7, #.10, pp.15-18.
10. B. von Halle In Pursuit of Good Behavior // Database Programming & Design, 1996, v. 9, #.5, pp.11-15.
11. Kopelaars T. Business Rules: Classification and Implementation.- Proc. of International Oracle User Week, 1994, Paper 10, pp. 1-10.
12. Kopelaars T. Business Rules: Guidelines for Deferred Checking.- Proc. of European Oracle User Group Conference, 1995, Florence, Italy, v. 4, pp. 3-14.