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

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

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

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

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. Производные правила вывода

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

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