Приведение к 3НФ с помощью алгоритм декомпозиции

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

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

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

Исходное отношение: R(K₁,K₂,A₁,…,A_n,B₁,…,B_m).

Ключ: { K₁,K₂} - сложный.

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

{ K₁,K₂} ® {A₁,…,A_n,B₁,…,B_m} - зависимость всех атрибутов от ключа отношения.

{ K₁} ® {A₁,…,A_n} - зависимость некоторых атрибутов от части сложного ключа.

Декомпозированные отношения:

R₁(K₁,K₂,B₁,…,B_m) - остаток от исходного отношения. Ключ { K₁,K₂}.

R₂(K₁,A₁,…,A_n) - атрибуты, вынесенные из исходного отношения вместе с частью сложного ключа. Ключ K₁.

Шаг 3 (Приведение к 3НФ).

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

Пример:

Пусть имеется в БД некоторое отношение и - его структура. И существует транзитивная зависимость от ключа: - выполняется в , где - ключ, - множество и - непервичный атрибут в . Очевидно, что не находится в 3НФ. Чтобы достигнуть этого, разбиваем на части:

. .

Если остались какие-нибудь транзитивные зависимости в или , то можно осуществить декомпозицию ещё раз.

Замечание. На практике, при создании логической модели данных, как правило, не следуют прямо приведенному алгоритму нормализации. Опытные разработчики обычно сразу строят отношения в 3НФ. Кроме того, основным средством разработки логических моделей данных являются различные варианты ER-диаграмм. Особенность этих диаграмм в том, что они сразу позволяют создавать отношения в 3НФ. Тем не менее, приведенный алгоритм важен по двум причинам. Во-первых, этот алгоритм показывает, какие проблемы возникают при разработке слабо нормализованных отношений. Во-вторых, как правило, модель предметной области никогда не бывает правильно разработана с первого шага. Эксперты предметной области могут забыть о чем-либо упомянуть, разработчик может неправильно понять эксперта, во время разработки могут измениться правила, принятые в предметной области, и т.д. Все это может привести к появлению новых зависимостей, которые отсутствовали в первоначальной модели предметной области. Тут как раз и необходимо использовать алгоритм нормализации хотя бы для того, чтобы убедиться, что отношения остались в 3НФ и логическая модель не ухудшилась.

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

Недостатки метода декомпозиции:

Число разбиений слишком велико.

Поиск транзитивных зависимостей имеет экспоненциальную сложность.

Дата добавления: 2014-01-11