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


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


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

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

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

  1. Рефлексивность: X®X (F1);
  2. Пополнение: если X®Y, то XZ®Y (F2); Пополнение возможно только для левой части, при этом полученную левую часть нельзя разложить обратно!
  3. Аддитивность: если X®Y, X®Z, то X®YZ (F3);
  4. Проективность: если X®YZ, то X®Y, X®Z (F4);
  5. Транзитивность: если X®Y, Y®Z, то X®Z (F5);
  6. Псевдотранзитивность: если X®Y, YZ®W, то XZ®W (F6).

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

ß-аксиомы:

  1. Рефлексивность: X®X (ß1);
  2. Накопление: если 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) {а, е, ж}

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

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

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

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

  1. Неизбыточное – покрытие, которое не содержит избыточных Ф/З. У каждого множества Ф/З может быть несколько не избыточных покрытий.


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



    Книжный магазин