Проверка зависимостей на элементарность

Зависимости без “лишних” атрибутов слева называются элементарными. Следующий пример показывает, как можно привести зависимости к элементарному виду.

Пример 22. Пусть множество функциональных зависимостей

F = {ABE ® C, A ® B, B ® A} задано на множестве атрибутов U = ABCE.

Очевидно, анализу на элементарность должны подвергаться зависимости, в левой части которых содержится несколько атрибутов. В данном примере такой зависимостью является ABE ® C. Остальные зависимости уже являются элементарными.

Попытаемся исключить атрибут A, т.е. проверим справедливость зависимости BE ® C. Для этого, используя факт выводимости зависимости, вычислим (BE)⁺ = BEA C. Правая часть этой зависимости C Î (BE)⁺. Следовательно, зависимость BE ® C выводится из F, то есть (BE ® C) Î F⁺, и атрибут A можно исключить. В результате множество F можно заменить на F₁ = {BE ® C, A ® B, B ® A}. Рассмотрим теперь полученную зависимость BE ® C и попытаемся исключить из нее атрибут B. Чтобы это можно было сделать, установим справедливость зависимости E ® C. Так как E⁺ = E и C Ï E⁺, то делаем вывод о невозможности исключения B.

Попытаемся теперь из зависимости BE ® C исключить атрибут E, то есть установить справедливость зависимости B ® C. Так как B⁺ = BA и C Ï B⁺, то делаем вывод о невозможности исключения атрибута E. Таким образом, окончательно имеем

F₁ = {BE ® C, A ® B, B ® A}.

Множество F₁ содержит только элементарные зависимости, но количество зависимостей не уменьшилось.

Нетрудно показать, что множества F и F₁ эквивалентны.

В рассмотренной процедуре порядок просмотра зависимостей также влияет на результат. Формальная процедура, оптимизирующая этот процесс, в настоящее время неизвестна. Однако известна рекомендация о первоочередном анализе на избыточность атрибутов той зависимости, которая содержит наибольшее количество атрибутов в левой части.

В следующем примере показано, как приведение зависимостей к элементарному виду, может уменьшить количество зависимостей.

Пример 23. Пусть множество функциональных зависимостей

F = {L ® KA, A ® DOXZC, DEM ® K, D ® EK} справедливо на множестве атрибутов U = ACDEKLMOXZ.

Проанализируем зависимость DEM ® K на элементарность. Остальные зависимости уже являются элементарными.

Пытаемся из анализируемой зависимости исключить атрибут D. Используя факт выводимости, установим справедливость зависимости EM ® K. Так как EM⁺ = EM и KÏ EM⁺, то делаем вывод о невозможности исключения D.

Пытаемся из зависимости DEM ® K исключить атрибут E, т.е. проверяем справедливость зависимости DM® K. Так как DM⁺ = DME K и KÎ DM⁺, то атрибут E можно исключить. В результате множество F можно заменить на F₁ = {L ® KA, A ® DOXZC, DM ® K, D ® EK}.

Продолжаем процесс исключения атрибутов теперь уже из зависимости DM ® K.

Пытаемся исключить из этой зависимости атрибут M. Так как D⁺ = DE K и KÎ D⁺, то атрибут M можно исключить. В результате множество F₁ можно заменить на F₂ = {L ® KA, A ® DOXZC, D ® K, D ® EK}. Поскольку зависимость D ® K получается из декомпозиции правой части зависимости D ® EK, то D ® K является лишней и ее можно исключить из F₂.

Таким образом, вместо F окончательно имеем множество

F₃ = {L ® KA, A ® DOXZC, D ® EK}, которое содержит меньше зависимостей, чем исходное множество F.

Нетрудно показать, что множества F и F₃ эквивалентны.