Конец теоремы.

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

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

invhF (S)ir(S) = 8X ! Y 2 F (S)[invhX ! Y ir(S)]

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

F (S) F +(S); [F +(S)]+ = F +(S)

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