Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





Хотя в предыдущем разделе так и не был дан эффективный алгоритм для вычисления замыкания 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.







Date: 2016-05-25; view: 1001; Нарушение авторских прав



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию