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

Хотя в предыдущем разделе так и не был дан эффективный алгоритм для вычисления замыкания S⁺ на основе множества функциональных зависимостей S, в этом разделе описан алгоритм определения, будет ли данная ФЗ находиться в данном замыкании. Для этого прежде всего следует дать определение понятию суперключ. Суперключ отношения R — это множество атрибутов отношения R, которое содержит в виде подмножества, но не обязательно собственного подмножества, по крайней мере один потенциальный ключ. (Определение термина "суперключ", таким образом, может быть выведено из определения понятия "потенциальный ключ".) Таким образом, отсюда следует, что суперключи для данного отношения R — это такие подмножества К множества атрибутов отношения R, что функциональная зависимость

истинна для каждого атрибута А отношения R.

Теперь предположим, что известны некоторые ФЗ, выполняющиеся для данного отношения, и требуется определить потенциальные ключи этого отношения. По определению потенциальными ключами называются неприводимые суперключи (т.е. суперключ содержит потенциальный ключ). Таким образом, выясняя, является ли данное множество атрибутов К суперключом, можно в значительной степени продвинуться к выяснению вопроса, является ли К потенциальным ключом.

Для этого нужно определить, будет ли набор атрибутов отношения R множеством всех атрибутов, функционально зависящих от К. Таким образом, для заданного множества зависимостей S, которые выполняются для отношения R, необходимо найти способ определения множества всех атрибутов отношения R, которые функционально зависимы от К, т.е. так называемое замыкание K⁺ множества К для S. Простой алгоритм вычисления этого замыкания показан на рис. 9.2. Ниже даны пояснения. Упражнение. Докажите, что этот алгоритм правильный.

Пример. Предположим, что дано отношение R с атрибутами А, В, С, D, E и F и следующими ФЗ:

Теперь вычислим замыкание { А, В } ⁺ множества атрибутов { А, В } для данного множества ФЗ.

1. 1. Присвоим замыканию CLOSURE, S начальное значение — множество { А, В }.

2. 2. Теперь выполним внутренний цикл четыре раза, по одному разу для каждой ФЗ. На первой итерации (для зависимости А ® ВС) будет обнаружено, что левая часть действительно является подмножеством замыкания CLOSURE[K, S]; таким образом, к результату можно добавить атрибуты В и С. Замыкание CLOSURE[K, S]теперь представляет собой множество { А, В, С }.

3. 3. На второй итерации (для зависимости Е ® CF) можно обнаружить, что левая часть не является подмножеством полученного до этого момента результата; который, таким образом, остается неизменным.

4. 4. На третьей итерации (для зависимости В ® Е) множество Е будет добавлено к замыканию CLOSURE[ K, S ],которое теперь будет иметь вид { А, В, С, Е }.

5. 5. На четвертой итерации (для зависимости CD®EF) замыкание CLOSURE[ K, S ]останется неизменным.

6. 6. Теперь внутренний цикл будет выполнен еще четыре раза. На первой итерации результат останется прежним, на второй он будет расширен до { А, В, С, Е, F }, а на третьей и четвертой — снова не изменится.

7. Наконец, после еще одного четырехкратного прохождения цикла замыкание CLOSURE[ K, S ] остается неизменным и весь процесс в целом завершается с результатом { А, В, С, Е, F } ⁺= { A, В, С, Е, F }. Обратите внимание, что { А, В }не является суперключом (и, следовательно, потенциальным ключом).

Из сказанного выше можно сделать очень важное заключение: для заданного множества функциональных зависимостей S можно легко указать, будет ли заданная зависимость А ® Y следовать из S, поскольку это возможно тогда и только тогда, когда Y является подмножеством замыкания X ⁺ множества X для заданного множества S. Иначе говоря, таким образом представлен простой способ определения, будет ли данная функциональная зависимость X ® Y включена в замыкание S ⁺ множества S.