32. Алгоритми нормалізації відношень.

Нормализация – метод создания набора отношений с заданными свойствами на основе требований к данным, установленным в некоторой организации. Процесс нормализации был впервые предложен Э.Ф.Коддом. Сначала были предложены только 3 вида нормальных форм: первая (1НФ), вторая (2НФ) и третья (3НФ). Затем Бойсом и Коддом было сформулировано более строгое определение 3НФ, которое получило название НФ Бойса-Кодда (НФБК). Вслед за НФБК появились определения 4НФ и 5НФ, однако на практике эти нормальные формы более высоких порядков используются редко. Нормализация – это формальный метод анализа отношений на основе их первичного (или потенциальных) ключей и существующих функциональных зависимостей. Он включает ряд правил, которые могут использоваться для проверки отдельных отношений таким образом, чтобы вся база данных могла быть нормализована до желаемой степени нормализации. Если некоторое требование не удовлетворяется, то нарушающее данное требование отношение должно быть декомпозировано на отношения, каждое из которых (в отдельности) удовлетворяет всем требованиям нормализации. Нормальные формы – требования, гарантирующие целостность данных.

1НФ. Схема R(r) находится в 1НФ, если все значения атрибутов, принадлежащих соответствующим доменам, являются атомарными. Атомарный атрибут – это атрибут, который воспринимается в операциях как единое целое. Например, атрибут дата рождения может выступать как атомарный атрибут, если в БД нет необходимости отдельно осуществлять операции с днем, месяцем или годом рождения, если такая необходимость есть, тогда дата рождения – неатомарных атрибут и должен быть разбит отдельно на день, месяц и год рождения.

2НФ. Схема R(r) находится во 2НФ отношения множества функциональных зависимостей, если она находится в 1НФ и каждый непервичный атрибут полностью зависит от каждого ключа множества ключей. Ключ – это минимальный набор атрибутов, значение которого однозначно идентифицирует кортеж. Непервичный атрибут – атрибут, который не входит в ключ. Например, в таблице, где Фамилия и Имя являются ключом (ключ нельзя делить), все остальные атрибут являются непервичными.

3НФ. Схема отношений R(r) находится в 3НФ, если она находится в 2НФ и ни один из непервичных атрибутов не является транзитивно зависимым от ключа.

Транзитивная зависимость является описанием такого типа функциональной зависимости, которая возникает при наличии следующих функциональных зависимостей между атрибутами А, В, С: . В данном случае транзитивная зависимость осуществляется через атрибут В. Для выполнения условий 3НФ необходимо внести изменения в структуру БД, а именно разбить исходную таблицу на новые таблицы так, чтобы для каждой из новых таблиц транзитивность отсутствовала. Это приведет к 2 негативным последствиям: для разбиения 1 таблицы на 2 потребуется дополнительный ресурс ЦП и памяти для организации связи между новыми таблицами; в двух таблицах будут представлены данные одного и того же атрибута – дублирование данных. Это будет «платой» за выполнение условия целостности данных.

НФБК. Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом. Детерминант – атрибут (множество атрибутов), от которого полностью зависит другой атрибут. Различие между 3 НФ и НФБК заключается в том, что функциональная зависимость допускается в 3НФ, если атрибут В является первичным ключом, а атрибут А не обязательно является потенциальным ключом. Тогда как в НФБК эта зависимость допускается только тогда, когда атрибут А является потенциальным ключом. Следовательно, НФБК является жесткой версией 3НФ, т.к. каждой НФБК является отношением в 3НФ, но не всякое отношение в 3НФ является отношением в НФБК.

Для приведения схемы данных к 3НФ можно использовать один из 2 существующих алгоритмов: алгоритм декомпозиции и алгоритм синтеза.

Алгоритм декомпозиции: Разработка универсального отношения для базы данных -> Определение всех ФЗ(функциональных зависимостей) между атрибутами отношения.->

Определение, находится ли отношение в НФБК (Бойса-Кодда). Если да, то завершить проектирование; в противном случае отношение должно быть разбито на два других отношения.->Повторение этапов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции.

Выполнить декомпозицию отношения на два отношения можно так. Пусть отношение R(A, B, C, D, ...) содержит ФЗ и, следовательно, не находится в НФБК. Атрибут С является детерминантом, но не возможным ключом. Для выполнения декомпозиции отношения R создаются два отношения R₁(A, B, C, ...) и R₂(C, D), в одно из которых выделяется ФЗ . Такая декомпозиция является декомпозицией без потерь при естественном соединении. Далее с тех же позиций рассматриваются отношения R₁ и R₂.

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

Пример приведения отношения к 3НФ посредством декомпозиции.

Рассмотрим отношение, связывающее студентов с группами, факультетами и специальностями, на которых он учится: (ФИО, Номер зач.кн., Группа, Факультет, Специальность, Выпускающая кафедра). В этом случае у нас есть следующие функциональные зависимости: Номер зач.кн. ФИО; Номер зач.кн. Группа; Номер зач.кн. Факультет; Номер зач.кн. Специальность; Номер зач.кн. Выпускающая кафедра; Группа Факультет; Группа Специальность; Группа Выпускающая кафедра; Выпускающая кафедра Факультет. Эти зависимости образуют транзитивные группы. Для того чтобы избежать этого, мы можем предложить следующий набор отношений: (Номер.зач.кн., ФИО, Специальность, Группа); (Группа, Выпускающая кафедра); (Выпускащая кафедра, Факультет).

Для устранения многозначных зависимостей (между атрибутами А, В и С некоторого отношения, для каждого значения А имеется набор значений атрибута В и набор значений атрибута С) существуют 4НФ и 5НФ. 4НФ. Отношение находится в 4НФ, если оно находится НФ Бойса-Кодда и не содержит нетривиальных многозначных зависимостей. Нормализация НФБК-отношения с получением 4НФ-отношений заключается в устранение многозначных зависимостей из НФБК-отношение посредством выделения в новое отношение одного или нескольких участвующих в многозначной зависимости атрибутов вместе с копией одного или нескольких детерминантов. 5НФ. При любой декомпозиции отношения на два других отношения полученные отношения обладают свойством соединения без потерь. Это значит, что полученные отношения можно снова соединить и получить прежнее отношение в исходном виде. Однако бывают случаи, когда требуется декомпозировать отношение на более чем два отношения. В таких случаях возникает необходимость учитывать зависимость соединения, которая устраняется с помощью 5НФ. Свойство декомпозиции, которое вызывает генерацию ложных строк при обратном соединении декомпозированных отношений с помощью операции естественного соединения – зависимость соединения. Отношение в 5НФ – отношение без зависимостей соединения. 5НФ также называется проективно-соединительной нормальной формой.