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