14. Замыкание множества функциональных зависимостей.

Замкнутые множества функциональных зависимостей

Как мы показали, на основании заданного множества FD зачастую возможно вы­вести некоторые другие FD, включая тривиальные и нетривиальные. В следующих разделах нам понадобится различать заданные (given) FD, справедливость которых в контексте определенного отношения провозглашается изначально, и производные (derived) FD, получаемые путем логического вывода на основании заданных FD с по­мощью рассматриваемых здесь правил и изложенного выше алгоритма вычисления замыкания множества атрибутов.

Иногда существует возможность выбора одного из альтернативных наборов FD, пригодных для представления полного множества FD конкретного отношения. Любое множество функциональных зависимостей отношения, из которых допустимо вывести все другие FD, называют базисом (basis) отношения. Если ни одно из подмножеств ба­зиса не может быть, в свою очередь, использовано для получения полного множества FD отношения, принято говорить, что базис является минимальным (minimal).

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

Прежде чем перейти к изложению остальных правил обращения с функциональ­ными зависимостями, рассмотрим основной принцип, лежащий в основе всех этих правил. Предположим, что {А_ЬА₂,..., А_п) — это множество атрибутов, a S — множество функциональных зависимостей. Замыканием (closure) множества {Л_ь А₂,.А_п] при ус­ловии выполнения FD множества S называют множество В атрибутов, такое что для каждого отношения, которому удовлетворяют все FD множества 5, справедлива и FD А₁А₂-А_п~^В. Другими словами, FD А_уА₂ — А_п^В следует из FD множества S. Замыкание множества {А_и А₂, ...,А_п) атрибутов обозначают как t [А_Х,А₂ А_п}⁺. Чтобы упростить обсуждение ас­пектов вычисления замыканий множеств атри­бутов, мы разрешим возможность использова­ния тривиальных FD, полагая, что А_х,А₂,...,А_{п и} всегда являются членами [А_{,А₂ А_п}⁺.

На рис. 3.19 схематически изображен про­цесс вычисления замыкания множества атри­бутов. Некоторое заданное множество атрибу­тов последовательно расширяется по мере до­бавления в него атрибутов правых частей Рис. 3.18. Правило тривиальной зависимости функциональных зависимостей, атрибуты левых частей которых уже присутствуют в мно­жестве. На определенном шаге процедуры дальнейшее расширение множества окажется невозможным, и ее результатом будет искомое замыкание множества. Ниже приведено

более подробное описание алгоритма вычисления замыкания множества {А_ЪА₂ А_п)

атрибутов по отношению к некоторому множеству FD.

Пусть переменная X представляет множество атрибутов, подлежащее расширению до момента достижения замыкания. X инициализируется значением [A_ltA₂,..., А_п].

Выполняется поиск некоторой FD В_г В₂ ••■ В_т —> С, такой, что все атрибуты В_и В₂,..., В_т принадлежат множеству X, а С — нет. Если указанная FD существу­ет, С добавляется в множество X.

Шаг 2 повторяется до тех пор, пока существуют соответствующие FD, атрибуты которых подлежат включению в множество X. Поскольку X допускает только расширение и количество атрибутов, охватываемых любой реляционной схе­мой, конечно, на определенной итерации процесса множество атрибутов, кото­рые могут быть добавлены в X, будет исчерпано.

После завершения процедуры расширения множество X содержит искомое зна­чение замыкания, {А_ЬА₂ Л„}⁺.

24. Независимые проекции отношений. Теорема Риссанена Теорема Риссанена

Проекции r1 и r2 отношения r являются независимыми тогда и только тогда, когда:

каждая FD в отношении r логически следует37) из FD в r1 и r2;

общие атрибуты r1 и r2 образуют возможный ключ хотя бы для одного из этих отношений.