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

Для отношения r(R) в любой момент существует некоторое семейство ФЗ, которому оно удовлетворяет, причем, одно его состояние может удовлетворять данной ФЗ, другое – нет. Требуется выявить семейство ФЗ F, которому удовлетворяют все допустимые состояния r, то есть будем считать семейство F заданным на схеме R.

Множество ФЗ, применимых к r(R), конечно, поэтому можно найти все ФЗ, которым удовлетворяет r (например, применяя алгоритм, рассмотренный ранее). Но это достаточно долгий процесс. Иногда оказывается возможным по некоторому множеству ФЗ определить другие ФЗ.

Определение. Будем говорить, что множество ФЗ F влечет ФЗ X Y (F |= XY), если каждое отношение, удовлетворяющее всем зависимостям из F, удовлетворяет и X Y.

Аксиома вывода – правило, устанавливающее, что если отношение удовлетворяет какой-то ФЗ, то оно удовлетворяет и некоторой другой ФЗ. Рассмотрим следующее множество аксиом.

F1. Рефлексивность

X X

F2. Пополнение (расширение левой части)

(X Y)  (XZ Y)

П

r (A B C D)

a1	b1	c1	d1
a2	b2	c1	d1
a1	b1	c1	d2
a3	b3	c2	d3

ример

Здесь (A B)  { ABB, ACB, ADB, ABCB, ABDB }

Конец примера

F3. Аддитивность

Позволяет объединить две ФЗ с одинаковыми левыми частями.

(XY, XZ)  (XYZ)

Пример

Для предыдущего отношения: (AB, AC)  (ABC)

Конец примера

F4. Проективность

В некоторой степени обратная F3.

(XYZ)  (XY)

F5. Транзитивность

(XY, YZ)  (XZ)

П

r (A B C D)

a1	b1	c2	d1
a2	b2	c1	d2
a3	b1	c2	d1
a4	b1	c2	d3

ример

Здесь (AB, BC)  (AC)

Конец примера

F6. Псевдотранзитивность

(XY, YZW)  (XZW)

На самом деле, эта система избыточна. Например, F6  F5 (для Z=), (F1, F2, F3, F5)  F6. Но она полна, то есть любая ФЗ, которая следует из F, может быть получена применением F1-F6.

Можно доказать [14], что {F1, F2, F6} – полное подмножество аксиом: (F1, F2, F6)  F3, (F1, F2, F6)  F4, F6  F5. Например, докажем F4. Пусть XYZ, тогда из (F1): YY и (F2): YZY. По (F6): XY. Утверждение доказано.

Подмножество независимых аксиом {F1, F2, F6} носит название аксиом Армстронга.

Определение. Пусть F – множество ФЗ для r(R). Замыкание F (обозначается F⁺) – это наименьшее множество, содержащее F, и такое, что при применении к нему аксиом Армстронга нельзя получить ни одной ФЗ, не принадлежащей F.

Определение. Два множества ФЗ F и G над одной и той же схемой называются эквивалентными, если F⁺ = G⁺, и обозначается это так: F  G.

Если F |= XY, то либо XY  F, либо её можно получить путём последовательного применения аксиом вывода к F. Эта последовательность аксиом называется выводом XY из F.

Определение. Последовательность P функциональных зависимостей называется последовательностью вывода на F, если каждая ФЗ из P либо принадлежит F, либо следует из предыдущих ФЗ в P после применения к ним одной из аксиом вывода.

Пример

F = {ABE, AGJ, BEI, EG, GIH}. Последовательность вывода определяется неоднозначно, например для ABGH она может выглядеть так (справа указана аксиома и предыдущий шаг, на котором выведена требуемая ФЗ):

1. ABE;

2. ABAB (F1: 1);

3. ABB (F4: 2);

4. ABBE (F3: 1, 2);

5. BEI;

6. ABI (F5: 4, 5);

7. EG;

8. ABG (F5:1, 7);

9. ABGI (F3: 6,8);

10. GIH;

11. ABH (F5: 9, 10);

12. ABGH (F3: 8, 11).

Очевидно, что эта последовательность будет, в частности, последовательностью вывода для других ФЗ, например, ABGI.

Конец примера

Определение. Используемое множество в последовательности вывода P – множество ФЗ изF, принадлежащее P.

B-аксиомы и RAP-последовательности вывода

Кроме аксиом Армстронга, часто рассматривается другая полная система аксиом, которая называется B-аксиомами.

B1. Рефлексивность (Reflexivity)

XX

B2. Накопление (Accumulation)

(XYZ, ZCW)  (XYZC)

B3. Проективность (Projectivity)

(XYZ)  (XY)

Пример

Пусть F – такое же множество ФЗ, как в предыдущем примере. Приведём последовательность вывода для ABGH, использующую только B-аксиомы:

1. EIEI (B1);

2. EG;

3. EIEGI (B2);

4. EIGI (B3);

5. GIH;

6. EIGHI (B2);

7. EIGH (B3);

8. ABAB (B1);

9. ABE;

10. ABABE (B2);

11. BEI;

12. ABABEI (B2);

13. ABABEGI (B2);

14. ABABEGH (B2);

15. ABGH (B3).

Конец примера

Можно показать [14], что аксиомы Армстронга выводятся из B-аксиом. Из полноты системы аксиом Армстронга следует и полнота системы B-аксиом.

Определение. Последовательность вывода XY из F, полученная при помощи B-аксиом называется RAP-последовательностью (по первым буквам названия B-аксиом), если она удовлетворяет следующим условиям:

1. первая ФЗ – это XX;

2. последняя ФЗ – это XY;

3. каждая ФЗ (за исключением первой и последней) либо принадлежит F, либо имеет вид XZ и получена с помощью аксиомы B2.

Пример

Пусть F – такое же множество ФЗ, как в предыдущем примере. Выпишем RAP-последовательность вывода ABGH из F:

1. ABAB (B1);

2. ABE;

3. ABABE (B2);

4. BEI;

5. ABABEI (B2);

6. EG;

7. ABABEGI (B2);

8. GIH;

9. ABABEGH (B2);

10. ABGH.

Конец примера

Теорема. Пусть F – множество ФЗ. Если существует последовательность вывода из F для XY, то существует RAP-последовательность вывода из F для XY.