Удаление избыточных функциональных зависимостей

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

Избыточной ФЗ называется зависимость, не заключающая в себе такой информации, которая не могла бы быть получена на основе других зависимостей из числа использованных при проектировании БД.

Поскольку избыточная ФЗ не содержит уникальной информации, она может быть удалена из набора ФЗ без отрицательного воздействия на результаты. Избыточные ФЗ удаляются на начальном этапе проектирования до декомпозиции универсального отношения.

Одной из причин появления в наборе ФЗ избыточных зависимостей является генерация ФЗ с помощью концепции транзитивной зависимости. Транзитивная зависимость определяется следующим образом: если A ® B и B ® C, то A ® C — транзитивная зависимость.

Следует отметить два момента. Во-первых, транзитивная зависимость A®C является корректной зависимостью. Во-вторых, если все три зависимости A ® B, B ® C и A ® C входят в набор ФЗ, то зависимость A ® C является избыточной и ее использование в процессе проектирования не требуется. Действительно, транзитивная зависимость A ® C причинит больше вреда, чем пользы при проектировании, в чем мы убедились, когда анализировали правило цепочек. Поэтому транзитивную зависимость следует исключить из набора ФЗ перед началом декомпозиции.

Рассмотрим примеры того, как можно упростить набор ФЗ до начала проектирования. На рис.1.11(а) показан исходный набор ФЗ до начала проектирования. На рис.1.11(г) показан набор неизбыточных ФЗ, выделенных путем удаления всех транзитивных зависимостей из исходного набора. На рис.1.12 показана процедура декомпозиции и получения набора отношений в НФБК.

A C D A ® B

A ® C

A ® D

B ® C

B B ® D

C ® D

(а) Исходный набор ФЗ

A C D A ® B

A ® C

B ® C

B B ® D

C ® D

(б) A ® D удалена, так

как A ® C и C ® D

A C D A ® B

A ® C

B ® C

B C ® D

(в) B ® D удалена, так

как B ® C и C ® D

A C D A ® B

B ® C

B C ® D

(г) A ® C удалена, так как A ® B и B ® C и результате
получен неизбыточный набор ФЗ

Рис.1.11. Удаление транзитивных зависимостей.

A B C D R(A, B, C, D)

(а) Набор ФЗ при отсутствии избыточности

C D R1(C, D)

A B C R2(A, B, C)

(б) Извлечение зависимости C ® D из цепочки

C D R1(C, D)

B C R3(B, C)

A B R4(A, B)

(в) Извлечение зависимости B ® C из R2(A, B, C)

Рис.1.12. Получение набора НФБК-отношений.

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

Первый вид избыточности формулируется следующим образом (здесь A, B, Z — атрибуты или наборы атрибутов): если A ® B, то A, Z ® B является корректной, но избыточной ФЗ. Атрибут Z добавляется к детерминанту А без привнесения какой-либо новой информации в процесс проектирования.

Второй вид избыточности возникает в случае добавления к обеим частям данной ФЗ одного и того же атрибута с целью формирования новой зависимости: если A ® B, то A,Z ® B,Z является корректной но избыточной зависимостью.

На рис.1.13 приведены примеры обоих видов избыточности, связанных с добавлением атрибутов.

(а) A B

Добавочная ФЗ

(избыточная)

Z

(б) Добавленная ФЗ

(избыточная)

A B

Z

Рис.1.13. Примеры добавления атрибута.

Помимо правил транзитивности и добавления для уменьшения или модификации исходного набора ФЗ и получения другого, эквивалентного ему набора ФЗ можно использовать еще три правила, связанных с объединением, декомпозицией и псевдотранзитивностью функциональных зависимостей.

Объединение ФЗ: если А ® В и А ® С, то А ® В,С.

Декомпозиция ФЗ: если А ® В,С, то А ® В и А ® С.

На рис.1.14 дано графическое представление каждого правила.

В В

А Þ А

С С

(а)

В В

А Þ А

С С

(б)

Рис.1.14. Примеры объединения (а) и декомпозиции (б).

Если А ® В и B,Z ® C, то А,Z ® C является избыточной в силу псевдотранзитивности. Пример псевдотранзитивности приведен на рис.1.15. Этот тип избыточности возникает в тех случаях, когда в получаемых ФЗ обнаруживаются составные детерминанты.

На рис.1.16 показаны способы преобразования исходного набора ФЗ в набор избыточных ФЗ с помощью некоторых рассмотренных правил (правил вывода).

A Z Псевдотранзитивная ФЗ

(избыточная)

С

В

Рис.1.15. Графическое представление

псевдотранзитивности.

A ® B, C

A B D A ® D

A ® E

E ® C

E C B ® D

B, C ® D

(a) Исходный набор ФЗ

A ® B, C

A B D A ® D

A ® E

E ® C

E C B ® D

(б) B, С ® избыточная ФЗ,

т.к. имеет добавленный атрибут С к ФЗ B ® D

A ® B

A B D A ® С

A ® E

A ® D

E C E ® C

B ® D

(в) A ® B, C замещена на A ® B, A ® С (декомпозиция)

A ® B

A B D A ® E

B ® D

E ® C

E C

(г) A ® С и A ® D избыточны из-за транзитивности

Рис.1.16. Исключение избыточных ФЗ
с помощью правил вывода.

Дата добавления: 2015-07-20