Виды декомпозиций. Декомпозиция без потерь


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


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

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

ü

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

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

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

  1. Минимальное – это не избыточное покрытие, содержащее наименьшее количество функциональных зависимостей. Их так же может быть несколько. Если рассматривать Ф/З F1 и F2, то они оба не избыточные, но минимальным среди них является только F2.
  2. Редуцированное – это множество, содержащее в себе только редуцированные Ф/З. Ф/З называется редуцированной, если она слева и справа не содержит посторонних атрибутов. Например, 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»

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

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

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

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




Начало  Назад  Вперед