2.3. Свойства функциональных зависимостей

Правила вывода функциональных зависимостей
F1. Аксиома рефлексивности
F2. Аксиома пополнения
F3. Аксиома аддитивности
F4. Аксиома проективности
F5. Аксиома транзитивности
F6. Аксиома псевдотранзитивности

При анализе семантики предметной области разработчик базы обычно выделяет только часть функциональных зависимостей, которые в дальнейшем будем обозначать символом F.

Однако F может не охватывать полное множество зависимостей для отношения Ri со схемой R.
Полное множество функциональных зависимостей, обозначаемое через F+, можно вычислить по нижеследующему алгоритму.

Пусть Ri состояние отношения R со схемой R, для которого задано множество зависимоcтей F = {X Y}, где X AR и Y AR

Шаг 1. Сортировка Ri.

Отсортируем отношение Ri по X столбцам так, чтобы собрать кортежи с равными значениями x вместе.

Шаг 2. Проверка выполнения зависимости.

Если каждая совокупность кортежей с равными х значениями, имеет равные у значения, то зависимость X Y выполняется, в противном случае функциональная зависимость между атрибутами X и Y отсутствует.

Шаг 3. Повторение шага 1 на булеане B(AR) (множестве всех подмножеств).

Пример. Пусть дано отношение

R (A, B, C)
    a1 b1 c1
    a2 b2 c2
    a3 b1 c1 ,

на котором определено множество функциональных зависимостей F ={ A B, A C }.

На шаге 1(1) выполняется сортировка R по столбцу B, результатом чего будет отношение

R (B, A, C)
    b1 a1 c1
    b1 a3 c1
    b2 a2 c2 .

На шаге 2(1) устанавливается наличие функциональных зависимостей В С и ВА С.

Шаги 1 и 2 повторяются для атрибута C.

На шаге 1(2) выполняется сортировка R по столбцу С, результатом чего будет отношение

R (C, A, B)
    c1 a1 b1
    c1 a3 b1
    c2 a2 b2 .

На шаге 2(2) устанавливается наличие функциональных зависимостей C B и CА B.

Объединяя исходные зависимости с зависимостями, выявленными на шагах 2(1) и 2(2), получим F+ ={A B, A C, B C, BA C, C B, CA B, ABC AB и остальные тривиальные зависимости}.

F+ также называют замыканием, т.к. оно логически следует из F.


ПРАВИЛА ВЫВОДА ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ

Количество функциональных зависимостей для отношения R конечно и их полное множество F+ можно определять по рассмотренному выше алгоритму, но такой подход требует значительных временных затрат. Чтобы избежать этого, к известному множеству F применяют специальные правила, называемые аксиомами вывода, которые утверждают, что если отношение удовлетворяет определенным ФЗ, то оно должно удовлетворять и другим функциональным зависимостям.

Пусть R - отношение со схемой R и Х AR, Y AR, W AR, Z AR - подмножества множества его атрибутов AR.

Тогда справедливы следующие аксиомы вывода:


F1. АКСИОМА РЕФЛЕКСИВНОСТИ

Любая функциональная зависимость рефлексивна по определению, т.е. Х X.

Следствие. Если Y X, то имеет место функциональная зависимость Х Y.

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

Пусть, например, имеется отношение R(A, B, C, D), на котором определено и некоторое множество функциональных зависимостей F.

Пусть, далее, Х={B, C, D}, а Y={B, D}, очевидно, что Y X. Если состояние Ri отношения R имеет вид

Ri(A, B, C, D) тогда R[B, C, D] R[B, D]
  a1 b1 c1 d1     b1 c1 d1     b1 d1
  a2 b1 c2 d2      b1 c2 d2     b1 d2
  a3 b2 c1 d1     b2 c1 d1     b2 d1
  a4 b1 c1 d1            

т.е. одной и той же совокупности значений атрибутов, входящих в Х, всегда соответствует одна и та же совокупность значений атрибутов, входящих в Y.

Тогда в F+ войдут исходное множество зависимостей F изаданные зависимости разработчиком и зависимости, сформированные в соответствии с аксиомой F1, т.е. F+ = F U {A A, ..., BCD BD, ...}.

Правило F1 дает так называемые тривиальные зависимости Х X, XY X и т.д., которые характеризуются тем, что атрибуты, входящие в правую часть ФЗ, полностью содержатся среди атрибутов левой ее части.


F2. АКСИОМА ПОПОЛНЕНИЯ

Функциональная зависимость XYZ Y принадлежит F+, если на отношении R выполняется X Y и Z AR, X AR, Y AR.

Данное правило показывает, что если в R существует Х Y, то к левой части функциональной зависимости можно прибавить любые атрибуты, принадлежащие AR, что определит зависимости, принадлежащие F+.

Пример. Пусть задано отношение R(A, B, C, D), на котором определено множество функциональных зависимостей F = {A B}, и пусть состояние Ri отношения R следующее:
Ri(A, B, C, D)
  a1 b1 c1 d1
  a1 b1 c1 d2
  a2 b2 c2 d2
  a3 b1 c3 d3.

Тогда, согласно аксиоме F2, отношение R будет удовлетворять и следующим зависимостям: {AB B, AC B, AD B, ABC B, ACD B, ABD B, ABCD B}.

В трактовке Армстронга [3], аксиома F2 формулируется следующим образом. Если Z AR, X AR, Y AR и задана зависимость Х Y, которая либо принадлежит F, либо получена из F с использованием правил вывода, то X U Z Y U Z (для краткости запись X U Z Y U Z будет в дальнейшем записываться в виде: XZ YZ).

Для аксиомы F2 не существенно, перекрываются множества X, Y, Z или нет. Согласно F2, любые атрибуты из множества AR можно подставить (но одновременно) и в правую и в левую части выражения функциональной зависимости, при этом функциональная зависимость сохраняется.


F3. АКСИОМА АДДИТИВНОСТИ

Согдасно этой аксиоме можно объединить две функциональных зависимости с одинаковыми левыми частями.

Если отношение R удовлетворяет функциональным зависимостям Х Y и Х Z и X AR, Y AR, Z AR, то оно удовлетворяет и функциональной зависимости X YZ (запись X Y U Z в дальнейшем подменяется записью X YZ).

Пример. Пусть задано отношение R(A, B, C, D), на котором определено множество функциональных зависимостей F = {A B, A C}, и пусть состояние Ri отношения R следующее:

Ri(A, B, C, D)
  a1 b1 c1 d1
  a1 b1 c1 d2
  a2 b2 c2 d2
  a3 b1 c3 d3

Тогда по аксиоме F3, отношение R должно удовлетворять и зависимости A BC.

Действительно проекции

SELECT DISTINCT A, B
FROM R;

и
SELECT DISTINCT A, С
FROM R;
имеют не более одного кортежа для любого значения аi атрибута А. Если бы эти проекции имели более одного кортежа, то нарушились бы условия А В и А С, следовательно R удовлетворяет А ВС.


F4. АКСИОМА ПРОЕКТИВНОСТИ

Эта аксиома обратна аксиоме аддитивности и позволяет разделить функциональную зависимость. Аксиома утверждает, что если для отношения R выполняется функциональная зависимость X YZ, то для него выполняется и функциональная зависимость X Y (и X Z).

Это утверждение непосредственно следует из того, что Y YZ (и Z YZ), учитывая, что YZ является сокращенной записью для Y U Z.

Рассмотрим конкретный пример. Пусть имеется отношение R, удовлетворяющее зависимости А ВС. Тогда, согласно F4, отношение Ri должно удовлетворять и зависимостям А В и А С.

Пример. Пусть имеется отношение R, удовлетворяющее зависимости А ВС. Тогда, согласно F4, отношение R должно удовлетворять зависимостям А В и А С.

Пусть состояние Ri отношения R имеет вид:

Ri(A, B, C, D)
  a1 b1 c1 d1
  a1 b1 c1 d2
  a2 b2 c1 d3
  a3 b1 c2 d1.

Тогда, если А ВС, то проекция:

SELECT DISTINCT A, B, C
FROM R;

даст результат:
r'(A, B, C)
  a1 b1 c1
  a2 b2 c1
  a3 b1 c2 ,
в котором имеется только по одному кортежу для каждого значения аi атрибута А.

Теперь, применив операцию проекции к r':

SELECT DISTINCT A, B
FROM r';

получим r'':
r"(A, B)
  a1 b1
  a2 b2
  a3 b1.

Однако такой же результат даст и следующее предложение:

SELECT DISTINCT A, B
FROM R;

Полученное отношение может иметь тоже не более одного кортежа, для каждого значения аi атрибута А, следовательно, по определению функциональной зависимости, имеет место А В.


F5. АКСИОМА ТРАНЗИТИВНОСТИ

Если X AR, Y AR, Z AR и для отношения R имеют место зависимости X Y, Y Z, то для него выполняется и зависисмость X Z.

Докажем справедливость данной аксиомы.

Пусть в отношении R имеется два кортежа t1 и t2. Тогда при наличии зависимости X Y если t1(х) = t2(х), то t1(у) = t2(у). Но, если t1(у) = t2(у), то при наличии Y Z обязательно t1(z) = t2(z), т.е., если t1(х) = t2(х), то t1(z) = t2(z), и, следовательно, для R выполняется и зависимость X Z.

Пример. Пусть задано отношение R(A, B, C, D), на котором определено множество функциональных зависимостей F = {A B, A C}, и пусть состояние Ri отношения R следующее:

Ri(A, B, C, D)    и F = {A B и B C }
  a1 b1 c1 d1
  a1 b1 c1 d2
  a2 b2 c2 d1
  a3 b1 c1 d3

Тогда отношение R (в состоянии Ri) будет удовлетворять и зависимости A BC.

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


F6. АКСИОМА ПСЕВДОТРАНЗИТИВНОСТИ

Если X, Y, Z и W - подмножества атрибутов отношения R, для которого выполняются зависисмости X Y и YZ W, то для него справедлива и зависимость XZ W.

Докажем, что при заданных условиях зависимость XZ W справедлива.

Из X Y по аксиоме F2 следует X Z Y Z.

По аксиоме рефлексивности F1 справедливо Z Z, из чего, по аксиоме F2 следует XZ Z.

Тогда по аксиоме F3 из XZ Y и XZ Z следует XZ YZ.

Наконец из XZ YZ и YZ W (дано) по аксиоме F5 следует XZ W, что и требовалось доказать.


Перечисленные аксиомы могут быть выведены друг из друга, что говорит об избыточности полного набора из шести приведенных аксиом, из которого различным образом можно выделить три аксиомы в качестве базиса.

Одним из распространенных вариантов является выбор в качестве базиса аксиом F1, F2 и F6, которые носят название аксиом Армстронга. Используя эти три аксиомы, можно вывести все остальные.

Докажем, например, аксиому F4 (проективности), исходя из F1, F2 и F6.

Аксиома F4 утверждает, что если X YZ , то X Y.

Доказательство. Предварительно покажем, что аксиома F5 является частным случаем аксиомы F6. Действительно, если в формальную запись аксиомы F6: X Y & YZ W ⇒ XZ W, подставить Z = Ø (Ø – пустое множество), то получится X Y & Y W ⇒ X W, т.е., аксиома F5.
     Теперь, воспользовавшись F5, докажем F4.

Из F1 следует Y Y, из чего по аксиоме F2 выводится YZ Y. Теперь из исходной посылки аксиомы F4: X YZ и полученной зависимости YZ Y по F5 следует X Y, что и требовалось доказать.

Таким образом, аксиомы F1, F2 и F6 составляют полный базис множества F1 - F6.

[ Назад  Начало раздела  Далее  Содержание]