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



             

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


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

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

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

Пример: 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}.

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




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