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

Вопрос о проектировании "хороших" схем реляционных баз данных изучается в литературе уже свыше двадцати лет. К сожалению, к настоящему моменту так и не появилось общепринятой на практике методики проектирования схем. Описанная во всех учебниках нормализация схем отношений имеет серьезные ограничения в применении. С одной стороны, потому, что теория зависимостей, которая лежит в ее основе, изучала сложные типы ограничений, практически неприменяемые в практике проектирования баз данных (БД) (многозначные зависимости, зависимости соединения, транзитивные или 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 317 318	4-67 4-95 4-67

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

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

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

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

Табельный номер служащего	Табельный номер руководителя
010 015 020 030	020 020 030 null

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

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

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

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

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