Замыкания
В теории реляционных структур данных рассматривают два вида замыкания:
- замыкание множества функциональных зависимостей F на заданном множестве атрибутов U (обозначается F+);
- замыкание набора атрибутов X Í U относительно множества функциональных зависимостей F (обозначается X+).
Замыканием F+ множества функциональных зависимостей F на множестве атрибутов U называется множество всех зависимостей вида X ® Y, каждая из которых или принадлежит F или логически следует из F, включая и тривиальные зависимости.
Если F = F+, то множество F называют полным.
Вычисление замыкания F+ для известного множества функциональных зависимостей F является, как правило, трудоемкой задачей, так как множество F+ может содержать большое количество зависимостей, даже если их немного в самом множестве F. Поэтому обычно задача построения замыкания F+ и не ставится. Однако часто необходимо решать задачу принадлежности некоторой зависимости замыканию F+. Как следует из определения, некоторая зависимость принадлежит замыканию F+, если она принадлежит множеству F или выводится из F. То есть опять нам нужно уметь устанавливать факт выводимости одной зависимости из других. Для решения этой задачи нужно использовать понятие замыкания атрибутов.
Пусть F - множество функциональных зависимостей, определенное на множестве атрибутов U и X Í U.
Замыканием X+ набора атрибутов X относительно F называется множество таких атрибутов Aj из U, зависимости которых от X (X ® Aj) логически следуют из F.
Замыкание множества атрибутов X+ обладает важным свойством [6], которое позволяет сразу определить, следует ли зависимость X ® Y из множества F, т.е. устанавливает факт выводимости одной зависимости из других. Это свойство может быть сформулировано в виде следующей теоремы.
Теорема 1. Функциональная зависимость X ® Y логически следует из F, если и только если правая часть зависимости Y содержится в замыкании атрибутов левой части зависимости, то есть Y Í X+.
Таким образом, чтобы установить факт выводимости заданной зависимости из остальных зависимостей, надо уметь вычислять замыкание атрибутов.
Известен итерационный алгоритм вычисления замыкания атрибутов [6], который здесь приводить не будем, а рассмотрим решение поставленной задачи на простом примере. Это решение очевидным образом вытекает из итерационного алгоритма.
Пример 15. Пусть U = ABCDEHG и F = {A ® D, AB ® DE, CE ® G, E ® H}.
Вычислим AB+. Замыкание набора атрибутов AB должно включать само AB и все зависимые от AB атрибуты. Таким образом,
AB+ = AB . . .
Чтобы добавить зависимые от AB атрибуты, надо найти в F такие зависимости, в левых частях которых содержатся подмножества набора AB (это A, B и AB). Такими зависимостями являются A ® D и AB ® DE. Тогда атрибут D зависит от A, а DE зависит от AB. Атрибуты D и E должны быть добавлены. Таким образом, AB+ = ABDE.
Другими словами, замыкание некоторого набора атрибутов содержит сам набор и все, зависимые от него, атрибуты.
Рассмотрим использование факта выводимости на следующем простом примере.
Пример 16. Ответим на вопрос, можно ли вывести зависимости
B ® D, B ® CD и D ® C из множества F = {B ® C, C ® D, A ® D}?
Исследуем зависимость B ® D.
По факту выводимости вычисляем замыкание атрибутов левой части зависимости B ® D по множеству F:
B + = BCD.
Правая часть исследуемой зависимости (атрибут D) содержится в замыкании, то есть D Ì BCD. Поэтому зависимость B ® D выводится из F. Как?
Множество F содержит две зависимости B ® C и C ® D, из которых по аксиоме транзитивности следует зависимость B ® D.
Исследуем зависимость B ® CD.
Замыкание атрибута левой части этой зависимости было вычислено выше и равно
B + = BCD.
Правая часть исследуемой зависимости равна CD и CD Ì B +. Поэтому зависимость B ® CD выводится из F. Как?
В множестве F имеется зависимость B ® C. Еще есть зависимость B ® D, которая, как только что было доказано, выводится из F. Используя правило объединения этих зависимостей по правым частям, получаем справедливость зависимости B ® CD.
Исследуем зависимость D ® C.
Замыкание левой части этой зависимости по множеству F:
D+ = D. Так как правая часть исследуемой зависимости C Ë D+, то по факту выводимости зависимость D ® C не выводится из F.