Аксиомы Армстронга

Аксиомы вывода

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

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

· тривиальные (ХY®Y, Х®X),

· нетривиальные (Х®Y, Х®XY),

· полные (Х®Y, Y®Z),

· неполные (ХY®Z, Y®Z)[3].

Определение 9

Функциональная зависимость тривиальна, если ее правая часть является либо собственным подмножеством левой, либо равна ему, то есть функциональная зависимость Х®Y тривиальна, если Y Í X.

Определение 10

Функциональная зависимость называется полной, если ни одно собственное подмножество ее левой части не определяет правую часть.

Определение 11

Левая часть полной функциональной зависимости называется детерминантом.

Полнота функциональных зависимостей может быть определена только при рассмотрении всего множества функциональных зависимостей, в то время как тривиальность является свойством конкретной функциональной зависимости. Например, множество функциональных зависимостей F={X®Z, ХY®Z} содержит одну полную функциональную зависимость Х®Z и одну неполную ХY®Z, детерминантом будет только левая часть первой функциональной зависимости (X). Однако в множестве F={Z®W, ХY®Z} функциональная зависимость ХY®Z уже является полной, а множество содержит два детерминанта Z и XY. Как правило, неполные и тривиальные функциональные зависимости исключаются из рассмотрения и не учитываются при осуществлении декомпозиции.

Существуют правила, которые позволяют на основании одних функциональных зависимостей вывести другие. Эти правила получили название аксиом вывода. Наиболее известные аксиомы это так называемые аксиомы Армстронга и b - аксиомы.

Аксиома рефлексивности (F₁).

X®X

Аксиома пополнения (F₂).

Определение 12

Если отношение удовлетворяет функциональным зависимостям X®Y, то оно удовлетворяет и функциональной зависимости XZ® Y.

Аксиома аддитивности (F₃). (Объединение нескольких функциональных зависимостей с одинаковыми левыми частями).

Определение 13

Если отношение удовлетворяет функциональным зависимостям X®Y и X®Z, то оно удовлетворяет и функциональной зависимости X®ZY.

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

Аксиома проективности (F₄).

Определение 14

Если отношение удовлетворяет функциональным зависимостям X®ZY и X®Z, то оно удовлетворяет и функциональной зависимости X®Y.

Данная аксиома является обратной по отношению к аксиоме аддитивности. Применяется, как правило, при осуществлении последовательности вывода.

Аксиома транзитивности (F₅).

Определение 15

Если отношение удовлетворяет функциональным зависимостям X®Y и Y®Z, то оно удовлетворяет и функциональной зависимости X®Z.

Аксиома псевдотранзитивности (F₆).

Определение 16

Если отношение удовлетворяет функциональным зависимостям X®Y и YZ®W, то оно удовлетворяет и функциональной зависимости XZ®W.

Дата добавления: 2014-12-17