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

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

Во-первых, временная сложность процесса не ограничивается полиномиальной [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].


Содержание раздела

---

---