Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





 

Определение 6.3. Замыкание множества FD

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

 

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

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

Определение 6.4. Транзитивная функциональная зависимость

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

 

Подход к решению проблемы нахождения замыкания S+ множества FD S впервые предложил Вильям Армстронг*. Им был предложен набор правил вывода новых 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}. Тогда из неравенства (b) следует, что t1 {C} ¹ t2 {C}, что противоречит тривальной FD AC ® C. Следовательно, предположение об отсутствии FD AC ® BC не является верным, и справедливость второй аксиомы доказана.



 

Аналогично докажем истинность третьей аксиомы Армстронга. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие что t1 {A} = t2 {A} (a), но t1 {C} ¹ t2 {C} (b). Но из наличия 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. Тем не менее, Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

 

(4) A ® A (самодетерминированность) – прямо следует из правила (1);

(5) если A ® BC, то A ® B и A ®C (декомпозиция) – из правила (1) следует, что BC ® B; по правилу (3) A ® B; аналогично, из BC ® С и правила (3) следует A ®C;

(6) если A ® B и A ®C, то A ® BC (объединение) – из правила (2) следует, что A ® AB и AB ®BC; из правила (3) следует, что A ® BC;

(7) если A ® B и C ® D, то AC ® BD (композиция) – из правила (2) следует, что ® и BC ® BD; из правила (3) следует, что AC ® BD;

(8) если A ® BC и B ® D, то A ® BCD (накопление) – из правила (2) следует, что ® BCD; из правила (3) следует, что A ® BCD.

 

Определение 6.5. Замыкание множества атрибутов

 

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

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

 

K := 0; Z[0] := Z;

DO

K := K+1;

Z[K] := Z[K-1];

FOR EACH FD A ® B IN S DO

IF A Í Z[K] THEN Z[K] := (Z[K] UNION B) END DO;

UNTIL Z[K] = Z[K-1];

Z+ := Z[K];

 

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

 

Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD Z ® Z[I], очевидно, принадлежит 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, т.е. FD Z ® (Z[K] UNION B) входит во множество S+, что переводит нас на следующий шаг индукции.

 

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {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 в замыкание Z.*



Определение 6.6. Суперключ отношения

Суперключом отношения r называется любое подмножество K заголовка r, включающее, по меньшей мере, хотя бы один возможный ключ r. Конец определения.

 

Одним из следствий этого определения является то, что подмножество K заголовка отношения r является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения r выполняется FD K ® A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K+ совпадает с заголовком r.

 

Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2014-01-03; Просмотров: 724; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.025 сек.