Изучение основных алгоритмов теории реляционных баз данных, страница 7

X→Y к F⁺ (или F |=Х→Y). Эту проверку осуществляет алгоритм PRF (рис. 2.2).

Рис. 2.2

Сложность алгоритма PRF по времени та же, что и для SX ⁺.

Приложение 3

Построение неизбыточного покрытия

Для любого множества ФЗ G, определённого на атрибутах множества R , всегда существует некоторое  такое, что F является неизбыточным покрытием G. Множество F может быть построено путём удаления из G избыточных ФЗ. На этом основан алгоритм NPOK (рис.3.1).

Рис. 3.1

Алгоритм   имеет   сложность   по   времени  O(nm³),  где n = |R|, m = |G|.

Заметим, что, изменяя в цикле For порядок просмотра ФЗ из G , можно получать

различные , являющиеся неизбыточными покрытиями G .

Приложение 4

Построение редуцированного покрытия

Для всякого множества ФЗ G , определённого на множестве атрибутов R , всегда можно построить множество F , являющееся редуцированным покрытием G. Процесс построения F выполняют в два этапа. Вначале редуцируют левые части всех ФЗ, входящих в G, то есть находят посторонние атрибуты в левых частях ФЗ и удаляют их. В результате получается множество F* , которое является леворедуцированным. Заметим, что даже если G было неизбыточным  множеством ФЗ, то результат леворедуцирования может содержать избыточные ФЗ и посторонние атрибуты в правых частях ФЗ. На втором этапе выполняют редуцирование справа множества   F* -- удаление посторонних атрибутов из правых частей ФЗ, входящих в F*.

В результате все ФЗ X→Y, избыточные в F* , если такие имелись, будут иметь вид X→Ø. После их удаления полученное множество ФЗ F - редуцированное покрытие G. Кроме того, оно является также и неизбыточным покрытием G.

Процесс построения редуцированного покрытия реализуют с помощью алгоритмов LRED, PRED (рис. 4.1, 4.2).

Если в алгоритме LRED множество G неизбыточно, то в операторе If проверку

F* |= (X - А) →Y можно упростить до проверки F* |= (X - А) →A,    при этом пропуская ФЗ,

у которых левая часть состоит из одного атрибута (почему?). Модифицированный таким образом алгоритм LRED обозначим через LRED1.

Если в алгоритме PRED множество F* редуцированно слева, то F - редуцированное, неизбыточное покрытие G.

Алгоритмы LRED, LRED1, PRED имеют  сложность O(nm³), где n = |R|, m =|F|.