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



             

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


Вид не избыточного покрытия во многом определяется порядком, в котором Ф/З проверяются на избыточность. 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»;




    Содержание  Назад  Вперед