Алгоритм построения замыкания атрибутов над
Рис. 6.2. Алгоритм построения замыкания атрибутов над заданным множеством FD
Докажем корректность алгоритма по индукции. На нулевом шаге 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 в замыкание Z2).
Суперключом отношения r называется любое подмножество K заголовка r, включающее, по меньшей мере, хотя бы один возможный ключ r.
Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения r является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения r выполняется FD K
A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K+ совпадает с заголовком r.
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий
