БД5. Функциональные зависимости. Правила вывода Армстронга и Дарвена. Замыкание множества атрибутов.

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

Функциональная зависимость - связь типа многие к одному между двумя множествами атрибутов заданной переменной-отношения. Для заданной переменной-отношения R зависимость А -> В (где А и В являются подмножествами множества атрибутов переменной-отношения R) выполняется для переменной-отношения R тогда и только тогда, когда любые два кортежа переменной-отношения R с одинаковыми значениями атрибутов множества А имеют одинаковые значения атрибутов множества В.

Правила вывода Армстронга и Дарвена

Армстронг предложил набор правил вывода новых функциональных зависимостей на основе данных: (знак “→” это функциональная зависимость)

1. правило рефлексивности.
   B ⊆ A => A → B
2. дополнение.
   A → B => AC → BC, где С – новый атрибут в пределах данной схемы. АС, BC – объединение множеств.
3. транзитивность.
   A → B, B → C=> A → C.

Набор правил Армстронга является полным – для заданного множества ФЗ минимальный набор может быть выведен только с помощью этих трех правил; является исчерпывающим – в результате применений этих ФЗ никакие дополнительные ФЗ не могут быть получены.

Дополнительные правила, упрощающие задачу вывода функциональных зависимостей:

4. самоопределение.
   A → A
5. декомпозиция.
   A → BC => A → B, A → C
6. объединение.
   A → B, A → C => A → BC
7. композиция.
   A → B, C → D => AC → BD
8. правило унификации (общая теорема определения Дарвена).
   A → B, C → D => A ∪ (C-B) → BD

Замыкание множества атрибутов

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

Замыкание множества атрибутов X над множеством ФЗ S — максимальное по включению множество атрибутов, обозначаемое X_S⁺, функционально зависящих от S.

Множество ФЗ S неприводимо, если:

• Каждая правая часть ФЗ содержит ровно один атрибут
• Каждая левая часть ФЗ минимальна по включению
• S минимально по включению

Множество ФЗ S минимально по включению, если ни одна функциональная зависимость из множества S не может быть удалена из множества S без изменения его замыкания S+.