Метода функциональных зависимостей и ее нормализация

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

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

Всякая нормализованная таблица автоматически считается таблицей в первой нормальной форме, сокращенно 1НФ.

Теперь в дополнение к 1НФ можно определить дальнейшие уровни нормализации – вторую нормальную форму (2НФ), третью нормальную форму (3НФ) и т.д. По существу, таблица находится в 2НФ, если она находится в 1НФ и удовлетворяет, кроме того, некоторому дополнительному условию, суть которого будет рассмотрена ниже. Таблица находится в 3НФ, если она находится в 2НФ и, помимо этого, удовлетворяет еще другому дополнительному условию и т.д.

Таким образом, каждая нормальная форма является в некотором смысле более ограниченной, но и более эффективной, чем предшествующая. Это связано с тем, что "(N+1)-я нормальная форма" не обладает некоторыми непривлекательными особенностями, свойственным "N-й нормальной форме". Общий смысл дополнительного условия, налагаемого на (N+1)-ю нормальную форму по отношению к N-й нормальной форме, состоит в исключении этих непривлекательных особенностей.

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

Пусть дано отношение. Подмножество атрибутов отношения будем называть потенциальным ключом, если оно имеет следующие свойства:

1. Свойство уникальности - в отношении не может быть двух различных кортежей с одинаковым значением.

2. Свойство неизбыточности - никакое подмножество атрибутов ключа не является уникальным.

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

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

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

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

Таблица 2

Табельный номер	Фамилия	Зарплата
	Иванов
	Петров
	Сидоров

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

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

Рассмотрим пример с поставщиками и поставками деталей. Предположим, что нам требуется хранить информацию о наименовании поставщиков, наименовании и количестве поставляемых ими деталей, причем каждый поставщик может поставлять несколько деталей и каждая деталь может поставляться несколькими поставщиками. Можно предложить хранить данные в следующем отношении:

Поставщики и поставляемые детали (Номер поставщика, Наименование поставщика, Номер детали, Наименование детали, Поставляемое количество).

Потенциальным ключом этого отношения может выступать пара атрибутов {"Номер поставщика", "Номер детали"} - они подчеркнуты.

Приведенный способ хранения данных имеет ряд недостатков.

Что произойдет, если изменилось наименование поставщика? Так как наименование поставщика повторяется во многих кортежах отношения, то это наименование нужно одновременно изменить во всех кортежах, где оно встречается, иначе данные станут противоречивыми. То же самое с наименованиями деталей. Значит, данные хранятся в нашем отношении с большой избыточностью.

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

Подобные проблемы возникают потому, что мы смешали в одном отношении различные объекты предметной области - и данные о поставщиках, и данные о деталях, и данные о поставках деталей. Говорят, что такое отношение плохо нормализовано.

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

Эти фразы отражают различные типы взаимосвязей. Чтобы более точно отразить предметную область, можно иначе сформулировать фразы: " Один Поставщик может выполнять несколько Поставок", " Одна Деталь может поставляться несколькими Поставками". Это пример взаимосвязи типа " один-ко-многим ".

Взаимосвязь между "Поставщиками" и "Деталями" можно переформулировать так: " Несколько Деталей может поставляться несколькими Поставщиками". Это пример взаимосвязи типа " много-ко-многим ".

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

Механизм реализации взаимосвязи "один-ко-многим" состоит в том, что в дочернее отношение добавляются атрибуты, являющиеся ссылками на ключевые атрибуты родительского отношения. Эти атрибуты и являются внешними ключами, определяющими, с какими кортежами родительского отношения связаны кортежи дочернего отношения. Такие атрибуты еще называют мигрирующими из родительского отношения.

Таким образом, наш пример с поставщиками и поставляемыми деталями должен выглядеть следующим образом:

Поставщики (Номер поставщика, Наименование поставщика).

Детали (Номер детали, Наименование детали).

Поставки (Номер поставщика, Номер детали, Поставляемое количество).

В отношении "Поставки" атрибуты "Номер поставщика" и "Номер детали" являются ссылками на ключевые атрибуты отношений "Поставщики" и "Детали" и, следовательно, являются внешними ключами. Заметим, что данные отношения свободны от недостатков, описанных выше, когда все данные предлагалось хранить в одном отношении. Действительно, при изменении наименования поставщика или детали это изменение происходит только в одном месте. Если поставщик прекратил поставки всех деталей, то удаляются соответствующие кортежи в отношении "Поставки", данные же о самом поставщике остаются без изменений.

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

Внешний ключ, как правило, не обладает свойством уникальности. Так и должно быть, так как в дочернем отношении может быть несколько кортежей, ссылающихся на один и тот же кортеж родительского отношения. Это, собственно, и дает тип отношения "один-ко-многим".

Если внешний ключ все-таки обладает свойством уникальности, то связь между отношениями имеет тип " один-к-одному ". Чаще всего такие отношения объединяются в одно отношение, хотя это и не обязательно.

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

Функциональные зависимости. Для устранения указанных аномалий в универсальном отношении применяется метод нормализации отношений. Нормализация основана на понятии функциональной зависимости атрибутов отношения.

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

Символически функциональная зависимость записывается как

B®A.

Множество атрибутов B называется детерминантом функциональной зависимости, а множество атрибутов A - зависимой частью.

Полная функциональная зависимость. Поле A находится в полной функциональной зависимости от составного поля B, если оно функционально зависит от B и не зависит функционально от любого подмножества поля B.

Например, в таблице Блюда поля Рецепт и Вид функционально зависят от ключа Название блюда, а в таблице Поставщики поле Страна функционально зависит от составного ключа (Поставщик, Город). Однако последняя зависимость не является функционально полной, так как Страна функционально зависит и от части ключа – поля Город.

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

1. Сотрудники организации выполняют проекты.

2. Проекты состоят из нескольких заданий.

3. Каждый сотрудник может участвовать в одном или нескольких проектах или временно не участвовать ни в каких проектах.

4. Над каждым проектом могут работать несколько сотрудников или временно проект может быть приостановлен; тогда над ним не работает ни один сотрудник.

5. Над каждым заданием в проекте работает один сотрудник.

6. Каждый сотрудник числится в одном отделе.

7. Каждый сотрудник имеет телефон, находящийся в отделе сотрудника.

В ходе дополнительного уточнения того, какие данные необходимо учитывать, выяснилось следующее:

1. О каждом сотруднике необходимо хранить табельный номер и фамилию. Табельный номер является уникальным для каждого сотрудника.

2. Каждый отдел имеет уникальный номер.

3. Каждый проект имеет номер и наименование. Номер проекта является уникальным.

4. Каждая работа из проекта имеет номер, уникальный в пределах проекта. Работы в разных проектах могут иметь одинаковые номера.

Универсальное отношение:

СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ, Н_ПРО, ПРОЕКТ, Н_ЗАДАН), где

Н_СОТР - табельный номер сотрудника;

ФАМ - фамилия сотрудника;

Н_ОТД - номер отдела, в котором числится сотрудник;

ТЕЛ - телефон сотрудника;

Н_ПРО - номер проекта, над которым работает сотрудник;

ПРОЕКТ - наименование проекта, над которым работает сотрудник;

Н_ЗАДАН - номер задания, над которым работает сотрудник.

Так как каждый сотрудник в каждом проекте выполняет одно задание, то в качестве потенциального ключа отношения необходимо взять пару атрибутов { Н_СОТР, Н_ПРО }.

В этом отношении можно выписать следующие функциональные зависимости:

Зависимость атрибутов от ключа отношения:

{ Н_СОТР, Н_ПРО }® ФАМ

{ Н_СОТР, Н_ПРО }® Н_ОТД

{ Н_СОТР, Н_ПРО } ®ТЕЛ

{ Н_СОТР, Н_ПРО }® ПРОЕКТ

{ Н_СОТР, Н_ПРО } ®Н_ЗАДАН.

Зависимость атрибутов, характеризующих сотрудника, от табельного номера сотрудника:

Н_СОТР ®ФАМ

Н_СОТР ®Н_ОТД

Н_СОТР ®ТЕЛ.

Зависимость наименования проекта от номера проекта:

Н_ПРО ®ПРОЕКТ.

Зависимость номера телефона от номера отдела:

Н_ОТД ® ТЕЛ.

Приведенные функциональные зависимости отражают взаимосвязи, обнаруженные между объектами предметной области.

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

Если потенциальный ключ отношения является простым, то отношение автоматически находится в 2НФ.

Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ не находится в 2НФ, так как есть атрибуты, зависящие от части сложного ключа.

Зависимость атрибутов, характеризующих сотрудника, от табельного номера сотрудника является зависимостью от части сложного ключа:

Н_СОТР ®ФАМ

Н_СОТР ®Н_ОТД

Н_СОТР ®ТЕЛ.

Зависимость наименования проекта от номера проекта является зависимостью от части сложного ключа:

Н_ПРО ®ПРОЕКТ.

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

Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ декомпозируем на три отношения - СОТРУДНИКИ_ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ:

а)Отношение СОТРУДНИКИ_ОТДЕЛЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ):

Функциональные зависимости:

Зависимость атрибутов, характеризующих зависимость сотрудника от табельного номера сотрудника:

Н_СОТР ®ФАМ

Н_СОТР ®Н_ОТД

Н_СОТР ®ТЕЛ.

Зависимость номера телефона от номера отдела:

Н_ОТД ® ТЕЛ.

б)Отношение ПРОЕКТЫ (Н_ПРО, ПРОЕКТ):

Функциональные зависимости:

Н_ПРО ®ПРОЕКТ.

в)Отношение ЗАДАНИЯ (Н_СОТР, Н_ПРО, Н_ЗАДАН):

Функциональные зависимости:

{ Н_СОТР, Н_ПРО } ®Н_ЗАДАН.

Отношения, полученные в результате декомпозиции, находятся в 2НФ. Действительно, отношения СОТРУДНИКИ_ОТДЕЛЫ и ПРОЕКТЫ имеют простые ключи, следовательно, автоматически находятся в 2НФ; отношение ЗАДАНИЯ имеет сложный ключ, но единственный неключевой атрибут Н_ЗАДАН функционально зависит от всего ключа { Н_СОТР, Н_ПРО }.

Часть аномалий обновления устранена. Так, данные о сотрудниках и проектах теперь хранятся в различных отношениях, поэтому при появлении сотрудников, не участвующих ни в одном проекте, добавляются кортежи в отношение СОТРУДНИКИ_ОТДЕЛЫ. Точно так же при появлении проекта, над которым не работает ни один сотрудник, вставляется кортеж в отношение ПРОЕКТЫ.

Фамилии сотрудников и наименования проектов теперь хранятся без избыточности. Если сотрудник сменит фамилию или проект сменит наименование, то такое обновление будет произведено в одном месте.

Если по проекту временно прекращены работы, но требуется, чтобы сам проект сохранился, то для этого проекта удаляются соответствующие кортежи в отношении ЗАДАНИЯ, а данные о самом проекте и данные о сотрудниках, участвовавших в проекте, остаются в отношениях ПРОЕКТЫ и СОТРУДНИКИ_ОТДЕЛЫ.

Тем не менее часть аномалий разрешить не удалось.

Оставшиеся аномалии вставки. В отношение СОТРУДНИКИ_ОТДЕЛЫ нельзя вставить кортеж (4, Пушников, 1, 33-22-11), т.к. при этом получится, что два сотрудника из 1-го отдела (Иванов и Пушников) имеют разные номера телефонов, а это противоречит модели предметной области. Причина аномалии - избыточность данных, порожденная тем, что в одном отношении хранится разнородная информация (о сотрудниках и об отделах).

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

Причина аномалии - избыточность данных, также порожденная тем, что в одном отношении хранится разнородная информация.

Оставшиеся аномалии удаления. При удалении некоторых данных по-прежнему может произойти потеря другой информации.

Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и об отделах).

Заметим, что при переходе ко второй нормальной форме отношения стали почти адекватными предметной области. Остались трудности, связанные только с одним отношением СОТРУДНИКИ_ОТДЕЛЫ.

3НФ (Третья Нормальная Форма). Атрибуты называются взаимно независимыми, если ни один из них не является функционально зависимым от другого.

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

Отношение СОТРУДНИКИ_ОТДЕЛЫ не находится в 3НФ, т.к. имеется функциональная зависимость неключевых атрибутов (зависимость номера телефона от номера отдела):

Н_ОТД ® ТЕЛ.

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

Отношение СОТРУДНИКИ_ОТДЕЛЫ декомпозируем на два отношения - СОТРУДНИКИ, ОТДЕЛЫ.

Отношение СОТРУДНИКИ (Н_СОТР, ФАМ, Н_ОТД):

Функциональные зависимости:

Зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника:

Н_СОТР ®ФАМ

Н_СОТР ®Н_ОТД

Н_СОТР ®ТЕЛ.

Отношение ОТДЕЛЫ (Н_ОТД, ТЕЛ):

Функциональные зависимости:

Зависимость номера телефона от номера отдела:

Н_ОТД ® ТЕЛ.

Обратим внимание на то, что атрибут Н_ОТД, не являвшийся ключевым в отношении СОТРУДНИКИ_ОТДЕЛЫ, становится потенциальным ключом в отношении ОТДЕЛЫ. Именно за счет этого устраняется избыточность, связанная с многократным хранением одних и тех же номеров телефонов.

Таким образом, все обнаруженные аномалии обновления устранены. Реляционная модель, состоящая из четырех отношений СОТРУДНИКИ, ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ, находящихся в третьей нормальной форме, является адекватной описанной модели предметной области.

Алгоритм нормализации (приведение к 3НФ). Итак, алгоритм нормализации (т.е. алгоритм приведения отношений к 3НФ) описывается ниже.

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

Шаг 2 (приведение к 2НФ). Если в некотором отношении обнаружена зависимость атрибутов от части сложного ключа, то проводим декомпозицию этого отношения на несколько отношений следующим образом: те атрибуты, которые зависят от части сложного ключа, выносятся в отдельное отношение вместе с этой частью ключа. В исходном отношении остаются все ключевые атрибуты.

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

НФБК (Нормальная Форма Бойса-Кодда). При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ неявно предполагалось, что все отношения содержат один потенциальный ключ. Это не всегда верно. Рассмотрим следующий пример отношения, содержащего два ключа.

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

Поставки (PNUM, PNAME, DNUM, CNT):

PNUM – номер поставщика,

PNAME – наименование поставщика,

DNUM – номер детали,

CNT – количество деталей, поставляемое поставщиком.

Данное отношение содержит два потенциальных ключа - { PNUM, DNUM } и { PNAME, DNUM }. Видно, что данные хранятся в отношении с избыточностью - при изменении наименования поставщика это наименование нужно изменить во всех кортежах, где оно встречается. Можно ли эту аномалию устранить при помощи алгоритма нормализации, описанного ранее? Для этого нужно выявить имеющиеся функциональные зависимости:

PNUM ®PNAME - наименование поставщика зависит от номера поставщика.

PNAME ®PNUM - номер поставщика зависит от наименования поставщика.

{PNUM, DNUM} ®CNT - поставляемое количество зависит от первого ключа отношения.

{ PNUM, DNUM } ®PNAME - наименование поставщика зависит от первого ключа отношения.

{ PNAME, DNUM } ®CNT - поставляемое количество зависит от второго ключа отношения.

{ PNAME, DNUM} ®PNUM - номер поставщика зависит от второго ключа отношения.

Данное отношение не содержит неключевых атрибутов, зависящих от части сложного ключа. Действительно, от части сложного ключа зависят атрибуты PNAME и PNUM, но они сами являются ключевыми. Таким образом, отношение находится в 2НФ.

Кроме того, отношение не содержит зависимых друг от друга неключевых атрибутов, т.к. неключевой атрибут всего один - CNT. Таким образом, отношение "Поставки" находится в 3НФ.

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

Поставщики (PNUM, PNAME).

Поставки-2 (PNUM, DNUM, CNT).

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

Отношение "Поставки" не находится в НФБК, так как имеются зависимости (PNUM ®PNAME и PNAME ®PNUM), детерминанты которых не являются потенциальными ключами.

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