2.4.3.7. Недостатки нормализации посредством декомпозиции

При нормализации схемы отношения посредством декомпозиции возникает ряд проблем.

Во-первых, временная сложность процесса не ограничивается полиномиальной [10]. В терминах размера схемы отношения и заданного множества F-зависимостей схема отношения может обладать экспоненциальным числом ключей. Кроме того, проверка атрибута схемы на непервичность является NP-полной задачей.

Во-вторых, число порожденных процессом схем отношения может оказаться большим, чем в действительности необходимо для 3НФ.

Пример 2.13. Пусть заданы схема и . Ключами относительно являются и . Используя транзитивную зависимость от через , разлагаем R следующим образом:

K

K

Далее в используем транзитивную зависимость Е от АВ через В для получения

K

K

Окончательная схема базы данных в 3НФ имеет вид

R

Существует декомпозиция R в ЗНФ с двумя схемами отношений, а именно:

K

K

Третья проблема состоит в том, что при декомпозиции схемы отношения могут возникнуть частичные зависимости. Эти зависимости могут породить в окончательной схеме базы данных больше схем, чем это в действительности необходимо.

Пример 2.14. Для схемы отношения и . атрибут А является единственным ключом в R относительно . Атрибут транзитивно зависит от через . Разлагая, получаем

K

K

Фактическим ключом является , но от него частично зависит. Следовательно, транзитивно зависит от . Схему следует разложить в

K

K

Схемы , и образуют схему базы данных в 3НФ для . Однако схемы отношений и также образуют схему базы данных в 3НФ для .

Этих недостатков можно избежать, если при декомпозиции следить за тем, чтобы промежуточное множество атрибутов в разлагаемой транзитивной зависимости было минимальным. В примере 2.14 атрибут транзитивно зависел через от , но не минимально. Атрибут транзитивно зависит от только через .

Четвертая проблема состоит в том, что для построенной схемы базы данных заданное множество F-зависимостей может оказаться ненавязанным [10].

Пример 2.15. Пусть заданы схема и . Исключив транзитивную зависимость от через , получаем

K

K .

Множество ненавязано схеме базы данных R из-за того, что зависимость невыводима из F-зависимостей в , приложимых к или (это утверждение должно быть подтверждено вычислением ).

Наконец, пятая проблема. С помощью декомпозиции можно породить схемы со «скрытыми» транзитивными зависимостями.

Пример 2.16. Пусть заданы схема и . Атрибуты являются ключом , а частично зависит от . При декомпозиции получаем

K

K .

Несмотря на то, что , формально находятся в 3НФ, в существует «скрытая» транзитивная зависимость от .

Чтобы избежать проблем, возникающих при декомпозиции схем отношений, необходимо использовать другие методы получения третьей нормальной формы, например, метод синтеза 3НФ [10].