Базы данных: конспект лекций - Коллектив авторов - Страница 26

В частном случае, когда правая часть функциональной зависимости, т. е. подсхема Y, совпадает со всей схемой отношения, ограничение функциональной зависимости переходит в ограничение уникальности первичного или кандидатного ключа. Действительно:

Просто в определении функциональной зависимости вместо подсхемы X нужно взять обозначение ключа K, а вместо правой части функциональной зависимости, подсхемы Y взять всю схему отношений S, т. е., действительно, ограничение уникальности ключей отношений является частным случаем ограничения функциональной зависимости при равенстве правой части схемы функциональной зависимости всей схеме отношения.

Приведем примеры изображения функциональной зависимости:

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

Хорошим примером таких специальных правил являются правила вывода Армстронга.

Но прежде чем приступать к анализу самих правил вывода Армстронга, введем в рассмотрение новый металингвистический символ «├», который называется символом метаутверждения о выводимости. Этот символ при формулировании правил записывается между двумя синтаксическими выражениями и свидетельствует о том, что из формулы, стоящей слева от него, выводится формула, стоящая справа от него.

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

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

Правило вывода 1. ├ X → X;

Правило вывода 2. X → Y├ X ∪ Z → Y;

Правило вывода 3. X → Y, Y ∪ W → Z ├ X ∪ W → Z;

Здесь X, Y, Z, W – произвольные подсхемы схемы отношения S. Символ метаутверждения о выводимости разделяет списки посылок и списки утверждений (заключений).

1. Первое правило вывода называется «рефлексивность» и читается следующим образом: «выводится правило: “X функционально влечет за собой X”». Это самое простое из правил вывода Армстронга. Оно выводится буквально из воздуха.

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

2. Второе правило вывода называется «пополнение» и читается таким образом: «если X функционально определяет Y, то выводится правило: “объединение подсхем X и Z функционально влечет за собой Y”». Правило пополнения позволяет расширять левую часть ограничения функциональных зависимостей.

3. Третье правило вывода называется «псевдотранзитивность» и читается следующим образом: “если подсхема X функционально влечет за собой подсхему Y и объединение подсхем Y и W функционально влекут за собой Z, то выводится правило: «объединение подсхем X и W функционально определяют подсхему Z»”.

Правило псевдотранзитивности обобщает правило транзитивности, соответствующее частному случаю W: = 0. Приведем формулярную запись этого правила:

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

Правило вывода 1. inv r(S);

Правило вывода 2. inv r(S) ⇒ inv r(S);

Правило вывода 3. inv r(S) & inv r(S) ⇒ inv r(S);

Проведем доказательства этих правил вывода.

1. Доказательство правила рефлексивности следует непосредственно из определения ограничения функциональной зависимости при подстановке вместо подсхемы Y – подсхемы X.

Действительно, возьмем ограничение функциональной зависимости:

Inv r(S) и подставим в него X вместо Y, получим:

Inv 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.

Правило псевдотранзитивности доказано.

Все правила доказаны.

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

Что это за правила, как они получаются?

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

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

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

Теорема.

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

Правило вывода 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”».