Аксиомы вывода Классификация покрытий

При декомпозиции исходные отношения опираются не на все Ф/З, а только на те, которые являются подмножеством так называемого минимального покрытия. Чтобы осуществить переход от множества Ф/З к минимальному покрытию необходимо установить так называемые избыточные Ф/З. Пусть дано множество Ф/З F на схеме R. При этом X и Y принадлежат данной схеме. Ф/З X®Y, является избыточной, если она следует из множества: F – (X®Y).

Для вывода Ф/З используются правила вывода или аксиомы вывода: Армстронга и ß-аксиомы.

Аксиомы Армстронга:

Рефлексивность: X®X (F1);

Пополнение: если X®Y, то XZ®Y (F2); Пополнение возможно только для левой части, при этом полученную левую часть нельзя разложить обратно!

Аддитивность: если X®Y, X®Z, то X®YZ (F3);

Проективность: если X®YZ, то X®Y, X®Z (F4);

Транзитивность: если X®Y, Y®Z, то X®Z (F5);

Псевдотранзитивность: если X®Y, YZ®W, то XZ®W (F6).

Из всех представленных шести аксиом, три являются независимыми (F1, F2, F6), а остальные можно вывести на основании этих. При выводе одних Ф/З на основании других, выстраиваются цепочки Ф/З полученных на основании аксиом вывода. Их называются выводы.

ß-аксиомы:

Рефлексивность: X®X (ß1);

Накопление: если X®YZ, Z®CW, то X®YZCW (ß2);

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

а. X®YZ (дано)

б. X®Z (F4) {а}

в. Z®CW (дано)

г. Z®C (F4) {в}

д. Z®W (F4) {в}

е. X®C (F5) {б, г}

ж. X®W (F5) {б, д}

з. X®YZCW (F3) {а, е, ж}

Проективность: если X®YZ, то X®Z (ß3).

Классификация покрытий:

Покрытие – это эквивалентные множества Ф/З. При этом, под эквивалентным множеством понимают такие множества F1 и F2 на схеме R, когда они взаимообратные, т.е., из множества F1 путем применения аксиом вывода, может быть получено F2, а из множества F2, аналогичным способом, может быть получено обратное множество F1.

Различают следующие покрытия:

Неизбыточное – покрытие, которое не содержит избыточных Ф/З. У каждого множества Ф/З может быть несколько не избыточных покрытий.
Вид не избыточного покрытия во многом определяется порядком, в котором Ф/З проверяются на избыточность. F={A®B, A®C, A®BC}.Получаем не избыточные покрытия: F1={A®B, A®C} или F2={A®BC}.

Алгоритм получения:

ü

выбирается Ф/З из исходного множества Ф/З (любая) и проверяется ее возможность получения их оставшихся элементов множества Ф/З с помощью аксиом вывода;

ü если выбранная Ф/З не следует из оставшихся элементов множества Ф/З, то она оставляется в исходном множестве;

ü если вывод Ф/З возможен, то она удаляется. Вывод продолжается до тех пор, пока не будет проверена каждая Ф/З.

Минимальное – это не избыточное покрытие, содержащее наименьшее количество функциональных зависимостей. Их так же может быть несколько. Если рассматривать Ф/З F1 и F2, то они оба не избыточные, но минимальным среди них является только F2.

Редуцированное – это множество, содержащее в себе только редуцированные Ф/З. Ф/З называется редуцированной, если она слева и справа не содержит посторонних атрибутов. Например, F3={A®B, AB®C}. Ф/З AB®C, содержит лишний атрибут в левой части – B. Доказать, что A®C.

а. A®A (ß1)

б. A®B (дано)

в. A®AB (ß2 из а и б)

г. AB®C (дано)

д. A®ABC (ß2 из в и г)

е. A®C (ß3 из д)

Таким образом, покрытие F4={A®B, A®C} – является редуцированным, но не минимальным.

Алгоритм получения:

ü      удаляются посторонние атрибуты из левой части Ф/З;

ü      удаляются все посторонние атрибуты из правой части Ф/З;

ü      удаляются все Ф/З вида: «A®0»

Каноническое – неизбыточное покрытие, состоящее из полных Ф/З, правая часть которых содержит только один атрибут.

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

Алгоритм получения:

ü      применяют аксиомы проективности; все Ф/З приводят к виду «X®A»;

ü      из полученного множества удаляются все избыточные Ф/З;

ü      в оставшихся Ф/З, удаляются все избыточные атрибуты.

Таким образом, вновь полученное множество Ф/З, становится редуцированным.

Пример: F5 = { A®BE, AB®CD, C®DE, B®E}

A®E – избыточная Ф/З

A®B

AB®C – не редуцир. (лишний атр. B)

AB®D – не редуцир. (лишний атр. B)

C®E

C®D

B®E

1.A®B

2.A®C

3.A®D – избыточн. (F5 из 2 и 4)

4.C®D

5.C®E

6.B®E

F6 = {A®B, A®C, C®D, C®E, B®E} – каноническое покрытие.

Оптимальное – это такое покрытие, для которого не существует эквивалентного ему множества с еще меньшим числом вхождений атрибутных символов.

F7={ABC®DB, AB®EC, E®AB} Оптимальное: F8={AB®E, EC®D, E®AB}

Кольцевое – используется в качестве основания для декомпозиции на минимальном покрытии Ф/З с эквивалентными левыми частями.

Множество Ф/З называется кольцевым покрытием множества F, если оно эквивалентно ему и представлено виде комплексных Ф/З.

Например, для множества F9 = {A®B, B®A, B®C, C®D} кольцевое покрытие будет иметь вид: G1 = {(A; B) ®C; (C) ®D}.

Кольцевые покрытия могут быть: не избыточными, минимальными, редуцированными, оптимальными.

Содержание раздела