Полное множество правил вывода

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

1. Рефлексивность. Если й, .....Д } с .... Л,},

то .4i ,- 3 .. А В Sj... flu. Это то, что мы называли тривиальными зависи.мостями

2. Ноиашение. Если At /Ь ... А fi £>... й ,

то At Л.... An С Ci... Q -> В, Bi... В С) G>... Са для любого множества атрибутов С, Ci..... Сд..

3. Транзитивность. Если At А... А - В Вг... В ; и /? ft - Ди С Ci... С*, то At Аг ... А - С, Сг... Q.

3-6.5 Замыкающие множества

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

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

Более того, иногда можно выбирать, какие зависимости использовать для представления полного множества зависимостей для отношения. Любое множество заданных зависимостей, из которого можно вывести все зависимости для отношения, называется базисом для этого отношения. Еслн полное множество зависимостей нельзя вывести ни из одного собственного подмножества зависимостей, входящих в базис, базис считается минимальным.

Пример 3.31. Рассмотрим отношение R{A, В, О, в котором каждьт атрибут функционально определяет все остальные атрибуты. Здесь полное множество выводимых зависимостей состоит из шести зависимостей, содержащих по одному агри-буту справа и слева: А-л В, А-С, В-А. В-С, С-А и С-*В. Оно содержит также гри нетривиальные зависимости с двумя афибутами слепа каждая: АВ- С, AC-i В и ВС-А. В не.\1 есть сокращения для пар зависимостей типа А -> ВС. к тому же мо;-кно еще добавить фивиальные зависимости типа А-А или зависи-люсги типа АВ- ВС. не являющиеся полностью тривиальными (хотя строгое определение функиионА1Ьиой зависимости не требует перечисления тривиальных зависимосгей. частично тривиальных зависимостей или зависимостей с лиюжесг-вом атрибутов и правых частях).

T:iKoe отношение и его зависилюсти имеют множество мини.мапьных базисов, например:

{А -> В. В- А. В- С, С В]

{л -> в, д с. с + Л}

Преллагае.м читателю в качестве упражнения найти другие базисы и мини.мальные базисы. □

3-6.6 Упражнения к разделу 3.6

* Упражнение 3.6,1. Рассмотрим отношение со схемой Л(Л, В, С, D) и с фуик-иионапьными зависимостями АВ~* С, С-> D и DA.

a) Какие нетривиальные зависимости следуют из этих зависимостей?

b) Укажите все ключи для fi.

c) Какие надключи для Л не являются оючали1?

Упрожнение 3.6,2. Выполните упражнение 3.6.1 для следующих схем и зависимостей:

i) S{A, В, С. D) с функциональными зависимостями /1->5, Д->Си В- D.

О) ЦА, B.C,D)c функциональными зависимостями АВ С, ВС-* D, CD-лА w ADB.

lii) (ЛА, В, С D) с функциональными зависимостями /)->£, ВС, С- D и D -А.

Упрожнение 3.6.3. Обоснуйте следующие правила с помощью теста на замыкание, описанного в разделе 3.6.3.

*а) Пополнение левых частей. Если Л Аг... А В - функциональная зависимость, а С - другой атрибут, то AtAi...A C--> В.

b) Завершенное пополнение. Если /!/2 - Л-> - функциональная зависимость, а С - другой атрибут, то А\Аг-. А С ВС. Заметим, что из этого правила легко вывести правило пополнения , упомянутое в разделе 3.6.5 среди аксиом Армстронга.

c) Псевдотранзитивноеть Пусть верны зависимости /(, Ai... А ~у В, В2... Д и С[ Сг... Ск- а все В на,ходятся среди С. Тогда верна зависимость AyAi... А Е[ Ег... Ej-t D, где все Е совпадают с теми С, которых нет среди В.

d) Дополнение. Если верны функциональные зависимости

Ai А2... А -> Bi Bi... В , и С CS ... Са-- Dl Di... Dj, то верна и зависимость

/Il А,... А С, С, ... С, В, В,... В, D, D,... Ц

Из нее нужно удалить один экземпляр каждого атрибута, который появляется одновременно среди А и среди С и.ли же среди В и среди D.

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

*а) Если А- В, то В-А.

b) Если С и Л С, то В-> С.

c) Если АВ С, го АС или С.

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

! Упражнение 3.6.6. Пуств Л и множества атрибутов. Покажите, что еслн .V -г ), Tt-i с ) . где з:1М1>1кания берутся по отношению к одному и тому же

китожесгву фуи1ч111101111.1ьны\ занисимостеи.

! Ипрожиенис 3.6.7. Докажите, что (.V+Г = V+.

!! Упрожнение 3.6.8. Множество атрнОхтов Л замкнуто (по отношению к данному множеству функциональных зависимсктей)- если X* = X. Рассмотрим отношение со схемой R{A. В. С. D) и неизвестным множеством фу1Ичинона.П1.иых зависимостей. М.\ можно оС>нар>жить- если известно, какие множества атрибутов замкнуты. Как i-иl будут зависилюсти. если:

al все множества четырех атрибутов замкнуты;

b) замкнуты только множества 0 и \А. В. С. D\:

c) замкнуты только множества 0, [А, В) и \А, В. С, D\.

! Упрожнение 3.6.9. Найдите все минимапьные базисы Д1Я зависимостей и отношений из примера 3.31.

!1 Упрожнение 3.6.10. Покажите, что если функциональная зависимость / следует из некоторых заданных зависимостей то можно вывести F из этих зависимостей с помошью акс1юм Армстронга (определенных в разделе 3.6.5). Подсказка: проверьте iLiropiiTM вычисления замыкания множесгва атрибутов н покажите, как можно имитировать любой шаг этого алгоритма, выво.1я функциональные зависимости с помошью аксиом Армстронга.

3.7 Разработка схем реляционных БД

Как уже неоднократно отмеча;юсь, при прямом преобразовании объектно-ориеитироианиых ODL-лроектов (а также E/R-проектов) в схе.мы реляционной БД позникуют некоторые проблемы. Главная из них избыточность--повторение одного ()акта в нескольких кортежах. Наиболее распространенная причина избыточности - соединение однозначных и многозначных свойств объекта в одном отношении. Например, в разделе 3.2.2 была показана избыточность, возникающая при попытке сохранить однозначную информацию о фильме, например о его длине, вместе с многозначными свойствами типа множества кинозвезд, занятых в этом фильме. Такие пробле\1ы просматриваются на рис. 3.27. который воспроизведен здесь как рис. 3.30. .Аналогичная избыточность возникала и тогда, когда мы пытались сохранить однозначную информацию о дате рождения кинозвезды вместе с се адресами.

Pm£. 3.30. Отношение Movie с ономолилзд