Базы данных конспект лекций - Коллектив авторов (2007)

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

Необходимо специально отметить, что эти самые произвольные правила являются «производными» именно от пройденных нами ранее правил вывода Армстронга.

Сформулируем производные правила вывода функциональных зависимостей в виде следующей теоремы.

Теорема.

Следующие правила являются производными от правил вывода Армстронга.

Правило вывода 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 (следует из пятого шага).