2.2. Метод синтеза

1. В результате синтеза структура БД содержит минимальное число столбцов

2. В каждой таблице минимальное число столбцов

3. В каждой таблице минимальное индексное выражение для каждого ключа

4. В каждой таблице минимальный набор альтернативных ключей

В результате синтеза БД будет находиться в 3НФ.

Понятие логического следования для функциональной зависимости:

Одной функциональной зависимости соответствует множество таблиц, в которых эта зависимость выполняется. Если в каждой таблице, в которой действует ФЗ FD1, будет действовать и FD2, тогда между этими двумя отношениями будет действовать отношение логического следствия. Следует говорить, что из FD1 логически следует FD2.

Поскольку проверить на всех мыслимых таблицах выполнение этого следования невозможно, то логическое следствие заменяется понятием логического вывода. Если из FD1 можно логически вывести FD2, то они находятся в отношении логического вывода.

2.3. Аксиомы вывода

1. Аксиома рефлексивности

Y, X, R,

Y X R,

X Y.

Пример.

AB A,

A A.

2. Аксиома пополнения

|= A A,

f={X Y},

f |= XZ YZ,

X Y |= XZ YZ.

3. Аксиома транзитивности

,

f |= X Z.

Теорема аддитивности.

f |= X→YZ, X→Z,

,

f |= X Z.

Доказательство.

1) X Y,

2) X Z,

3) XX XY (A2 к (1)),

4) XY ZY (A2 к (2)),

5) X ZY (A3 к (3) и (4)).

Теорема проективности.

f |= {X YZ},

f |= .

Доказательство.

1) X YZ,

2) YZ Y,

3) X Y.

Теорема псевдотранзитивности.

|= XZ W,

1) X Y,

2) YZ W,

3) XZ YZ,

4) XZ W.

2.4. Применение аксиом вывода

Используя аксиомы Fl—F6, можно получить другие правила вывода для F-зависимостей.

Пример. Пусть r — отношение со схемой R, а X и Y — подмножества R. Аксиома F1 утверждает, что r удовлетворяет Y Y. Применяя аксиому F2, получим, что r удовлетворяет XY Y. Другой способ установить это правило — убедиться, что r удовлетворяет X Y для Y X R.

Пример. Пусть r — отношение со схемой R, а X, Y и Z — подмножества R. Предположим, что r удовлетворяет XY Z и X Y. Согласно аксиоме F6, отношение r удовлетворяет XX Z, которая упрощается до X Z.

Чтобы опровергнуть какое-либо утверждение относительно F-зависимостей, достаточно указать хотя бы одно отношение, которое не удовлетворяет этому утверждению.

Пример. Опровергнем утверждение о том, что XY ZW влечет за собой X Z. Отношение r, представленное ниже, удо­влетворяет АВ CD, но А С:

r (А В C D)

а b с d

а b’ с’ d

Некоторые аксиомы вывода могут быть получены из других. Например, транзитивность F5 является частным случаем псевдо­транзитивности F6 при Z= . Аксиома F6 следует из Fl, F2, F3 и F5; если X Y и YZ W, то, как следствие F1, имеем Z Z. Согласно F2, имеем XZ Y и XZ Z. Используя F3, получим XZ YZ. Наконец, применяя F5, получим XZ W.

В следующем разделе будет показано, что система аксиом Fl—F6 полна; это означает, что каждая F-зависимость, которая следует из множества F, может быть выведена путем одно- или многократного применения к F этих аксиом. Выше было дока­зано, что каждая аксиома выполняется в любом отношении. Поэтому применение аксиом к F-зависимостям из множества F может дать в результате только F-зависимости, которые следуют из F.

Если даны аксиомы Fl, F2 и F6, то из них можно вывести остальные. Уже было показано, что F5 является частным случаем F6. Если даны X Y и X Z, то используем F1, чтобы полу­чить YZ YZ, и дважды применяем F6, получая сначала XZ YZ, а затем X YZ. Поэтому F3 следует из Fl, F2 и F6. Чтобы доказать F4, предположим, что X YZ. Из F1 имеем Y Y, а из F2 получаем YZ Y. Применение F6 дает X Y.

Таким образом, аксиомы Fl, F2 и F6 составляют полное подмно­жество для F1—F6. Аксиомы Fl, F2 и F6 являются также неза­висимыми: ни одна из этих аксиом не может быть получена из двух других (см. упр. 4.5). Эти три аксиомы называются иногда аксиомами Армстронга, хотя они не очень похожи на исходные аксиомы Армстронга (тем не менее это название общепринято).

Пусть F — множество F-зависимостей для отношения r (R). Замыкание F, обозначаемое F⁺, — это наименьшее содержащее F множество, такое, что при применении к нему аксиом Армстронга нельзя получить ни одной F-зависимости, не принадлежащей F. Так как F⁺ должно быть конечно, то можно вычислить его, начиная с F путем применения Fl, F2 и F6 и добавления полученных F-за­висимостей к F до тех пор, пока не перестанут получаться новые зависимости. Замыкание F зависит от схемы R. Если R = АВ, то F⁺ всегда будут содержать В В. Когда R не определено явно, предполагается, что существует множество всех символов атрибу­тов, используемых в F-зависимостях из F.

Из множества F можно вывести F-зависимость Х Y, если X Y принадлежит F⁺. Так как аксиомы вывода порождают только функциональные зависимости, то F влечет за собой X Y, если X Y выводится из F. В следующем разделе доказывается обратное утверждение. Заметим, что F⁺ = (F⁺)⁺ .