Замыкание множества функциональных зависимостей. Аксиомы Армстронга. Замыкание множества атрибутов
Определение 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) следует, что AС ® BС и BC ® BD; из правила (3) следует, что AC ® BD;
(8) если A ® BC и B ® D, то A ® BCD (накопление) – из правила (2) следует, что BС ® 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.