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

Рис 4.1. Редуцирование слева

Рис. 4.2, Редуцирование справа

Приложение 5

Проверка свойства сохранения F

Пусть F - множество ФЗ, заданных на атрибутах множества R,  ρ = {R_i,  i = 1,..., m} - декомпозиция множества R (),  - множество сохраняемых (поддерживаемых) декомпозицией ρ ФЗ.

Декомпозиция ρ сохраняет все ФЗ из F (далее просто сохраняет F), если F_ρ ≡ F.

Поскольку всегда верно F |= F_ρ, то для проверки данного свойства достаточно установить выводимость F_ρ |= F. Если множество F_ρ известно, то эту выводимость легко проверить, используя     алгоритм   PRF (см. прил. 2). Чаще всего множество F_ρ неизвестно. Выполнять его построение, исходя из F, R и ρ, нецелесообразно, поскольку эта   задача   является труднорешаемой (имеет неполиномиальную сложность по времени). В этом случае удобно воспользоваться алгоритмами PSX⁺ (рис. 5.1), PPRF (рис. 5.2).

Алгоритм PSX⁺ позволяет вычислить Х⁺ над F_ρ, исходя из заданных F, ρ и X. В строке 5 алгоритма PSX⁺ вычисляется замыкание  над F, для чего используется алгоритм SX⁺ (см. прил.2).

Алгоритм PPRF устанавливает выводимость  F_ρ |= X→Y . Применение   его   к   каждой   ФЗ X→Y    позволяет проверить выполнение выводимости F_ρ |= F.

Алгоритмы     PSX⁺,  PPRF имеют полиномиальную сложность по времени.

Рис. 5.1