4. Полнота системы правил Армстронга

4. Полнота системы правил Армстронга

Пусть F(S) — заданное множество функциональных зависимостей, заданных над схемой отношения S.

Обозначим через inv <F(S)> ограничение, накладываемое этим множеством функциональных зависимостей. Распишем его:

Inv <F(S)> r(S) = ?X ? Y ?F(S) [inv <X ? Y> r(S)].

Итак, это множество ограничений, накладываемое функциональными зависимостями, расшифровывается следующим образом: для любого правила из системы функциональных зависимостей X ? Y, принадлежащего множеству функциональных зависимостей F(S), действует ограничение функциональных зависимостей inv <X ? Y> r(S), определенных над множеством отношения r(S).

Пусть какое-то отношение r(S) удовлетворяет этому ограничению.

Применяя правила вывода Армстронга к функциональным зависимостям, определенным для множества F(S), можно получить новые функциональные зависимости, как уже было сказано и доказано нами ранее. И, что показательно, ограничениям этих функциональных зависимостей отношение F(S) будет автоматически удовлетворять, что видно из расширенной формы записи правил вывода Армстронга. Напомним общий вид этих расширенных правил вывода:

Правило вывода 1. inv < X ? X > r(S);

Правило вывода 2. inv <X ? Y> r(S) ? inv <X ? Z ? Y> r(S);

Правило вывода 3. inv <X ? Y> r(S) & inv <Y ? W ? Z> r(S) ? inv <X ? W ? Z>;

Возвращаясь к нашим рассуждениям, пополним множество F(S) новыми, выведенными из него же с помощью правил Армстронга зависимостями. Будем применять эту процедуру пополнения до тех пор, пока у нас не перестанут получаться новые функциональные зависимости. В результате этого построения мы получим новое множество функциональных зависимостей, называемое замыканием множества F(S) и обозначаемое F⁺(S).

Действительно, такое название вполне логично, ведь мы собственноручно путем длительного построения «замкнули» множество имеющихся функциональных зависимостей само на себе, прибавив (отсюда «+») все новые функциональные зависимости, получившиеся из имеющихся.

Необходимо заметить, что этот процесс построения замыкания конечен, ведь конечна сама схема отношения, на которой и проводятся все эти построения.

Само собой разумеется, что замыкание является надмножеством замыкаемого множества (действительно, ведь оно больше!) и ни сколько не изменяется при своем повторном замыкании.

Если записать только что сказанное в формулярном виде, то получим:

F(S) ? F⁺(S), [F⁺(S)]⁺= F⁺(S);

Далее из доказанной истинности (т. е. законности, правомерности) правил вывода Армстронга и определения замыкания следует, что любое отношение, удовлетворяющее ограничениям заданного множества функциональных зависимостей, будет удовлетворять ограничению зависимости, принадлежащей замыканию.

X ? Y ? F⁺(S) ? ?r(S) [inv <F(S)> r(S) ? inv <X ? Y> r(S)];

Итак, теорема полноты системы правил вывода Армстронга утверждает, что внешняя импликация может совершенно законно и обоснованно быть заменена эквивалентностью.

(Доказательство этой теоремы мы рассматривать не будем, так как сам процесс доказательства не столь важен в нашем конкретном курсе лекций.)