Избыточные функциональные зависимости

Замыкание атрибутов. Определение и обоснование ключей в отношении

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

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

Замыканием множества атрибутов {A₁,A₂,…,A_n} на схеме R есть полное множество атрибутов, принадлежащих схеме R и функционально зависящих от {A₁,A₂,…,A_n}. Обозначается замыкание как {A₁,A₂,…,A_n}⁺.

Если замыканием того или иного множества атрибутов является вся схема отношения, то очевидно, что это множество, по крайней мере, является суперключом. Для того, чтобы определить ключ, необходимо проверить, есть ли в исходном множестве атрибутов собственное подмножество, у которого замыканием является также вся схема отношения, и оно в свою очередь не содержит аналогичного собственного подмножества. Далее рассмотрим процесс получения замыкания с помощью b- аксиом. Пусть дано множество функциональных зависимостей F={A®B, B®C}, на схеме R={ABC} отношения r. Докажем, что ключом данного отношения будет атрибут А. С этой целью построим замыкания для всех атрибутов левых частей функциональных зависимостей (см. Таблица 8).

Таблица 8

A®A	b1		B®B	b1
A®B	Дано		B®C	Дано
A®AB	b2		B®BC	b2
B®C	Дано
A®ABC	b2

Таким образом, атрибут А является ключом отношения, так как от него функционально зависят все атрибуты схемы отношения. Очевидно, что замыканием множеств AB, AC, ABC тоже будет вся схема отношения, однако они не будут являться ключами, поскольку содержат внутри себя ключи.

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

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

Пусть дано множество функциональных зависимостей F на схеме отношения R, XÍR, YÍR. Функциональная зависимость X®Y является избыточной для этого множества, если из множества функциональных зависимостей F-(X®Y) следует, что X®Y (F-(X®Y)|= X®Y).

Поскольку множество функциональных зависимостей не упорядочено и порядок рассмотрения функциональных зависимостей произволен, то в отдельных случаях в качестве избыточных функциональных зависимостей могут выступить различные функциональные зависимости. Например, в исходном множестве F={X®Y, X®Z, X®YZ} в качестве избыточных функциональных зависимостей могут быть приняты зависимости X®Y, X®Z, они следуют из X®YZ на основании аксиомы проективности, в то время как функциональная зависимость X®YZ тоже может быть рассмотрена как избыточная, поскольку она следует из двух других на основании аксиомы аддитивности. Следует отметить, что в обоих случаях после удаления избыточных функциональных зависимостей будут получены покрытия, эквивалентные исходному.

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