Проекция с рис. 3.34 иа две последние схемы дает два отношения - MoveStudiol и MovieStudio2 (рис. 3.35 и 3.36) Оба они находятся в 8CNF. Единственный ключ для MovieStudiol {ffle.year}, а еяннственный ключ для MoyieStudo2 - {studtoName}. В обоих случаях не существует нетривиальных зависимостей, не содержащих эти ключи в левой части. О

Рие. 3.35. Отношение MovieStudiol

StudioName studioAddr

Disney

Paramount

Рис. 3.36. Отношение MovieStudio2

Hollywood

i Buena Vista Hollywood

Bo всех предыдущих примерах достаточно одного применения декомпозиции д;!я получения множества отношений, находящихся в BCNF. В обшем случае это не так.

Пример 3.38. Обобщая пример 3.37, можно получить цепь функциональных зависимостей. Рассмотрим отношение со схемой

{title, year, stud oName, president. presAddr)

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

title year studioName <

StudioName president president presAddr

Для этого отношения существует единственный ключ {title, year) Поэтому 1госледние две зависимости нарушают BCNF Декомпозицию можно начать, например, с зависимости

StudioName - president

В первую очередь в правую часть этой зависимости нужно добавить псе ос аль-ные атрибуты из замыкания studioName. Применяя правило транзи ивности к StudioName -> president и presiden -* IpresAddr, получаем зависимость

StudioName -> presAddr

Затем, соединяя две зависимости с одинаковыми левыми частями, получаем

StudioName -> president presAddr

Эти фу11кш1ои;*льная зависимость имеет максимально развернутую правую часть, поэтому произведем лекомиозииню. в результаге чего получаются две схемы:

{title, уеег, studioName} {studioName. president. presAddr}

Первая из них находится в BCNF. Единственным к.1ючом оторой является {StudioName}, но при этом в ней есть зависи\юсть

president -> presAddr

наруигаюшая BCNF. Значит, необходигю продолжить декомпозицию, Hcnatbsyfl расим1ренную зависимость, в правой части которой находится president. В результате получаются три с.чемы в BCNF:

{title, year. studioName] {StudioName. president) {president, presAddr} □

В общем случае можно применять правило декомпозиции столько раз, сколько необходимо для поления отношений в BCNF. Конечный успех обеспечен, поскольку при каждом применении этого правила к отношению R получаются схемы, содержащие меньше атрибутов, чем Л. Как показано в примере 3.35, когда остается только два атрибута, отношение обязательно будет в BCNF.

Декомпозиция действительно всегда приводит к более мелким схемам. Допустим, чго зависимость А, ... А -> В, .. В , нарушает BCNF. Можно предположить, что она уже расширена так, что среди в Д находятся все другие атрибуты, функционально определяемые атрибутами А и все Bj, находящиеся среди А .... А уже удалены нз правой части зависимости.

Одна из схем. получающихся в результате декомпозиции, это все атрибуты Л. за исключением атрибутов В,..... £ , Но по крайней мере один aTpHeji Bj должен существовать, значит, эта схема не включает в себя все атрибуты.

Другая схема содержит все /( ...,А и В,.....В . Это множество не может быть

всеми атрибугами Л, иначе множество {у4 И } было бы надключом для Л

(т.е. атрибуты А.....А функционально определяли бы все остальные атрибуты Л).

Тем не менее ни одна зависимость с надключом в левой части не нарушает BCNF.

Таким образом, обе схемы, полученные при декомпозиции, меньше R. Значит, ряд повторных леком позиций в коиечно.м счете должен привести к множеству отношений, находящихся н BCNF.

3.7-5 Проекция функциональных зависимостей

При декомпозиции схемы отношения необходимо следить, чтобы резу.чьтирую-щие схемы были в BCNF. Из примера 3.38 ясно, что одна из них или даже обе новые схемы могут нарушать RCNF. Но как узнать, находится ли данное отношение п BCNF, еслн для этого отношения не определены зависи.мостн? В лри.мере 3.3S мы рассуждали о зависимостях, которые истинны для новых отношений ad hoc. К счастью, существует pei-улярный метод нахождения функциональных зависимостей для результатов декомпозишиг

Пусть имеется отношение Л, разложенное на отношение 5 и какое-то другое стношенис. Пусть /- -множество функциональных зависимостей, истинных на Л. Для вычисления функшюнальных зависимостей, истинных на S. сделайте следующее.

Упрощение поиска зависимостей

при выведении функщюнальнь х зависимостей для отношения S из зави- i

симостей для R с помощью алгоритма раздела 3.7.5 иногда можно ограничить I

область поиска, не вычисляя замыкания всех подмножеств aTpHejTOB S. Oie- ]

дующие правша облегчают поиск.

1. Необязательно рассматривать замыкание множества всех атрибутов S. \

2. Необязательно рассматривать множество атрибутов, не содержащее j левой части какой-либо зависимости. I

3. Необязательно рассматривать множество, содержащее атрибут, не входящий в левую часть какой-либо зависимости.

Пример 3,39. Пусп> R имеет схему R</\, В, Q D) и для R заааны зависимости А -*В и ВС. Пусть S(A, Q одно из отношений, полученных в результате декомпози-тт R. Вычислим зависимости, которые верны для S.

В принципе, нужно вычислить замыкание каждого подмножества множества {А. С}. Последнее является множеством атрибутов отношения 5. Начнем с {А}. Очевидно, что это множество {А. В, Q. Поскольку В не входит в схему ,5, нельзя утверждать, что А-* В является зависимостью для S. Но С входит в S, поэтому для S устанавливается зависимость А С.

Теперь рассмотрим {С]*. Поскольку С ие входит в левую часть заданной зависимости, в замыкании не появляется ничего нового, т.е. {Q* = [Q. В общем случае множество, не содержащее по крайней мере одной левой части заданной зависимости, не может порождать никаких зависимостей в S.

И наконец, нужно рассмотреть {А, Q. Это замыкание равно {А, В, Q. Значит, мы не нашли никакой новой зависимости. кро.ме той, что была обнаружена при рассмотрении {А). Следовательно, /)С-единствепная зависимость, которую надо установить для S. Конечно, из нее можно вывести другие зависимости для 5, например AD-* С или тривиальную зависимость А-А. Однако их можно получить по правилам, приведенным в разделе 3.6, и не требуется устанавливать спеш1ально при определении зависимостей для S. □

Пример 3.40. Рассмотрим отношение R{A, В, С, D, Е), расчлененное на S{A, В. С) и какое то другое отношение. Пусть для Л уртаиовлены функциональные зависимости A-D, В Е н DEC.

Сначала рассмотрим {А]* = {А, D}. Поскольку D ие входит в схему 5, мы не получаем новых зависимостей. Точно так же \В) - {В, Е] и {Q = {Q не дают новых зависимостей для 5.

Теперь рассмотрим пары. {А, В}* = {А, В, С, D, £}, поэтому для S получается зависимость АВ-* С. Ни одна из остальных возможных пар новых зависимостей для 5 не дает. Разумеется, множество всех атрибуттзв т.е. В. Q, тоже не может дать нетривиальную зависимость д.ля S. Следовательно, единственной зависимо-сгью. которую нужно установить для 5, является АВ-* С. □

Рассмотрите кажлое множество атрибутов А , солержащееся в множестве атрибутов отношения S. Вычислите Л*. Тогда для каждого атрибуте! В, такого как

1) В есть атрибут

2) В в.\однт в А ;

3) В не входит с А,

в 5 выполняется функшнональная зависимость А- В.