Этапы построения схемы БД

Вторая и третья нормальные формы

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

Определение. Пусть задана схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, (возможно R – тип записи для структурированной модели данных). Пусть X и Y – некоторые подмножества из множества атрибутов U. Будем говорить, что X функционально определяет Y(X ® Y), если в любой реализации r схемы R не могут присутствовать два кортежа t,u Î r, такие что t[X]=u[X] и t[Y]¹u[Y].

Свойства функциональных зависимостей.

Дано: схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R:

Рефлексивность. Если Y Í X Í U, то X ® Y.

Пополнение. Если X ® Y и Z Í U, то XZ ® YZ.

Транзитивность. Если X ® Y и Y ® Z, то X ® Z.

Определение. Пусть F – множество функциональных зависимостей, определенных на множестве атрибутов U = {A₁, A₂,..., An}. Тогда через F⁺ обозначим замыкание множества F, полученное из F за счет применения правила логического следствия.

Формальное определение первичного ключа

Дано: схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R. Множество X Í U, является первичным ключом для R, если выполнено:

1. X ® A₁,A₂,...,An Î F⁺;

2. Для любого Y Ì X (Y -истинное подмножество X) выполнено Y ® A₁,A₂,...,An Ï F⁺.

Замечание. Отношение R может содержать несколько первичных ключей.

Определение. Атрибут (либо множество атрибутов) B функционально полностью зависит от множества атрибутов X в отношении R, если выполнено: X ® B Î F⁺ и для любого Y Ì X (Y -истинное подмножество X) выполнено Y ® B Ï F⁺.

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

Определение. Дано: схема отношения R, определенная на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R и X – первичный ключ в R. Тогда R находится в третьей нормальной форме, если не выполнено следующее условие: существует Y Í U, существует атрибут A Ï X È Y:

1. X ® Y Î F⁺;

2. Y ® A Î F⁺;

3. Y ® X Ï F⁺,

где F⁺ – замыкание множества функциональных зависимостей.

Примечание. Если Y Ì X, то указанная зависимость называется частичной, в противном случае – транзитивной.

Дано: схема отношения R, определенная на совокупности атрибутов U = {A₁, A₂,..., A_n}, F – минимальное покрытие множества функциональных зависимостей в R.

Шаг 1. Функциональные зависимости X ® A_i Î F, X ® A_j Î F …, имеющие одинаковые левые части и совпадающие области определения, объединяются в одну зависимость X ® A_iA_j … (по правилу объединения).

Шаг 2. Строим декомпозицию r(R₁, R₂,..,R_k), где R_i состоит из атрибутов зависимости F_i Î F.

Шаг 3. Для атрибутов, которые не входят ни в одну функциональную зависимость, строятся отдельные отношения, состоящее из одного атрибута.

Примечание 1. Изолированный атрибут является признаком неполноты множества функциональных зависимостей F и/или множества атрибутов U.

Примечание 2. Из способа построения R_i очевидно, что декомпозиция r сохраняет функциональные зависимости.

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

Шаг 4. Строится обобщенный ключ W (первичный ключ для отношения R) и декомпозия r дополняется еще одним отношением X: r₁=rÈ{W}. Если отношение, соответствующее обобщенному ключу, является интерпретируемым и технологичным, то r₁ результат построения. В противном случае выполняется шаг 5.

Шаг 5. В обобщенном ключе W определяется многозначная зависимость X ®® Y(Z) (возможно их несколько), причем атрибуты X могут полностью или частично отсутствовать в W, и выполняется декомпозиция отношения W на отношения XY и XZ: r₂=rÈ{XY}È{XZ}. Чаще всего отношения {XY} и {XZ} уже содержатся в декомпозиции r, либо представимы через отношения в ней (тогда r₂=r), и r₂ обладает свойством соединения без потерь информации в рамках четвертой нормальной формы.

Многозначные зависимости. Дано: схема отношения R, определенная на совокупности атрибутов U = {A₁, A₂,..., A_n}, пусть X Í U, Y Í U и X Ç Y =Æ, Z=R \(X È Y).

Определение. Множество X мультиопределяет множество Y в контексте Z: X ®® Y(Z) (многозначная зависимость), если для произвольной реализации r схемы R существует два кортежа t₁,t₂ Î r таких, что t₁ [ X ] =t₂ [ X ], то существует кортеж t₃, для которого выполнено:

t₃ [ X ] =t₁ [ X ], t₃ [ Y ] =t₁ [ Y ], t₃ [ Z ] =t₂ [ Z ],

в силу симметрии существует кортеж t₄:

t₄ [ X ] =t₁ [ X ], t₄ [ Y ] =t₂ [ Y ], t₄ [ Z ] =t₁ [ Z ]

Обобщенный ключ: W – первичный ключ для отношения R, сформированного по всему множеству атрибутов U = {A₁, A₂,..., A_n}.

Введение дополнительного отношения (обобщенного ключа) может привести к следующим проблемам:

Совокупность атрибутов в W не обладает свойством однозначной семантической интерпретации: этому отношению нельзя присвоить однозначное имя. Решения:

а) выявляются потерянные функциональные зависимости на атрибутах W.

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

в) выявляется многозначная зависимость на атрибутах W и осуществляется декомпозиция отношения W.

Если отношение W оказалось интерпретируемым, то оно может быть не технологичным: на предприятии отсутствует служба, которая отвечала бы за сопровождение данных в этом отношении. Решение:

а) сформировать новую схему документооборота на предприятии;

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