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

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

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

 транзитивно зависел через от , но  не минимально. Атрибут  транзитивно зависит от  только через .

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

---

---

---

Главная сайта

---