Тема_5 (1122344), страница 2
Текст из файла (страница 2)
Кузнецов. Базы данных.15 Проектирование РБДЭлементы теории функциональных зависимостей (7)Базовые определения и утверждения (6)Определение 5.2. Тривиальная функциональнаязависимостьFD A→B называется тривиальной, если A ⊇ Bт. е. множество атрибутов A включает множество B или совпадает смножеством BОчевидно, что любая тривиальная FD всегда выполняетсяНапример, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ всегдавыполняется FD{СЛУ_ЗАРП, ПРО_НОМ} → СЛУ_ЗАРПЧастным случаем тривиальной FD является A → AПоскольку тривиальные FD выполняются всегда, их нельзятрактовать как ограничения целостности, и поэтому они непредставляют интереса с практической точки зренияОднако в теоретических рассуждениях их наличие необходимоучитывать22.10.2009С.Д. Кузнецов. Базы данных.16 Проектирование РБДЭлементы теории функциональных зависимостей (8)Базовые определения и утверждения (7)Определение 5.3.
Замыкание множества FDЗамыканием множества FD S являетсямножество FD S+, включающее все FD,логически выводимые из FD множества SДля начала приведем два примера FD, изкоторых следуют (или выводятся) другие FDБудем снова пользоваться отношениемСЛУЖАЩИЕ_ПРОЕКТЫДля этого отношения выполняется, например,FDСЛУ_НОМ → {СЛУ_ЗАРП, ОТД_НОМ}Из нее выводятся FDСЛУ_НОМ → СЛУ_ЗАРП и СЛУ_НОМ → ОТД_НОМ22.10.2009С.Д. Кузнецов.
Базы данных.17 Проектирование РБДЭлементы теории функциональных зависимостей (9)Базовые определения и утверждения (8)В этом отношении СЛУЖАЩИЕ_ПРОЕКТЫимеется также пара FD СЛУ_НОМ → ОТД_НОМ иОТД_НОМ → ПРОЕКТ_РУКИз них выводится FD СЛУ_НОМ → ПРОЕКТ_РУКFD вида СЛУ_НОМ → ПРОЕКТ_РУК называютсятранзитивными, поскольку ПРОЕКТ_РУК зависит отСЛУ_НОМ «транзитивно», через атрибут ПРО_НОМОпределение 5.4.
Транзитивнаяфункциональная зависимостьFD A → C называется транзитивной, еслисуществует такой атрибут B, что имеютсяфункциональные зависимости A → B и B → C иотсутствует функциональная зависимость C → A.22.10.2009С.Д. Кузнецов. Базы данных.18 Проектирование РБДЭлементы теории функциональных зависимостей (8)Базовые определения и утверждения (7)Подход к решению проблемы поиска замыкания S+множества FD S впервые предложил Вильям АрмстронгИм был предложен набор правил вывода новых FD изсуществующих эти правила обычно называют аксиомами Армстронга, хотясправедливость правил доказывается на основеопределения FDПусть A, B и C являются (в общем случае, составными)атрибутами переменной отношения rМножества A, B и C могут иметь непустое пересечениеДля краткости будем обозначать через AB A UNION B.22.10.2009С.Д. Кузнецов. Базы данных.19 Проектирование РБДЭлементы теории функциональных зависимостей (9)Базовые определения и утверждения (8)Тогда для любого значения r:если B ⊆ A, то выполняется FD A → B (аксиомарефлексивности);если выполняется FD A → B, то выполняется иFD AC → BC (аксиома пополнения);если выполняются FD A → B и B → C, товыполняется и FD A → C (аксиоматранзитивности)22.10.2009С.Д.
Кузнецов. Базы данных.20 Проектирование РБДЭлементы теории функциональных зависимостей (10)Базовые определения и утверждения (9)Докажем истинность этих «аксиом».Истинность первой аксиомы Армстронга (B ⊆ A влечет A → B)следует из того, что при B ⊆ A FD A → B является тривиальной.Справедливость второй аксиомы (A → B влечет FD AC → BC )докажем от противногоПредположим, что FD AC → BC не соблюдаетсяЭто означает, что в некотором допустимом теле значения переменнойотношения r найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a),но t1 {BC} ≠ t2 {BC} (b)(здесь t {A} обозначает проекцию кортежа t на множество атрибутов A).По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}Поскольку имеется FD A → B, должно соблюдаться равенство t1 {B} = t2{B}Тогда из неравенства (b) следует, что t1 {C} ≠ t2 {C}, что противоречитналичию тривиальной FD AC→CСледовательно, предположение об отсутствии FD AC → BC не являетсяверным, и справедливость второй аксиомы доказана22.10.2009С.Д.
Кузнецов. Базы данных.21 Проектирование РБДЭлементы теории функциональных зависимостей (11)Базовые определения и утверждения (10)Аналогично докажем истинность третьейаксиомы Армстронга (A → B и B → C влечет A →C)Предположим, что FD A → C не соблюдаетсяЭто означает, что в некотором допустимом телеотношения найдутся два кортежа t1 и t2, такие что t1 {A}= t2 {A}, но t1 {C} ≠ t2 {C}Но из наличия FD A → B следует, что t1 {B} = t2 {B}, апотому из наличия FD B → C следует, что t1 {C} = t2 {C}Следовательно, предположение об отсутствии FD A →C не является верным, и справедливость третьейаксиомы и утверждения в целом доказана22.10.2009С.Д.
Кузнецов. Базы данных.22 Проектирование РБДЭлементы теории функциональных зависимостей (12)Базовые определения и утверждения (11)Можно доказать, что система правил выводаАрмстронга полна и совершенна (sound andcomplete) в том смысле, чтодля данного множества FD S любая FD, потенциальновыводимая из S, может быть выведена на основеаксиом Армстронга, иприменение этих аксиом не может привести к выводулишней FDТем не менее, Дейт по практическимсоображениям предложил расширить базовыйнабор правил вывода еще пятью правилами,для которых мы сразу покажем, что они выводятся изисходных аксиом Армстронга22.10.2009С.Д. Кузнецов.
Базы данных.23 Проектирование РБДЭлементы теории функциональных зависимостей (13)Базовые определения и утверждения (12)Для любого атрибута A выполняется FD A → A(аксиома самодетерминированности)прямо следует из аксиомы рефлексивностиЕсли выполняется FD A → BC, то выполняютсяи FD A → B и A → C (аксиома декомпозиции)из аксиомы рефлексивности следует, что выполняетсяFD BC → B;из аксиомы транзитивности следует, что выполняетсяFD A → B;аналогично, из аксиомы рефлексивности следует, чтовыполняется FD BC → C, аиз аксиомы транзитивности следует, что выполняетсяFD A → C22.10.2009С.Д.
Кузнецов. Базы данных.24 Проектирование РБДЭлементы теории функциональных зависимостей (14)Базовые определения и утверждения (13)Если выполняются FD A → B и A → C, то выполняется и FD A→ BC (аксиома объединения)из аксиомы пополнения следует, что выполняется FD A → AB и AB→ BC;из аксиомы транзитивности следует, что A → BCЕсли выполняются FD A → B и C → D, то выполняется и FDAC → BD (аксиома композиции)из аксиомы пополнения следует, что выполняются FD AС → BС иBC → BD;из аксиомы транзитивности (3) следует, что выполняется FD AC →BDЕсли выполняются FD A → BC и B → D, то выполняется и FDA → BCD (аксиома накопления)из аксиомы пополнения следует, что выполняется FD BС → BCD;из аксиомы транзитивности следует, что выполняется FD A →BCD22.10.2009С.Д.
Кузнецов. Базы данных.25 Проектирование РБДЭлементы теории функциональных зависимостей (15)Базовые определения и утверждения (14)Определение 5.5. Замыкание множестваатрибутовПусть заданы переменная отношения r,множество Z атрибутов этого отношения(подмножество Hr, или составной атрибут r) инекоторое множество FD S, выполняемых дляr.Тогда замыканием Z над S называетсянаибольшее множество Z+ таких атрибутов Yотношения r, что FD Z → Y ∉ S+22.10.2009С.Д.
Кузнецов. Базы данных.26 Проектирование РБДЭлементы теории функциональных зависимостей (16)Базовые определения и утверждения (15)Докажем корректностьалгоритма по индукцииНа нулевом шагеZ[0] = Z, и FD Z → Z[k],очевидно, принадлежитS+ (тривиальная FD«выводится» из любогомножества FD)Пусть для некоторого kвыполняется FD Z → Z[k], и пусть мы нашли в S такую FD A → B, что A⊆ Z[k].Тогда можно представить Z[k] в виде AC, и, следовательно,выполняется FD Z → AC.Но по аксиоме накопления (8) тогда выполняется FD Z → ACB, т.е.
FDZ → (Z[k] UNION B) входит во множество S+, что переводит нас наследующий шаг индукции.Очевидно, что, поскольку множество атрибутов отношения конечно, тона некотором шаге алгоритм завершит свою работу22.10.2009С.Д. Кузнецов. Базы данных.27 Проектирование РБДЭлементы теории функциональных зависимостей (17)Базовые определения и утверждения (16)Продемонстрируем работуалгоритма на примере.Пусть имеется отношениес заголовком{A, B, C, D, E, F} и заданныммножеством FDS = {A → D, AB → E, BF → E,CD → F, E → C}.Пусть требуется найти {AE}+над S.На первом проходе тела циклаDO Z[1] равно AE.В теле цикла FOR EACH будут найдены FD A → D и E → C, и в конце цикла Z[1] станетравным ACDE.На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будетнайдена FD CD → F, и в конце цикла Z[2] станет равным ACDEF.Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.Алгоритм построения замыкания множества атрибутов Z над заданныммножеством FD S помогает легко установить, входит ли заданная FD Z → B взамыкание S+.Очевидно, что необходимым и достаточным условием для этого является B ⊆ Z+,т.
е. вхождение составного атрибута B в замыкание Z22.10.2009С.Д. Кузнецов. Базы данных.28 Проектирование РБДЭлементы теории функциональных зависимостей (18)Базовые определения и утверждения (17)Определение 5.6. Суперключ отношенияСуперключом переменной отношения r называетсялюбое подмножество K заголовка Hr, включающее, поменьшей мере, хотя бы один возможный ключ rОдно из следствий этого определения состоит в том, чтоподмножество K заголовка Hr является суперключомтогда и только тогда, когда для любого атрибута A(возможно, составного) из заголовка отношения rвыполняется FD K → A.В терминах замыкания множества атрибутов K являетсясуперключом тогда и только тогда, когда K+ совпадает сHr22.10.2009С.Д.
Кузнецов. Базы данных.29 Проектирование РБДЭлементы теории функциональных зависимостей (19)Базовые определения и утверждения (18)Определение 5.7. Покрытие множества FDМножество FD S2 называется покрытиеммножества FD S1, если любая FD, выводимаяиз S1, выводится также и из S2Легко заметить, что S2 является покрытием S1тогда и только тогда, когда S1+ ⊆ S2+Два множества FD S1 и S2 называютсяэквивалентными, если каждое из них являетсяпокрытием другого, т. е.
S1+ = S2+22.10.2009С.Д. Кузнецов. Базы данных.30 Проектирование РБДЭлементы теории функциональных зависимостей (20)Базовые определения и утверждения (21)Определение 5.8. Минимальное множество FDМножество FD S называется минимальным в том и тольков том случае, когда удовлетворяет следующим свойствам:правая часть любой FD из S является множеством изодного атрибута (простым атрибутом);детерминант каждой FD из S обладает свойствомминимальности, т.е.удаление любого атрибута из детерминанта приводит кизменению замыкания S+, т. е. порождению множества FD, неэквивалентного SFD с минимальным детерминантом называется минимальнойслева;удаление любой FD из S приводит к изменению S+, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
