Шрифт:
Необходимо специально отметить, что эти самые произвольные правила являются «производными» именно от пройденных нами ранее правил вывода Армстронга.
Сформулируем производные правила вывода функциональных зависимостей в виде следующей теоремы.
Теорема.
Следующие правила являются производными от правил вывода Армстронга.
Правило вывода 1. + X Z -> X;
Правило вывода 2. X -> Y, X -> Z + X Y -> Z;
Правило вывода 3. X -> Y Z + X -> Y, X -> Z;
Здесь X, Y, Z, W, так же как и в предыдущем случае, – произвольные подсхемы схемы отношения S.
1. Первое производное правило называется правилом тривиальности и читается следующим образом:
«Выводится правило: “объединение подсхем X и Z функционально влечет за собой X”».
Функциональная зависимость с левой частью, являющейся подмножеством правой части, называется тривиальной. Согласно правилу тривиальности ограничения тривиальной зависимости выполняются автоматически.
Интересно, что правило тривиальности является обобщением правила рефлексивности и, как и последнее, могло бы быть получено непосредственно из определения ограничения функциональной зависимости. Тот факт, что это правило является производным, не случаен и связан с полнотой системы правил Армстронга. Подробнее о полноте системы правил Армстронга мы поговорим чуть позднее.
2. Второе производное правило называется правилом аддитивности и читается следующим образом: «Если подсхема X функционально определяет подсхему Y, и X одновременно функционально определяет Z, то из этих правил выводится следующее правило: “X функционально определяет объединение подсхем Y и Z”».
3. Третье производное правило называется правилом проективности или правилом «обращение аддитивности». Оно читается следующим образом: «Если подсхема X функционально определяет объединение подсхем Y и Z, то из этого правила выводится правило: “X функционально определяет подсхему Y и одновременно X функционально определяет подсхему Z”», т. е., действительно, это производное правило является обращенным правилом аддитивности.
Любопытно, что правила аддитивности и проективности применительно к функциональным зависимостям с одинаковыми левыми частями позволяют объединять или, наоборот, расщеплять правые части зависимости.
При построении цепочек вывода после формулировки всех посылок применяется правило транзитивности с той целью, чтобы включить функциональную зависимость с правой частью, находящейся в заключении.
Проведем доказательства перечисленных произвольных правил вывода.
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)> ограничение, накладываемое этим множеством функциональных зависимостей. Распишем его: