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

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

CLOSURE[Z,S]:= Z; do <бесконечно> for each FD X ® Y in S /* для каждой ФЗ X ® Y в S */ do if X ≤ CLOSURE[Z,S] /* ≤ = <является подмножеством> */ then CLOSURE[Z,S]:= CLOSURE[Z,S] È Y; end; if CLOSURE[Z,S] <не изменилось в этой итерации> then leave loop; /* вычисления завершаются */ end;

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

Пример 10.3. Пусть дана переменная-отношение R с атрибутами A, B, C, D, E, F и следующими ФЗ:

A ® BC

E ® CF

B ® E

CD ® EF

Вычислим замыкание {A,B}+, исходя из указанного множества ФЗ:

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

2. Выполним внутренний цикл четыре раза – по одному для каждой ФЗ. На первой итерации будет обнаружено, что левая часть действительно является подмножеством замыкания CLOSURE[Z,S]. Таким образом, к результату добавляются атрибуты B и C. В результате замыкание CLOSURE[Z,S] представляет собой множество {A,B,C}.

3. На второй итерации (E ® CF) к замыканию не добавляется атрибутов.

4. На третьей итерации (B ® E) к замыканию CLOSURE[Z,S] добавляется атрибут E. Теперь замыкание CLOSURE[Z,S] представляет собой множество {A,B,C,E}.

5. На четвертой итерации (CD ® EF) к замыканию не добавляется атрибутов.

6. Далее внутренний цикл выполняется еще четыре раза, в ходе чего на второй итерации (E ® CF) к замыканию добавится атрибут F.

7. После еще одного четырехкратного прохождения внутреннего цикла замыкание не изменится, и процесс завершится с результатом {A,B}⁺={A,B,C,E,F}.

Данный алгоритм представляет простой способ определения, будет ли данная ФЗ X®Y в замыкание S⁺ множества S.

С данной точки зрения, суперключи переменной-отношения R – это такие подмножества K множества атрибутов переменной-отношения R, что ФЗ K ® А будет истинна для каждого атрибута A переменной-отношения R, т.е. замыкание K⁺ в пределах заданного множества ФЗ совпадает со множеством всех атрибутов переменной-отношения R.

Дата добавления: 2015-05-09