Базы данных: конспект лекций
Шрифт:
При построении цепочек вывода после формулировки всех посылок применяется правило транзитивности с той целью, чтобы включить функциональную зависимость с правой частью, находящейся в заключении.
Проведем доказательства перечисленных произвольных правил вывода.
1. Доказательство правила тривиальности.
Проведем его, как и все последующие доказательства, по шагам:
1) имеем: X -> X (из правила рефлексивности вывода Армстронга);
2) имеем далее: X Z -> X (получаем, применяя сначала правило пополнения вывода Армстронга, а потом как следствие первого шага доказательства).
Правило тривиальности доказано.
2. Проведем
1) имеем: X -> Y (это посылка 1);
2) имеем: X -> Z (это посылка 2);
3) имеем: Y Z -> Y Z (из правила рефлексивности вывода Армстронга);
4) имеем: X Z -> Y Z (получаем при помощи применения правила псевдотранзитивности вывода Армстронга, а потом как следствие первого и третьего шагов доказательства);
5) имеем: X X -> Y Z (получаем, применяя правило псевдотранзитивности вывода Армстронга, а после следует из второго и четвертого шагов);
6) имеем X -> Y Z (следует из пятого шага).
Правило аддитивности доказано.
3. И, наконец, проведем построение доказательства правила проективности:
1) имеем: X -> Y Z, X -> Y Z (это посылка);
2) имеем: Y -> Y, Z -> Z (выводится при помощи правила рефлексивности вывода Армстронга);
3) имеем: Y z -> y, Y z -> Z (получается из правила пополнения вывода Армстронга и следствием из второго шага доказательства);
4) имеем: X -> Y, X -> Z (получается, применением правила псевдотранзитивности вывода Армстронга, а затем как следствие из первого и третьего шагов доказательства).
Правило проективности доказано.
Все производные правила вывода доказаны.
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),
Правило вывода 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);
Далее из доказанной истинности (т. е. законности, правомерности) правил вывода Армстронга и определения замыкания следует, что любое отношение, удовлетворяющее ограничениям заданного множества функциональных зависимостей, будет удовлетворять ограничению зависимости, принадлежащей замыканию.