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

↑

▷ Содержание

⇐ ПредыдущаяСтр 31 из 32Следующая ⇒

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

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология