18c0693f

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


При декомпозиции исходные отношения опираются не на все Ф/З, а только на те, которые являются подмножеством так называемого минимального покрытия. Чтобы осуществить переход от множества Ф/З к минимальному покрытию необходимо установить так называемые избыточные Ф/З. Пусть дано множество Ф/З 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}.

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