Базы данных. Вводный курс


Замыкание множества функциональных зависимостей. Аксиомы Армстронга. Замыкание множества атрибутов - часть 3


Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD Z

Z[I], очевидно, принадлежит S+ (тривиальная FD «выводится» из любого множества FD). Пусть для некоторого K выполняется FD Z
Z[K], и пусть мы нашли в S такую FD A
B, что A
Z[K]. Тогда можно представить Z[K] в виде AC, и, следовательно, выполняется FD Z
AC. Но по правилу (8) мы имеем FD Z
ACB, т.е. FD Z
(Z[K] UNION B) входит во множество S+, что переводит нас на следующий шаг индукции.

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {A

D, AB
E, BF
E, CD
F, E
C}. Пусть требуется найти {AE}+ над S. На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD A
D и E
C, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CD
F, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.

Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Z

B в замыкание S+. Очевидно, что необходимым и достаточным условием для этого является B
Z+, т. е. вхождение составного атрибута B в замыкание Z.

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

Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD K

A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K+ совпадает с заголовком R.

  К сожалению, классическая статья Армстронга – W.W. Armstrong. "Dependency Structures of Data Base Relationships", Proc. IFIP Congress, Stockholm, Sweden, 1974

– так и не переведена на русский язык (на самом деле, ее нелегко найти и в оригинале).Поэтому я не могу рекомендовать ее для дополнительного чтения, хотя обязан сослаться.

  Мы используем здесь знаки операций проверки включения множеств, что не совсем корректно, поскольку если, например, множество B состоит из одного элемента, то для его обозначения используется имя соответствующего атрибута, и в этом случае правильнее было бы использовать знак «

» (проверка вхождения элемента во множество).




Начало  Назад  Вперед



Книжный магазин