4. Множество X, к которому невозможно добавить атрибуты, и будет корректным значением замыкания /1г,

Рие. 3.29. Вычисление зомыкония множество атрибутов

Пример 3.2в. Рассмотрим отношение с атрибутами А, В, С. fl, Е и F. Пусть оно имеет функциональные зависимости АВ С, BC-tAD, Ек CF В. Вычислим замыкание \А, В], т.е. {А, В)+.

Начнем сХ = {А, В). Заметим сначала, что все атрибуты левой части функциональной зависимости АВ~* С находятся в X, значит, можно .аобавить атрибуг С, расположенный в правой част этой зависимости. Таким образом, после повторения шага 2 X становится множеством {И, В, Q.

Теперь ясно, что левая часть зависимости BC->AD входит в X, поэтому к X можно добавить атрибугы А м D} А уже входит в X, но D не входит, значит, после .аобавления X становится множеством {А, В, С, £>. Теперь можно использовать зависимость D- Е, чтобы добавить Е к. X, после чего X становится множеством [А, В, С, D, Ё). Дальнейшие изменения X невозможны. В частности, нельзя исполь зовать функциональную зависимость CF-* В, так как ее левая часть никогда не пойдет в X. Следовательно, {А. В}* - {А, В, С, D, £}. О

Зная, как вычислять замыкание любого множесгва атрибутов, можем проверить, следует ли функциональная зависимость А, Aj... А - В из множества зависимостей 5. Сначала вычисляем Hi. 2.....Л)* е помощью множества зависимостей S. Если В входит в {/! >4,.....А }*, тогда

АхА2..А ч> В

действительно следует из S. Если же В не входит в {А А2, ....А }*, данная зависимость не следует из 5. В общем случае можно проверить и зависимость с множеством атрибутов в правой части, так как она является сокращенной записью для множества зависимостей. А, А2 ... А -> В, B... В , следует из множесгва зависимостей 9 тогда и только тогда, когда В В.В , входят в {/)[, Aj,.... А }*.

в BC-s-i-10 -это сскрашенная йвись пары ВС-* А и ВС-эти зависимости можно paccviaTpMBHTb отдельно.

О При желании

Пример 3.29. Рассмотрим отношение и функциональные зависимости из примера 3.2S. Допустим, что нужно проверить, следует ли из этих зависимостей АВ-> D. Вычисляем, как показано выше, \А, В), получаем \А. В, С, D, Е) и, поскольку в это миожссгао входит Д делаем вывод, что АВ > D действительно следует из указанных зависимостей.

Обратимся теперь к зависимости Z) - И. Чтобы проверить, следует ли она из данных завнсимосзей, сначала вычислим \D)*. Начнем с Х~ {D]. Далее можно исиользовать D-i 12, чтобы добавить Ек множеству X. Однако на этом все заканчивается. Другую зависимость, левая часть которой входила бы в X, найти невозможно, поэтому \D\* = {D,E]. Но А не входит в множество {D, Е), значит, Z)- /4 не следует из данных зависимостей. □

3-6.4 Правило транзитивности

Правило пранзитивности позволяет строить новую фуикцноназьную зависимость из двух заданных.

Р.слн ,4, А,... А Д, Я,... В, и By А... В - С, С,... Q верны в отношении Я.

то Ai А-)... А - С С,... тоже верна в Л.

Если некоторые из С находятся среди А. ик можно удалить из правой части по правилу тривиальной зависимости.

Для обоснования правила транзитивности можно применить способ проверки из раздела 3.6.3. Чтобы проверить, верна ли И, И,.../1 - С, С,... С, нужно вычислить замыкание {.! /1 /1 )

Функциональная зависимость /1,/lj... 5,... Д, означает, что все .....В . входят в \А А2.....А.,)*. Тогда можно использовать зависимость

) Обоснование действия алгоритма замыкания

Обосновать алгоригм вычисления замыкания достаточно просто. Мнлук-uiiefi по числу применении операции наращивания шага 2 можно доказать, что аля каждого атрибута D в .V верна функциональная зависимость A... А - D

(если D входит также и в левую часть, зависимость тривиальна). Другими cлoll:l.иI- каждое отношение Л, удовлетворяющее всем зависимостям в S.

1 удонлетворяет и /I;... А D.

Базис индукции - О шагов. Тогда D должно совпадать с одним нз

j ,4 А,.....А и зависимость ,-1, .А,... А -> D верна на любом отношении, так как

; она тривма.1ьная.

I По индукции допусш.ч, что D было добавлено, ко1Да использовалась Г зависимость С Д,... В ,- А В силу и1шуктивного предположения Л удов-

1 детворяет /4, А-,... А -* В, для всех / = 1,2.....т. Другими словами, любые

I два кортежа из Я. совпадающие по всем А Aj,... А , совпадают и по всем I В,. 5, . Но поскольку Я удовлетворяет В, Bi... В ,-* D, эчн два кортежа

совпадают и ио LX Следовательно, R удовлетворяет зависимосги /4, И,... А -> D.

Из этого доказательства следует, что алгоритм замыкания является

ii правильным: если он помешает D в {/4 A...../1 )*, значит, A А-... А ~ D -

i истинная зависимость. Нужно еще доказать и его пояноту. а именно: \ если AiA-,... .4 D верно, то Сбудет noMCUicHO в {A,A2. ...,/! )*. Однако

такое доказательство выходит за рамки данной книги.

В, fi,... В-у С, С,... Q для добавления С С,... Q. в {/I /) .... z) } . Но поскольку все С входят в {/4 /( ., А )*, можно сделать вывод, что зависимость /1 ... -4 -* С Cj ... Q верна для любого отношения, удовлетворяюшего А, А ... А - В, В,... В и В, В,... С, С,... Q.

Замыкания и ключи

Заметим, что {Ах.А-...../) ) является множеством всех атрибутов тогда

и только тогда, когда /I А, ...,/) -надоюч рассматриваемого отношения.

Только в этом случае /4 А.....А функционально определяет все остальные

атриб\т~ы. Чтобы проверить, является ли А, /4 А ключом отношения,

достаточно сначала убедиться, что {/4 А...../< }+ -это все атрибуты, а затем

установить, что ни для какого множества S, полученного удалением одного

из атрибутов из /4,...../4 ), замыкание ие является множеством всех

атрибутов.

Пример 3.30. Начнем с отношения Movie (см. рис. 3.12), построенного в разделе 3.2.4 для представления четырех атрибутов класса Movie и его связи с классом Studio.

Допустим, мы решили представить в этом же отношении данные о студии, владеющей фильмом. Для простоты в качестве адреса студии введем только гороа В результате получим следующее отношение:

Можно утверждать, что здесь верны две зависимости:

title year -> studioName StudioName studloAddr

Первая обосновывается тем, что связь ownedBy класса Movie однозначна (фильмом владеет только одна студия), а вторая тем, что атрибут address класса Studio однозначен, он имеет тип string (см. рис. 2.6).

Правило транзитивности позволяет соединить эти две зависимости в одну:

title year -> studioAddr

Она означает, что название и год выпуска (фильма) определяет адрес ст>дии, владеющей этим фильмом. □