Нормализация реляционных баз данных

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

Аномалия удаления проявляется в том, что удаляя факты, относящиеся к одной сущности (объекту, явлению и т. п.), мы непроизвольно удаляем факты, относящиеся к другой сущности.

Аномалия вставки приводит к тому, что нельзя поместить в БД некоторый факт об одной сущности, не указав дополнительно некоторый факт о другой.

Аномалия обновления заключается в том, что для внесения изменения в данные об одном факте (событии, объекте) необходимо выполнить множественные изменения в БД. Примеры аномалий приведены ниже.

Одним из существенных преимуществ реляционной модели является наличие формального механизма оценки качества логической структуры БД средствами теории нормализации.

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

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

Пусть R — реляционное отношение, а X и Y — некоторые подмножества атрибутов этого отношения. Y функционально зависимо от X тогда и только тогда, когда для каждого значения множества X существует только одно значение множества Y [3]. Иначе говоря, если два кортежа отношения совпадают по значению X, то они обязательно будут совпадать и по значению Y. Записывается функциональная зависимость как X > Y, читается как «X функционально определяет ?» . Если существует ФЗ X > У, то X называют детерминантом, a Y — зависимой частью.

Из определения ФЗ, в частности, следует, что любое подмножество атрибутов отношения функционально зависимо от любого из потенциальных ключей.

Утверждение о том, что данная ФЗ выполняется всегда, по сути, является ограничением целостности для отношения и накладывает определенные ограничения на множество допустимых значений кортежей этого реляционного отношения. Забегая вперед, можно заметить, что если отношение R удовлетворяет ФЗ Л > В и Л не является потенциальным ключом, то в R присутствует некоторая избыточность, которая должна быть устранена в ходе процесса нормализации.

Рассмотрим пример. Пусть отношение STUDENTS имеет структуру, представленную в табл. 5.1, и атрибут StudID является первичным ключом. В представленном отношении есть следующие функциональные зависимости:

• • {StudID} > {ФИО};
• • {StudID, ФИО} > {Группа};
• • {StudID, ФИО} > {StudID} и т. д.

Таблица 5.1

Отношение STUDENTS.

В то же время подмножество атрибутов {Группа} в общем случае не является функционально зависимым от {ФИО}, так как в списке студентов могут оказаться однофамильцы с одинаковыми инициалами, но обучающиеся в разных группах.

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

Функциональная зависимость называется тривиальной, если ее зависимая часть является подмножеством детерминанта. В рассмотренном примере {StudID, ФИО} > {StudID} - это тривиальная зависимость.

Функциональная зависимость называется неприводимой, если выполняются следующие условия:

• • правая (зависимая) часть является одноэлементным множеством, т. е. справа находится только один атрибут;
• • левая часть (детерминант) является неприводимой, т. е. ни один атрибут из детерминанта не может быть опущен без потери ФЗ.

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

• • рефлексивность — если множество атрибутов В является подмножеством А, то, А > В;
• • дополнение — если, А > В, то, А! об С > В! об С;
• • транзитивность — если, А > В и В > С, то, А > С.

На базе правил Армстронга был выведен ряд других правил:

• • самоопределение — А > А;
• • декомпозиция — если, А > В! об С, то, А > В и, А > С;
• • объединение — если, А > В и, А > С, то, А > В! об С;
• • композиция — если A>B и C>D, то A! обC>B!обD.

Для множества ФЗ S его замыканием S' называется множество всех ФЗ, которые можно вывести из зависимостей S. Множество S всегда будет являться подмножеством своего замыкания.