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

Теорема 1. Любое множество атрибутов функционально определяет любое своё подмножество.

А, В ® А; А, В ® В.

Теорема 2. Если А ® В и А ® С, то А ® В, С и обратно, если А ® В, С, то А ® В и А ® С.

Теорема 3. Называется теоремой о транзитивности: если А ® В и В ® С, то А ® С.

Теорема 4. Если А ® В, то А, С ® В, где С – любой атрибут отношения.

Теорема 5. Между атрибутами ключа не существует функциональных зависимостей.

Нормальные формы отношений

Нормальная форма отношения – это отношение с дополнительными ограничениями на хранящиеся в нем значения.

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

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

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

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

Недостатки такого отношения:

1) графы "Имя поставщика" и "Сведения о поставщике" не могут быть заполнены до фактической поставки конкретной партии;

 

Рисунок 6.1 – Пример отсутствия 2НФ

2) если поставщик задержал поставку некоторой партии, то удаление кортежа приведёт к удалению сведений о поставщике;

3) если надо изменить сведения о поставщике, то их придётся менять во всех кортежах, где упоминается этот поставщик.

Для получения второй нормальной формы необходимо исходное отношение разделить на два отношения:

- отношение с составным ключом;

- отношение с ключом, являющимся подмножеством составного ключа.

Для рассматриваемого примера получим:

ПОСТАВЩИК (Номер поставщика, Имя поставщика, Сведения о поставщике);

ПАРТИЯ (Номер поставщика, Код товара, Номер партии товара, Количество).

 

Третья нормальная форма (3НФ) – это отношение, находящееся во второй нормальной форме и не содержащее транзитивных зависимостей.

Рассмотрим пример отношения, в котором присутствует транзитивная зависимость:

СТУДЕНТ (№студента, №группы, Код факультета).

В данном отношении №студента ® №группы, №группы ® Код факультета, №студента ® Код факультета.

Недостатки отношения:

1) избыточность данных (код факультета повторяется для всех студентов группы, хотя было бы достаточно указать его один раз для группы);

2) усложнение контроля целостности данных.

Для получения 3НФ необходимо разделить исходное отношение на два:

СТУДЕНТ (№студента, №группы) и ГРУППА (№группа, Код факультета).

Алгоритм нормализации отношений. Метод декомпозиции

Исходные данные: универсальное отношение, включающее все атрибуты базы данных.

Шаг 1. Получение исходного множества функциональных зависимостей.

Рассматриваются все функциональные зависимости типа:

атрибут ® атрибут;

атрибут, атрибут ® атрибут;

…

атрибут, …, атрибут ® атрибут.

Шаг 2. Получение минимального покрытия множества функциональных зависимостей.

Исключаются те зависимости, которые являются следствием оставшихся зависимостей (см. теоремы о функциональных зависимостях).

Шаг 3. Объединение функциональных зависимостей.

Функциональные зависимости с одинаковой левой частью объединяются в одну зависимость.

Шаг 4. Нахождение ключа исходного отношения.

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

Шаг 5. Создание проекций исходного отношения.

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

Шаг 6. Анализ ключа.

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

Рассмотрим пример.

Исходное отношение: R (Дата, Код дисциплины, Название дисциплины, Код студента, № зачётной книжки, Фамилия, Имя, Отчество).

Шаг 1, Шаг 2 и Шаг 3 можно совместить. Результат выполнения этих шагов представлен на рисунке 6.2.

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

Шаг 4. На рисунке 6.3 отмечены атрибуты, которые попали в правые части функциональных зависимостей.

 

Рисунок 6.3 – Поиск ключа

 

Ключ исходного отношения: Дата, Код дисциплины, Код студента.

 

Шаг 5.

Проекции исходного отношения строятся для каждой зависимости, представленной на рис.2:

СПРАВОЧНИК_ДИСЦИПЛИН (Код дисциплины, Название дисциплины);

СТУДЕНТЫ (Код студента, № зачётной книжки, Фамилия, Имя, Отчество);

СЕССИЯ (Код дисциплины, Код студента, Оценка).

Первичными ключами отношений становятся левые части функциональных зависимостей.

Шаг 6.

Ключ исходного отношения не вошёл полностью ни в одно отношение, поэтому создаётся отношение из атрибутов ключа:

R1 (Дата, Код дисциплины, Код студента).

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

УЧЕБНЫЙ_ПЛАН (№ семестра, Код дисциплины, Код студента).

Ключом этого отношения становится ключ исходного отношения.

Результат. В результате применения метода декомпозиции получена реляционная модель в 3НФ:

СПРАВОЧНИК_ДИСЦИПЛИН (Код дисциплины, Название дисциплины);

СТУДЕНТЫ (Код студента, № зачётной книжки, Фамилия, Имя, Отчество);

СЕССИЯ (Код дисциплины, Код студента, Оценка);

УЧЕБНЫЙ_ПЛАН (№ семестра, Код дисциплины, Код студента).

 

Комментарий к примеру:

- реальные предметные области описываются значительно бóльшим количеством атрибутов;

- каждая функциональная зависимость должна быть обоснована с точки зрения предметной области (например, Код дисциплины, Код студента ® Оценка, так как предполагается, что по данной дисциплине экзамен сдаётся только один раз);

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