что противоречит наличию тривиальной FD

Тогда из неравенства (b) следует, что t1 {C} t2 {C}, что противоречит наличию тривиальной FD ACC. Следовательно, предположение об отсутствии FD ACBC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD AC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} t2 {C}. Но из наличия FD AB следует, что t1 {B} = t2 {B}, а потому из наличия FD BC следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD AC не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

1. A
   
   A (самодетерминированность) – прямо следует из правила (1);
2. если A
   
   BC, то A
   
   B и A
   
   C (декомпозиция) – из правила (1) следует, что BC
   
   B; по правилу (3) A
   
   B; аналогично, из BC
   
   С и правила (3) следует A
   
   C;
3. если A
   
   B и A
   
   C, то A
   
   BC (объединение) – из правила (2) следует, что A
   
   AB и AB
   
   BC; из правила (3) следует, что A
   
   BC;
4. если A
   
   B и C
   
   D, то AC
   
   BD (композиция) – из правила (2) следует, что AС
   
   BС и BC
   
   BD; из правила (3) следует, что AC
   
   BD;
5. если A
   
   BC и B
   
   D, то A
   
   BCD (накопление) – из правила (2) следует, что BС
   
   BCD; из правила (3) следует, что A
   
   BCD.

Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Z+ таких атрибутов Y отношения R, что FD ZY входит в S+.

Алгоритм вычисления Z+ очень прост. Один из его вариантов показан на .



Рис. 7.2.  Алгоритм построения замыкания атрибутов над заданным множеством FD


Содержание  Назад  Вперед

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---