4. CD EF (дано)

5. AD EF (следует из пп. 3 и 4 согласно правилу транзитивности)

6. AD F (следует из п. 5 согласно правилу декомпозиции) Щ

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

в принципе, замыкание для заданного множества функциональных зависимостей S можно вычислить с помощью следующего алгоритма: Применять правила из предыдущего раздела до тех пор, пока создание новых функциональных зависимостей не прекратится . На практике редко требуется вычислить замыкание само по себе, а потому и только что упомянутый алгоритм вряд ли будет достаточно эффективным. Однако из этого раздела вы узнаете, как можно вычислить некоторое подмножество замыкания, а именно - то подмножество, которое состоит из всех функциональных зависимостей с некоторым (указанным) множеством Z атрибутов, расположенных слева. Точнее говоря, мы покажем, что для заданной переменной-отнощения R, заданного множества атрибутов этой переменной-отнощения Z и заданного множества функциональных зависимостей S, выполняющихся для переменной-отношения R, можно найти множество всех атрибутов переменной-отношения R, которые функционально зависимы от Z, т.е. так называемое замыкание множества Z в пределах S. Простой алгоритм вычисления этого замыкания показан на рис. 10.2.

Упражнение. Докажите правильность этого алгоритма.

CLOSURE[Z,S] := Z ; do <бесконечно>;

for each FD X У in S /* для каждой ФЗ X -> Y в S */ do ;

if X < CLOSURE[Z,S] /* < = <является подмножеством> */ then CLOSURE[Z,S] := CLOSURE[Z,S] u Y ; end ;

if CLOSURE[Z,S] <не изменилось в этой итерации> then leave loop ; /* вычисления завершаются */

II

Рис. 10.2. Вычисление замыканш Z множества Ев пределах S

Пример. Предположим, что дана переменная-отношение R с атрибутами А, В, С, d, Е и F и следующими функциональными зависимостями. А ВС Е CF

Мно.жество функциональных зависимостей с атрибуталш Z, расположенны.ми слева, представляет собой множество из всех функциональных зависимостей вида Z->Z, где Z является некоторым подмножеством Z. Тогда замыкание S исходного .множества S представляет собой объединение всех таких множеств функциональных зависимостей, взятых для всех воз.можных множеств атрибутов Z

в Е CD EF

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

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

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

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

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

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

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

7. Наконец после еще одного четырехкратного прохождения цикла замыкание CLOSURE [Z,S] останется неизменным и весь процесс завершится с результатом {А,В} = {A,B,C,E,F}. I

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

Еще одно важное заключение основано на следующем факте. Прежде всего, вспомним определение понятия суперключ из главы 8. Суперключ переменной-отношения R - это множество атрибутов переменной-отношения R, которое в виде подмножества (но необязательно собственного подмножества) содержит по крайней мере один потенциальный ключ. Из этого определения прямо следует, что суперключи для данной переменной-отношения R - это такие подмножества К множества атрибутов переменной-отношения R, что функциональная зависимость К -> А будет истинна для каждого атрибута А переменной-отношения R. Другими словами, множество К является суперключом тогда и только тогда, когда замыкание К для множества К в пределах заданного множества функциональных зависимостей является множеством абсолютно всех атрибутов переменной-отношения R. (Кроме того, множество К является потенциальным ключом тогда и только тогда, когда оно является неприводимым суперключом).

10.6. Неприводимые множества зависимостей

Пусть S1 и S2 - два множества функциональных зависимостей. Если любая функциональная зависимость, которая выводится из множества зависимостей S1, также выводится из множества зависимостей S2 (т.е. если замыкание SI является подмножеством замыкания 52 , то множество S2 называется покрытием для множества SP. Это значит, что если СУБД обеспечит соблюдение ограничений, представленных зависимостями множества S2, то автоматически будут соблюдены и все ограничения, устанавливаемые зависимостями множества S1.

Далее, если множество S2 является покрытием для множества S1, а множество S1 одновременно является покрытием для множества S2 (т.е. если S1=S2 ), то множества S1 и S2 эквивалентны. Ясно, что если множества S1 и S2 эквивалентны, то соблюдение СУБД ограничений, представленных зависимостями множества S2, автоматически обеспечит соблюдение ограничений, представленных зависимостями множества S1, и наоборот.

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

1. Правая (зависимая) часть каждой функциональной зависимости из множества S содержит только один атрибут (т.е. является одноэлементным множеством).

2. Левая часть (детерминант) каждой функциональной зависимости из множества S является неприводимой, т.е. ни один атрибут из детерминанта не может быть опущен без изменения замыкания (без конвертирования множества S в некоторое иное множество, не эквивалентное множеству S). В этом случае функциональная зависимость называется неприводимой слева.

3. Ни одна функциональная зависимость из множества S не может быть удалена из множества S без изменения его замыкания (т.е. без конвертирования множества S в некоторое иное множество, не эквивалентное множеству S).

В отнощений пп. 2 и 3 следует отметить, что необязательно иметь точную информацию о составе замыкания S для получения ответа на вопрос, изменится ли это замыкание при удалении из исходного множества какой-либо функциональной зависимости. В качестве примера рассмотрим уже знакомую переменную-отнощение деталей Р с функциональными зависимостями, перечисленными ниже.

Р# PNME Р# COLOR Pt WEIGHT Р# CITY

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

Некоторые авторы используют термин покрытие для обозначения эквивалентного множества.

В литературе подобное множество часто называется минимальным.