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

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

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

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

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

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

1. если BA, тоAB(рефлексивность);

2. если AB, тоACBC(пополнение);

3. если ABиBC, тоAC(транзитивность).

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

Справедливость второй аксиомы докажем от противного. Предположим, что FD ACBCне соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежаt₁иt₂, такие, чтоt₁ {AC} = t₂ {AC}(a), ноt₁ {BC} t₂ {BC}(b) (здесьt {A}обозначает проекцию кортежаtна множество атрибутовA). По аксиоме рефлексивности из равенства (a) следует, чтоt₁ {A} = t₂ {A}. Поскольку имеется FDAB, должно соблюдаться равенствоt₁ {B} = t₂ {B}. Тогда из неравенства (b) следует, чтоt₁ {C} t₂ {C}, что противоречит наличию тривиальной FDACC. Следовательно, предположение об отсутствии FDACBCне является верным, и справедливость второй аксиомы доказана.

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

28 К сожалению, классическая статья Армстронга – W.W. Armstrong. "Dependency Structures of Data Base Relationships", Proc. IFIP Congress, Stockholm, Sweden, 1974 – так и не переведена на русский язык (на самом деле, ее нелегко найти и в оригинале). Поэтому я не могу рекомендовать ее для дополнительного чтения, хотя обязан сослаться.

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

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

5. если ABC, тоABиAC(декомпозиция) – из правила (1) следует, чтоBCB; по правилу (3)AB; аналогично, изBCСи правила (3) следуетAC;

6. если ABиAC, тоABC(объединение) – из правила (2) следует, чтоAABиABBC; из правила (3) следует, чтоABC;

7. если ABиCD, тоACBD(композиция) – из правила (2) следует, чтоAСBСиBCBD; из правила (3) следует, чтоACBD;

8. если ABCиBD, тоABCD(накопление) – из правила (2) следует, чтоBСBCD; из правила (3) следует, чтоABCD.

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

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

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

Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FDZZ[I], очевидно, принадлежитS⁺(тривиальная FD «выводится» из любого множества FD). Пусть для некоторогоKвыполняется FDZZ[K], и пусть мы нашли вSтакую FDAB, чтоAZ[K]. Тогда можно представитьZ[K]в видеAC, и, следовательно, выполняется FDZAC. Но по правилу (8) мы имеем FDZACB, т.е. FDZ(Z[K] UNION B)входит во множествоS⁺, что переводит нас на следующий шаг индукции.

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F}и заданным множеством FDS = {AD, ABE, BFE, CDF, EC}. Пусть требуется найти{AE}⁺надS. На первом проходе тела цикла DOZ[1]равноAE. В теле циклаFOR EACHбудут найдены FDADиEC, и в конце циклаZ[1]станет равнымACDE. На втором проходе тела цикла DO приZ[2], равномACDE, в теле циклаFOR EACHбудет найдена FDCDF, и в конце циклаZ[2]станет равнымACDEF. Следующий проход тела цикла DO не изменитZ[3], иZ⁺({AE}⁺) будет равноACDEF.

Алгоритм построения замыкания множества атрибутовZнад заданным множеством FDSпомогает легко установить, входит ли заданная FDZBв замыканиеS⁺. Очевидно, что необходимым и достаточным условием для этого являетсяBZ⁺, т. е. вхождение составного атрибутаBв замыканиеZ²⁹⁾.

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

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