КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ и II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ для

R122.

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

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

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

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

Пример 2.13. Пусть заданы схема R(A, В, С, D, Е) и F={AB→CDE, AC→BDE, B→C, С→В, C→D, В→Е}. Ключами R относительно F являются АВ и АС. Используя транзитивную зависимость D от АВ через С, разлагаем R следующим образом:

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

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

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

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

Пример 2.14. Для схемы отношения R(A, В, С, D) и F={A→BCD, С→D}. атрибут А является единственным ключом в R относительно F. Атрибут D транзитивно зависит от А через ВС. Разлагая, получаем

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

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

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

64