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

Определение. Пусть задана схема отношения 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 может содержать несколько первичных ключей.

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

Определение. Атрибут (либо множество атрибутов) 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, то указанная зависимость называется частичной, в противном случае – транзитивной.

2.7. Этапы построения схемы бд

Дано: схема отношения 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_k), где R_i состоит из атрибутов зависимости F_iF.

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

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

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

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

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

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

Многозначные зависимости. Дано: схема отношения 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 оказалось интерпретируемым, то оно может быть не технологичным: на предприятии отсутствует служба, которая отвечала бы за сопровождение данных в этом отношении. Решение:

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

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