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

 

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

Присвоим замыканию начальное значение (множество атрибутов)-{Z}. Далее для каждой функциональной зависимости из S проверяется условие: если ее левая часть является подмножеством замыкания, то к результату добавляются атрибуты, стоящие в правой части функциональной зависимости. Если левая часть функциональной зависимости не является подмножеством замыканий, то результат остается прежний.

Пример2. Дана переменная отношение с атрибутами А, В, С, D, E, F и следующими функциональными зависимостями:

A ―> BC

E ―> CF

B ―> E

DC ―> EF

Вычислить замыкание {AB}⁺ множества атрибутов А, В, исходя из заданного множества функциональных зависимостей S.

{AB}⁺ = {A, B, C, E, F}

Решение: присвоим замыканию начальное значение- множество атрибутов {AB}. Выполним внутренний цикл 4 раза по одному для каждой функциональной зависимости.

Атрибут А функциональной зависимости А ―> ВС, является подмножеством {AB}, следовательно, к результату добавляем ВС. Теперь замыкание представляет собой множество {A, B, C}.

Атрибут E функциональной зависимости E ―> CF не является подмножеством {A, B, C} – результат остается прежний.

Атрибут В функциональной зависимости В ―> Е является подмножеством {A, B, C}, следовательно к результату добавляем атрибут Е. Теперь замыкание представляет собой множество {A, B, C, Е}.

DC функциональной зависимости DC ―> EF не является подмножеством {A, B, C, Е} - результат прежний.

Применим тот же алгоритм к предыдущему результату. На первой итерации результат остается прежний. На второй итерации результат- {A, B, C, E, F}.На третьей и четвертой итерациях – результат остается прежний.

После еще одного четырехкратного прохождения цикла замыкание остается неизменным. Таким образом {AB}⁺ = {A, B, C, E, F}.

Т.к. {AB}⁺ не определяет все атрибуты отношения, то АВ – не ключ.

Пример3. Дана переменная- отношение с атрибутами A, B, C, D, E, F, G и следующими функциональными зависимостями:

A ―> B

BC ―> DE

AEF ―> G

1. Вычислить замыкание по атрибутам AС.

Решение: {AС}⁺ = {A, С, В, D, E}. Как видно {AС}⁺ не определяет все атрибуты переменной-отношения R, следовательно это не ключ.

вычислить замыкание по атрибутам A, С, F

2.Вычислить замыкание по атрибутам AС F.

Решение: {A, С, F}⁺ = {A, C, F, В, D, E, G};

AСF определяет все атрибуты отношения, следовательно AСF - суперключ. Его сократить нельзя. Значит AСF - потенциальный ключ переменной -отношения R.

3.Подразумевается ли зависимость ACF ―> DG одной из функциональных зависимостей множества S или является ли она членом замыкания множества S.

Решение. DG является подмножеством замыкания {A, С, F}⁺, следовательно зависимость ACF ―> DG подразумевается одной из ФЗ множества S, то есть является членом замыкания S⁺.

 

Вывод 1.Функциональная зависимость Х ―> Y является членом замыкания S⁺ тогда и только тогда, когда множество Y является подмножеством замыкания X⁺.

Вывод 2.если замыкание {Z}⁺ состоит из всех атрибутов переменной -отношения R, то подмножество Z называется суперключом переменной -отношения R.

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

Можно заметить, что потенциальный ключ состоит из атрибутов, которые не встречаются в правых частях всех функциональных зависимостей R. Но таким образом можно определить потенциальный ключ, если заранее известно, что он единственный. В противном случае необходимо вычислить замыкание атрибутов. ACF – не встречается в правых частях функциональных зависимостей.