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

Пусть R — отношение со схемой 7Z_} и Х_у У — подмножества 7Z. Отношение R удовлетворяет функциональной зависимости (F-зависимости) X —? Y, если пу ( имеет не более чем один кортеж для каждого^{-значения} х. Иными словами, фиксация значений столбцов из X однозначно определяет значение столбцов из У. В F-зависимости X —> У подмножество X называется левой частью, а У — правой частью.

Если отношение R со схемой 71 удовлетворяет функциональной зависимости X —> 71, то множество X называется суперключом. То есть суперключ однозначно определяет кортеж. Понятие суперключа в точности соответствует понятию теста таблицы. Напомним, что тестом таблицы называется такое множество столбцов, что проекция таблицы на эти столбцы не имеет одинаковых строк. Суперключ отношения называется ключом, если любое его подмножество не является суперключом. Понятие ключа полностью соответствует понятию тупикового теста таблицы.

Если 71 — некоторая схема отношений, то через М (71) обозначим множество всех отношений над схемой 71. Если М С М{71), то скажем что множество М удовлетворяет функциональной зависимости X —? У, если каждое отношение из А/ удовлетворяет X —> У.

Часто поступают наоборот и описывают множество М допустимых отношений описывается с помощью множества Fзависимостей, которым должно удовлетворять каждое отношение. Это множество F-зависимостей фактически описывает наши семантические знания об отношении. Поэтому в дальнейшем мы будем считать, что вместе со схемой 71 задано множество Т F-зависимостей, которым должны удовлетворять все допустимые отношения.

Если известны некоторые F-зависимости из F, то часто можно вывести остальные. Множество F-зависимостей Т влечет F-зависимость X —> У (обозначение: F = X —* У), если каждое отношение, удовлетворяющее F-зависимостям из F, удовлетворяет также F-зависимости X —> У. В этом случае также говорят, что X —* Y является логическим следствием Т, или что X —" У следует из Т.

Аксиома вывода — это правило, устанавливающее, что если отношение удовлетворяет определенным F-зависимостям, то оно должно удовлетворять и некоторым другим F-зависимостям.

Теперь введем шесть аксиом вывода для^{-зависимостей.} В их формулировках используется обозначение R для отношения со схемой 1Z и IV, X, У и Z — для подмножеств R.

F1. Рефлексивность. Отношение irx (&x=x{R)) всегда имеет не более одного кортежа, следовательно, X —> X всегда имеет место в R.

F2. Пополнение. Это аксиома имеет дело с расширением левой части F-зависимости. Если R удовлетворяет X —> Y, то ny (crx=_x®) имеет не более одного кортежа для любого Х-значения х. Если Z является любым подмножеством 7?, то 0Xuz=xz® Я (?x=x® и, следовательно, TTy (axuZ=xz®) Я пу (оХ = x®). Таким образом пу (аxuZ=xz®) имеет самое большее один кортеж, и R должно удовлетворять F-зависимости Xu Z —> Y.

F3. Аддитивность. Эта позволяет объединить две F-зависимости с одинаковыми левыми частями. Если отношение R удовлетворяет X —> Y и X —* Z, то обе проекции ъу ((Тх=х (Щ) и nz ( имеют не более одного кортежа для любогозначения х. Если бы отношение тсуиг{0Х=ж{Щ) имело более одного кортежа, то по крайней мере одно из отношений я^шу{&х=х (Щ) ИЛИ 7Tz (o‘x=x®) имело бы более одного кортежа. Таким образом, R удовлетворяет F-зависимости X —* Y U Z.

F4. Проективность. Эта аксиома в некоторой степени обратна аксиоме аддитивности. Если R удовлетворяет X YuZ, то TTyuz (^x=x®) имеет не более одного кортежа для любого Х-значения х. Так как яу (*Уиг{рх=х{Щ)) — 7ry (aY=_x(F)), то 7Ty ((rx=x®) также может иметь не более одного кортежа. Следовательно, R удовлетворяет X —" Y.

F5. Транзитивность. Эта и следующая аксиома являются наиболее мощными из аксиом вывода. Пусть отношение R удовлетворяет F-зависимостям X —* Y и Y —> Z. Рассмотрим кортежи Г] и г₂ в R. Если г (Х) = г₂(Х), то ri (T) = г₂(У), а из r (Y) = г₂(У), следует, что ri (Z) = r₂(Z). Таким образом, если ri (A') = г₂(Х), то ri (Z) = r₂(Z), т. е. R удовлетворяет X —? Z.

F6. Псевдотранзитивность. Пусть отношение R удовлетворяет F-зависимостям X —* Y и Y U Z —* W, а г и г₂ являются кортежами в R. По условию если ri (X) = г₂(Х), то ri (F) = г₂(Т), и, аналогично, если T{Y U Z) = r₂(T U Z),

Итак, если Х_у У, Z, W являются подмножествами 71_у то для любого отношения R справедливы следующие аксиомы вывода:

Используя аксиомы F1-F6, можно получить другие правила вывода для^{-зависимостей.} Более того аксиомы F1-F6 не являются независимыми, т. е. одни из них могут быть получены из других. Так если даны аксиомы FI, F2 и F6, то из них можно вывести остальные. Если даны X —> У и X —> Z, то используем F1, чтобы получить Y U Z —> У U Z, и дважды применяем F6, получая сначала XuZ —? YnZ, а затем X —> YuZ. Поэтому F3 следует из FI, F2 и F6. Чтобы доказать F4, предположим, что X —> Y U Z. Из F1 имеем У —* У, а из F2 получаем У U Z —> У. Применение F6 дает X —* У. F5 является частым случаем F6 при Z = 0. В качестве самостоятельного упражнения можно показать, что аксиомы FI, F2 и F6 являются независимыми, т. е. ни одна из них не может быть выведена из двух других.