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

              

Замыкание множества функциональных зависимостей. Аксиомы Армстронга. Замыкание множества атрибутов


Замыканием множества FD S является множество FD S+, включающее все FD, логически выводимые из FD множества S.

Для начала приведем два примера FD, из которых следуют (или выводятся) другие FD. Будем снова пользоваться отношением СЛУЖАЩИЕ_ПРОЕКТЫ. Для этого отношения выполняется, например, FD СЛУ_НОМ

{СЛУ_ЗАРП, ПРО_НОМ}. Из этой FD выводятся FD СЛУ_НОМ
СЛУ_ЗАРП и СЛУ_НОМ
ПРО_НОМ.

В отношении СЛУЖАЩИЕ_ПРОЕКТЫ имеется также пара FD СЛУ_НОМ

ПРО_НОМ и ПРО_НОМ
ПРОЕКТ_РУК. Из них выводится FD СЛУ_НОМ
ПРОЕКТ_РУК. Заметим, что FD вида СЛУ_НОМ
ПРОЕКТ_РУК называются транзитивными, поскольку ПРОЕКТ_РУК зависит от СЛУ_НОМ "транзитивно", через ПРО_НОМ.

FD A

C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A
B и B
C и отсутствует функциональная зависимость C
A.

Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг1). Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения r. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:

  1. если B
    A, то A
    B (рефлексивность);
  2. если A
    B, то AC
    BC (пополнение);
  3. если A
    B и B
    C, то A
    C (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при B

A FD A
B является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD AC

BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа 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}.

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




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