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


Аксиомы вывода Классификация покрытий - часть 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} – каноническое покрытие.

 

  1. Оптимальное – это такое покрытие, для которого не существует эквивалентного ему множества с еще меньшим числом вхождений атрибутных символов.

F7={ABC®DB, AB®EC, E®AB} Оптимальное: F8={AB®E, EC®D, E®AB}

  1. Кольцевое – используется в качестве основания для декомпозиции на минимальном покрытии Ф/З с эквивалентными левыми частями.

Множество Ф/З называется кольцевым покрытием множества F, если оно эквивалентно ему и представлено виде комплексных Ф/З.

Например, для множества F9 = {A®B, B®A, B®C, C®D} кольцевое покрытие будет иметь вид: G1 = {(A; B) ®C; (C) ®D}.

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

 




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