Функциональную завнснлюсгь часто можно выразить различными способами, ие изменяя множества допустимых экземпляров отношения; в таком случае говорят, что множества завис)1мостей эквивалентны. Считается, что множество фуикци-OHiUibHbix зависимостеГ! S стЪет из множества функциональных зависимостей Т. если каждый экземпляр от1юшения. уловлстворяюш1иТ всем зависимостям в Г, удовлетворяет и всем зависимостям в S. Заметим, что .множества зависимостей S и 7 эквивалентны, если 5 следует из Г, а 7 -из 5.

В этом разделе рассмотрим множество полезных правил, касающихся функциональных зависимостей. Эти npabima позволяют заменять множество зависимостей эквивалентным е.му множеством или добавлять к множеству зависимостей другие множества, которые следуют из исходного множества. Примером таких правил является правим транзитивности, позволяющее следовать по цепи функциональных зависимостей, как в примере 3.26. Введем также алгоритм ответа на общий вопрос: следует ли функциональная зависимость из одной или нескольких других зависимостей.

3.6.1 правило расщепления/соединения

с разделе 3.5.1 функциональная зависимость

А,А,...А В, Л... В была определена как сокращение множества зависимостей

А, А,... А г, Ау А2 ... А - А

А, Аз ... А В ,

Следовательно, можно расщепить атрибуты, стоящие в правой части, так, чтобы только одни атрибут появлялся в правой части каждой функциональной зависимости. Можно также заменить множество зависимостей с общей левой частью единственной зависимостью с той же левой частью и всеми правыми частями, соединенными в одно множество атрибутов. В любом случае новое множество зависимостей эквивалентно исходному. Такую эквивалентность можно реализовать двумя способами.

Функциональную зависимость /I, А ...А -> В, В-... В, можно заменить множеством функциональных зависимостей AiAi...A -*BiSU\n /= I, 2,..../п. Такое преобразование называется правилом расщепления.

Множество фyнкцlюиarьныx зависимостей А, /),... А -> Bi пля /=1,2.....т

можно заменить единственной функциональной зависимостью

А, /)>... А - B В,... В, . Такое преобразование называется правшам соединения.

Например, в примере 3.20 было показано что множество зависимостей

title year -+ lengtti title year filmType title year -> studioName

эквивалентно единственной зависимости

title year -> length filmType studioName

Может показаться, что расшелленне применимо и к левым частям фуикцио-нальны.х зависимостей. Но следующий пример показывает, что правила расщепления левых частей не существует.

Пример 3.27. Рассмотрим зависимость

title year - length

для отнощения Movie из примера 3.20. Расщепив его левую часть, получим две ложные зависимости

title -+ length year -т- length

Другими словами, title функшюнально не определяет length, так как могут существовать два фильма различной длины, но с одним и тем же названием (например, Кинг Конг). Аналогично, year функционально не определяет length, так как в один год может быть выпушено множество фильмов различной длины □

3.6.2 Тривиальные зависимости

Функциональная зависимость A А,... А -* В называется тривиальной, если В совпадает с одним из А. Например, зависимость

title year -> title

тривиальна.

Любая тривиальная зависимость верна на любом отношении, так как она означает, что два кортежа, совпадающие по всем атрибутам AAj, ..,А , совпадают по одному из них. Значит, можно допускать любую тривиальную зависимость, не подтверждая ее знаниями о данных.

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

Допуская тривиальные зависимости, мы допускаем и зависимости, в которых отдельные атрибуты находятся и справа, и слева. Зависимость А, А... А -* В В-... В ;.

травиаяънс, если {£ i,является подмножеством множесгва (И Ai,.... А );

нетривиальна, если по крайней мере одно В не входит в множество {И А-,.... Д,};

полностью нетривиальна, если ни одно В, не совпадает ни с одним А,.

Значит,

title year year length

нетривиальна, но не является полностью нетривиальной. Удалив year из правой части, получим полностью нетривиальную зависимость.

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

Функшюнальная зависимость /1, А-,... А В, 5,... £ , эквивалентна

Ах Ai... А - С С,... Qi Де все С - это такие В, которые не совпадают с А

Это правило, представленное на рис. 3.28, называется праваюм тривимьной

зависимости.

>-Аа

- Са Bs -

Бели t и о Они должны совпадают совпадать в Ва

Значит,

они обязательно совпадают и в Cs

Рие. 3.28. Провипо тривиальной зояисимосто

3.6-3 Вычисление замыкания атрибутов

Прежде чем перейти к другим правилам, рассмотрим общий принцип, из которого следуют все правила. Пусть (/! А, ., А ) есть множество атрибутов, а лиюжество функциональных зависимостей. Замыкание {Ai, At,.... А по зависимостям в S есть такое множество атрибутов Д что любое отношение, удовлетворяющее всем зависимостям в S, удовлетворяет также зависимости А<, Ai... А - В. Значит, Af Ai... А В следует из зависимостей S. Замыкание множесгва атрибугов Аг.....Л) обозначается \Ai, А,.....А )*. Для того чтобы упростить ход рассуждений о вычислении замыканий, допускаются тривиальные зависимости, поэтому Ai.A, .... А всегда входят в H, А,.... А \*.

На рис. 3.29 изображен процесс вычисления замыкания.

Начиная с заданного множества атрибутов, будем последовательно расширять его. .10бавляя правые части функциональных зависимостей тогда, когда вводятся их левые части. Множество, которое больше расширеть уже нельзя, яаляется замыканием. Следующие шаги описывают алгоритм вычислс1тя замыкания множества атрибутов {Лх, А,.... А \ по отношению к множеству функциональны.х зависи.мо-стеП.

1. Пусть А -множество трибутов, которое в конечном счете станет замыканием. Начнем с того, что -V есть {Ах. И},А.

2. Осуществляем поиск такой функциональной зависимости В\ ft ... В , -+ С.

в коюроП псе Л.....В , входят в множество атрибутов Л, а С нет.

Зате.м добавляем С к множеству X.

3. Повторяем шаг 2 необходимое число раз, пока к множеству А уже невозможно будет добавить атрибуты. Поскольку .V может только расги. а множество атрибутов любого отношения должно быть конечным, процесс

з;и1ершается.