Информационное обеспечение систем управления

       

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


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

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

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



Содержание  Назад  Вперед