Избыточные функциональные зависимости

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

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

Приемы удаления избыточных ФЗ

Транзитивные зависимости. Одним из вариантов появления в наборе ФЗ избыточных зависимостей является наличие ФЗ, представляющих транзитивные зависимости, которые определяются следующим образом:

Если A -> B и B -> C, то A -> C - транзитивная зависимость.

Здесь следует подчеркнуть два момента:

1. Транзитивная зависимость A -> C, приведенная в определении выше, является вполне корректной зависимостью.

2. Если A -> B, B -> C и A -> C входят в набор ФЗ, то A -> C является избыточной и ее использование в процессе проектирования не требуется. Действительно, транзитивная зависимость A -> C причинит больше вреда, чем пользы при проектировании, и ее следует исключить из набора перед началом проектирования.

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

Вид первый формулируется следующим образом: Если А -> В, то А,Z -> В является корректной, но избыточной ФЗ. Атрибут Z был добавлен к детерминанту А без привнесения какой-либо новой информации в процесс проектирования. (Здесь А,В и Z - атрибуты, каждый из которых может быть составным).

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

Если А -> В, то А,Z -> B,Z является корректной, но избыточной ФЗ.

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

 Рассмотрим вкратце еще три приема удаления избыточных ФЗ.

 Два наиболее простых для понимания приема удаления связаны с объединением и декомпозицией ФЗ, которые определяются следующим образом:

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

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

 Пятая разновидность избыточности называется псевдотранзитивностью.

Если X -> Y и Y,W -> Z, то X,W -> Z является избыточной в силу псевдотранзитивности. Этот тип избыточности возникает в тех случаях, когда в получаемых ФЗ обнаруживаются детерминанты. При обнаружении псевдотранзитивной зависимости ее необходимо удалить.

Минимальное покрытие

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

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

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

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