Введение в реляционные базы данных

              

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


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

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что 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 не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (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 Z
Y входит в S+.

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



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




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