Введение в реляционные базы данных



              

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


Рис. 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.




Содержание  Назад  Вперед