Функциональные зависимости и их свойства

Для объединения множеств атрибутов употребляются следующие обозначения:

если наименование атрибута имеет смысл, то вместо знака объединения ставится один пробел;

если атрибут обозначается произвольной латинской буквой, то знак объединения не ставится; запись XY эквивалентна X Y.

Множество атрибутов Y функционально зависит от множества атрибутов X, где X, Y {A₁,А₂,...,A_n}, если значения атрибутов в X единственным образом определяют значения атрибутов Y. В этом случае говорят, что между множествами атрибутов X и Y существует функциональная зависимость (F-зависимость), или X определяет Y; обозначают F : X Y или просто X Y.

Пример 3.1. Рассмотрим отношение ПОСТАВКИ (ПОСТАВЩИК, ГОРОД, ТОВАР, КОЛИЧЕСТВО). На значения атрибутов этого отношения накладываются следующие ограничения:

1) Осуществлять поставку данного товара в данном количестве из определенного города может только один поставщик;

2) Некоторый поставщик из данного города и в данном количестве может осуществлять поставку только одного товара;

Перечисленные ограничения являются F-зависимостями и их можно записать так:

1) ТОВАР ГОРОД КОЛИЧЕСТВО ПОСТАВЩИК

2) ГОРОД ПОСТАВЩИК КОЛИЧЕСТВО ТОВАР

Пусть R(A₁,А₂,...,A_n) — схема отношения, X и Y — подмножества атрибутов. Будем говорить, что отношение R удовлетворяет F-зависимости X Y, если для любых кортежей t₁,t₂ R из t₁(X)=t₂(X) следует t₁(Y)= t₂(Y). В F-зависимости X Y подмножество X называется левой, а Y — правой частью.

Такая интерпретация F-зависимости является основой алгоритма ЗАВИСИМОСТЬ.

Вход. Отношение R и F-зависимость X Y.

Выход. Истина, если R удовлетворяет X Y, в противном случае — ложь.

Шаг 1. Сортировать отношение R по Х-столбцам так, чтобы собрать кортежи с равными X-значениями.

Шаг 2. Если каждая совокупность кортежей с равными X-значениями имеет также равные Y-значения, то на выходе получаем истину, в противном случае — ложь.

F-зависимостыо X Y на множестве атрибутов А можно считать упорядоченную пару (X,Y), где X,Y A. Тогда множеством всех функциональных зависимостей над А будет L={(X, Y)| X A, Y A}.

Если Y не зависит от X, то записывают X Y. Если X Y и Y X, то X и Y называют эквивалентными или говорят, что между X и Y существует биекция, т. е. X Y.

Пример 3.2. Пусть поставщик осуществляет поставки ТОВАРА, определенное КОЛИЧЕСТВО. Он находится в ГОРОДЕ и определенной СТРАНЕ. Можно сформировать следующие зависимости:

f1: ТОВАР КОЛИЧЕСТВО,

f2: ТОВАР ПОСТАВЩИК,

f3: ПОСТАВЩИК ГОРОД,

f4: ГОРОД СТРАНА,

f5: ТОВАР СТРАНА.

Аксиомы вывода

Для различных состояний отношения R(A) могут существовать разные совокупности F-зависимостей. Интерес представляет выявление множества F-зависимостей F, которым удовлетворяют все допустимые состояния R(A). Для этого нужно знать семантические связи между атрибутами отношения. Такое множество F-зависимостей можно считать заданным в схеме отношения R(A). В подобном случае любое отношение со схемой R(A) должно удовлетворять всем F-зависимостям из F. Данное множество F конечно, так как существует только конечное число подмножеств множества А. Одним из способов его нахождения является использование алгоритма ЗАВИСИМОСТЬ, что требует много времени. Другим способом являются аксиомы вывода — правила, позволяющие на основании данного множества F-зависимостей получить все F-зависимости, которым удовлетворяет отношение R(A). Рассмотрим эти аксиомы.

Пусть X, Y, Z, W — непустые подмножества множества A={A₁,А₂,...,A_n}. Тогда для любого отношения со схемой R(A) справедливы следующие аксиомы вывода.

F1. Рефлексивность: Х Х.

F2. Транзитивность: если X Y и Y Z, то X Z.

F3. Пополнение: если X Y, то XZ Y.

F4. Псевдотранзитивность: если X Y и YZ W, то XZ W.

F5. Аддитивность: если X Y и X Z, то X YZ.

F6. Проективность: если X FZ, то X Y или Х Z.

Рассмотрим сформулированные аксиомы на примере отношения R, включающего атрибуты: X — ТОВАР, У — ПОСТАВЩИК, Z — ГОРОД, W — СТРАНА.

F1. Рефлексивность. Отношение π_X( _X=x(R)) всегда имеет не более одного кортежа. Следовательно, Х Х всегда истинно в R. Например, ТОВАР ТОВАР.

F2. Транзитивность. Пусть t₁ и t₂ — кортежи в R. Если t₁(X) = t₂(X), то t₁(Y) = t₂(Y), а из t₁(Y) = t₂(Y) вытекает t₁(Z) = t₂(Z). Таким образом, если

t₁(X) = t₂(X), то t₁(Z) = t₂(Z), т. е. R удовлетворяет X Z. Например, если ТОВАР ПОСТАВЩИК и ПОСТАВЩИК ГОРОД, то ТОВАР ГОРОД.

F3. Пополнение. Эта аксиома позволяет расширить левую часть F-зависимости. Если R удовлетворяет X Y, то π_Y( _X=x(R)) имеет не более одного кортежа для любого х Х. Если L R, то _XZ=xz(R) _X=x(R) и, следовательно, π_Y( _XZ=xz(R)) π_Y( _X=x(R)). Таким образом, π_Y( _XZ=xz(R)) имеет максимум один кортеж и R должно удовлетворять F-зависимости XZ Y. Например, если ТОВАР ПОСТАВЩИК, то ТОВАР ГОРОД ПОСТАВЩИК.

F4. Псевдотранзитивность. Пусть t₁ и t₂ — кортежи в R. По условию если t₁(X) = t₂(X), то t₁(Y) = t₂(Y), и аналогично, если t₁(YZ) = t₂(YZ), то t₁(W) = t₂(W). Из t₁(XZ) = t₂(XZ) получаем, что t₁(X) = t₂(X). Значит, t₁(Y) = t₂(Y) и, кроме того, t₁(YZ) = t₂(YZ), откуда следует, что t₁(W) = t₂(W). Таким образом, R удовлетворяет XZ W. Например, если ТОВАР ПОСТАВЩИК и ПОСТАВЩИК ГОРОД СТРАНА, то ТОВАР ГОРОД СТРАНА.

F5. Аддитивность. Эта аксиома позволяет объединить две F-зависимости с одинаковыми левыми частями. Из X Y и X Z следует, что π_Y( _X=x(R)) и π_Z( _X=x(R)) имеют не более одного кортежа для любого х Х. Если бы отношение π_YZ( _X=x(R)) имело более одного кортежа, то по крайней мере одно из отношений π_Y( _X=x(R)) или π_Z( _X=x(R)) имело бы более одного кортежа. Таким образом, R удовлетворяет F-зависимости X YZ. Например, если ТОВАР ПОСТАВЩИК и ТОВАР ГОРОД, то ТОВАР ПОСТАВЩИК ГОРОД.

F6. Проективность. Эта аксиома в некоторой степени обратна аксиоме аддитивности. Если R удовлетворяет Х YZ, то π_YZ( _X=x(R)) имеет не более одного кортежа для любого х Х. Так как π_Y(π_YZ( _X=x(R))) = π_Y( _X=x(R)), то π_Y( _X=x(R)) также может иметь не более одного кортежа. Следовательно, R удовлетворяет Х У. Например, если ТОВАР ПОСТАВЩИК ГОРОД, то ТОВАР ПОСТАВЩИК или ТОВАР ГОРОД.

Некоторые аксиомы вывода могут быть получены из других аксиом. Например, транзитивность F2 является частным случаем псевдотранзитивности F4 при Z = . Аксиома F4 выводится из F1...F3 и F5; если X Y и YZ W, то, как следствие, F1, Z Z. Согласно F3 имеем XZ Y и XZ Z. Используя F5, получаем XZ YZ. Наконец, применяя F2, имеем XZ W.

С помощью аксиом F1, F3 и F4 можно вывести аксиомы F2, F5 и F6. Как было сказано, F2 является частным случаем F4. Если X Y и X Z, то из F1 получаем YZ YZ и, дважды применяя F4, сначала получаем XZ YZ, а затем X YZ. Поэтому F5 следует из F1, F3 и F4. Для доказательства F6 предположим, что X YZ. Из F1 имеем Y Y, а из F3 получаем YZ Y. Применение F4 дает X Y.

Таким образом, аксиомы F1, F3 и F4 составляют полное подмножество для F1...F6 и являются независимыми в том смысле, что ни одна из аксиом не может быть получена из двух других. Аксиомы F1, F3 и F4 иногда называют аксиомами Армстронга.

Система аксиом F1...F6 является полной, т.е. путем одно- или многократного применения к F этих аксиом можно получить любую F-зависимость, которая следует из множества F.

Множество функциональных зависимостей F={f₁,f₂,...,f_m}, находится в приведенной канонической форме, если F-зависимости не имеют одинаковых левых частей. Для таких функциональных зависимостей если X_i Y_i и X_i Y_j, то X_i Y_i Y_j. Например, приведенной канонической формой для F={f₁,f₂, f₃} из примера 3.2 будет:

ТОВАР КОЛИЧЕСТВО ПОСТАВЩИК СТРАНА.

Замыкания

Пусть F= {X_i Y_i}, 1≤ i ≤n, — множество функциональных зависимостей. Замыканием множества F называют множество F⁺, содержащее все те зависимости, которые могут быть получены применением к F аксиом Армстронга. Замыкание множества функциональных зависимостей используется для определения биекций и ликвидации избыточности множества функциональных зависимостей.

Пример 3.3. Пусть F = {АВ С, С В} — множество F-зависимостей на R(A, В, С). Тогда F⁺ = {А А, AB А, АС A, АВС А, В В, АВ B, ВС В, ABC В, С С, АС С, ВС С, ABC С, АВ АВ, ABC АВ, АС AC, ABC АС, ВС ВС, ABC ВС, ABC ABC, АВ С, АВ АС, АВ ВС, AВ ABC, С В, С ВС, АС В, АС АВ}.

Вычисление F⁺ для множества зависимостей F является весьма трудоемкой задачей, так как множество зависимостей F⁺ может быть большим, даже если само F мало. Рассмотрим множество F = {A B₁, A B₂,..., A B_n}. Тогда F⁺ включает все зависимости A Y, где Y — подмножество множества {B₁,B₂,...,B_n}. Так как существует 2ⁿ таких подмножеств Y, то даже при небольших n их нелегко перечислить.

Более простым является вычисление замыкания атрибутов множества А относительно множества функциональных зависимостей F. Пусть F — множество функциональных зависимостей на множестве атрибутов U, а X — некоторое подмножество U. Тогда Х⁺ — замыкание X относительно F — есть множество атрибутов А таких, что зависимость Х A может быть выведена из F по аксиомам Армстронга. Замыкание X⁺ позволяет сразу определить, выводится ли зависимость X Y из F по аксиомам Армстронга. Существует следующая лемма.

Утверждение. Функциональная зависимость X Y выводится из аксиом Армстронга тогда и только тогда, когда Y Х⁺.

Рассмотрим алгоритм вычисления замыкания множества атрибутов U относительно множества функциональных зависимостей F.

Вход. Конечные множества: атрибутов U, зависимостей F и атрибутов X U.

Выход. Замыкание Х⁺ множества атрибутов X относительно F.

Вычисляем последовательность множеств атрибутов Х⁽⁰⁾, Х⁽¹⁾,... по следующим правилам.

Шаг 1. Х⁽⁰⁾ есть X.

Шаг 2. Хⁱ⁺¹ есть Xⁱ плюс множество атрибутов А таких, что в F существует некоторая зависимость Y Z, А принадлежит Z и Y X⁽ⁱ⁾ Поскольку Х = Х⁽⁰⁾ Х⁽¹⁾ ... U и U конечно, в итоге достигнем такого i, что X⁽ⁱ⁾ = X⁽ⁱ⁺¹⁾. Отсюда X⁽ⁱ⁾ = X⁽ⁱ⁺¹⁾ =X⁽ⁱ⁺²⁾ =... и поэтому процесс вычисления Х⁺ прекращается, если X⁽ⁱ⁾ = X⁽ⁱ⁺¹⁾.

Пример 3.4. Пусть F состоит из следующих зависимостей:

АВ С, AE G,

ВС D, D EC,

В АЕ, EG K,

а Х=АВ. Используя алгоритм, получаем Х⁽⁰⁾=Х=АВ. Для вычисления Х⁽¹⁾ находим зависимости, которые имеют в левой части А, В или АВ. Во множестве F существуют две зависимости: АВ С и В АЕ. Поэтому присоединяем С и E к Х⁽⁰⁾ получаем Х⁽¹⁾ =АВСЕ. Затем вычисляем Х⁽²⁾ путем поиска левых частей зависимостей F, содержащихся в Х⁽¹⁾. Находим BC D и AE G. Таким образом, Х⁽²⁾=ABCDEG. Далее находим EG K, D G и, наконец, Х⁽³⁾=ABCDEGK — множество всех атрибутов. Следовательно, Х⁽³⁾= Х⁽⁴⁾= ... . Итак, получаем (AB)⁺=ABCDEGK.

Пусть задано отношение R на множестве атрибутов {A₁,А₂,...,A_n}, Множество атрибутов К называется ключом отношения R (первичным ключом), если каждый атрибут A_i {A₁,А₂,...,A_n},, который не входит в К, функционально зависит от К, т. е. К A_i; и никакое подмножество К не удовлетворяет этому свойству. В дальнейшем ключевые атрибуты в схемах отношений будут подчеркиваться.

Пример 3.5. В функциональной зависимости ТОВАР ДАТА КОЛИЧЕСТВО ГОРОД ПОСТАВЩИК ключом является (ТОВАР ДАТА КОЛИЧЕСТВО).

Два множества F-зависимостей F и G над схемой отношения R эквивалентны, F ≡G, если F⁺ = G⁺. Если F ≡G, то F есть покрытие для G.

Пример 3.6. Множества F={A BC, A D, CD E} и G={А ВСЕ, A ABD, CD E} эквивалентны. Множество F не эквивалентно множеству G'={A BCDE}, поскольку зависимость CD E не выводится в G'.

Множество F-зависимостей F неизбыточно, если у него нет такого собственного подмножества F' что F'≡F. Если такое подмножество F' существует, то F избыточно.

Пример 3.7. Множество F={АВ С, А ВС, А В, В С} избыточно, так как есть подмножество F'={A B, B C}, которое эквивалентно F.

Пусть имеется множество функциональных зависимостей F={X_i Y_i}, i = . Множество атрибутов Z_i X_i называют посторонним в X_i, если X_i Z_i Y_i может быть получено в замыкании F⁺.

Пример 3.8. В примере 3.2 комбинация атрибутов ТОВАР и ПОСТАВЩИК определяет атрибут ГОРОД, т. е. f₃ может заменить зависимость

ТОВАР ПОСТАВЩИК ГОРОД.

Из f₂ видно, что атрибут ПОСТАВЩИК с левой стороны является посторонним.

Множество F-зависимостей F называют минимальным, если оно содержит не больше F-зависимостей, чем любое эквивалентное множество F-зависимостей.

Минимальное множество F-зависимостей не может содержать избыточных зависимостей. Таким образом, оно одновременно и неизбыточно.

Пример 3.9. Множество G={A BC, B A, AD E, BD L} неизбыточно, но не минимально, поскольку существует множество F={A BC, B A, AD EL}, которое эквивалентно G и содержит меньшее число F-зависимостей. Множество F является минимальным покрытием G.

При проектировании схем БД для минимального покрытия множества F-зависимостей полезно использовать следующие ограничения:

1) правая часть каждой F-зависимости содержит единственный атрибут;

2) ни для какой F-зависимости Х А в F множество F—(Х А) не эквивалентно F;

3) ни для какой F-зависимости Х А в F и собственного подмножества Z X множества F—(X A) (Z A) и F не эквивалентны.

Пример 3.10. Пусть F состоит из таких F-зависимостей:

AB C, ACD B, CG BD,

C A, D EG, CE AG,

BC D, BE C,

Используя условие 1), получаем

АВ C, D Е, CG B,

С A, D G, CG D,

ВС D, BE C, СЕ A,

ACD В, СЕ G.

Здесь F-зависимость СЕ А избыточна, поскольку она следует из зависимости С А. Подобным образом избыточна F-зависимость CG B, так как из CG D, С А и ACD B получаем CG B. Никакие другие F-зависимости не являются избыточными. Однако ACD B может быть замещена зависимостью CD B, поскольку С А. Таким образом, минимальное покрытие включает следующие F-зависимости:

AB C, CD B, BE C,

C A, D E, CG D,

BC D, D G, CE G.

Другое минимальное покрытие, построенное из F исключением СЕ А, CG D и АСD B, имеет вид

AB C, D E, CG B,

C A, D G, CE G.

B CD, BE C,

Отметим, что эти два минимальных покрытия имеют разное число зависимостей.

Более короткое представление множества F является предпочтительным: во-первых, потому, что от мощности F зависит временная сложность алгоритмов для обработки этого множества; во-вторых, объем используемой памяти и число операций при модификации БД также определяются числом F-зависимостей.