ТОРА (9) - Лекция №2 - Функциональные зависимости

Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.

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

Пусть $R=(A_1 ... A_n)$ является функциональной схемой отношения и $X$, $Y$ - некоторые подмножества атрибутов этой схемы. Говорят, что $X$ функционально определяет $Y$ ($X\rightarrow Y$), если в любом экземпляре отношения со схемой $R$ не существует двух кортежей, совпадающих по подмножеству $X$ и не совпадающих по подмножеству $Y$

Иначе говоря, если два кортежа совпадают по $X$, то они должны совпадать и по $Y$

Например, $R=(A_1, A_2, A_3, A_4)$, есть зависимости:

• $A_1\rightarrow A_2$ (1)
• $A_1A_3\rightarrow A_4$ (2)

Предположим, что имеет место один экземпляр отношения со схемой $R$

	$A_1$	$A_2$	$A_3$	$A_4$
$R$	фирма X	улица Ленина, д.1	сахар	40
	фирма X	улица Ленина, д.1	карамель	50
	фирма X	улица Ленина, д.2	пастила	90

Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре (по крайней мере, в приведённом экземпляре схемы отношения, а других мы не знаем).

А первая ФЗ (1) не имеет место быть (в третьей строке другой номер дома портит всю картину).

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

Пусть $R$ - универсальная схема отношения, а $F$ - исходное множество функциональных зависимостей на этой схеме. Замыканием $F$ называется всё множество функциональных зависимостей, которое логически следует из $F$ - обозначается как $F^+$

Функциональная зависимость логически следует из $F$, если её можно вывести (получить) с помощью аксиом Армстронга.

Аксиомы Армстронга

Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.

Аксиомы Армстронга являются надёжными и полными.

Надёжность - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ $F$

Полнота - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.

Рефлексивность

Если $Y \subseteq X \subseteq R$

то $X\rightarrow Y$. Тривиальная аксиома.

Дополнение

Если $X\rightarrow Y$ и $Z \subseteq R$ ($Z$ может быть пустым),

тогда $X\bigcup Z\rightarrow Y\bigcup Z$ или $XZ\rightarrow YZ$

Транзитивность

Если $X\rightarrow Y$, а $Y\rightarrow Z$,

то $X\rightarrow Z$

Пример построения множества ФЗ

Пусть задана УСО (универсальная схема отношения) $R=(A, B, C)$ и зависимости $F=(A\rightarrow B, B\rightarrow C)$

1. $A\rightarrow A$, $B\rightarrow B$, $C\rightarrow C$, $AB\rightarrow A$, $AB\rightarrow B$, $AC\rightarrow A$, $AC\rightarrow C$, $BC\rightarrow B$, $BC\rightarrow C$, $ABC\rightarrow A$, $ABC\rightarrow C$, $AB\rightarrow AB$, $AC\rightarrow AC$, $BC\rightarrow BC$, $ABC\rightarrow AB$, $ABC\rightarrow AC$, $ABC\rightarrow BC$, $ABC\rightarrow ABC$
   
   
2. $A\rightarrow AB$ (1ФЗ и пополняем A), $AC\rightarrow BC$, $B\rightarrow BC$ (2 ФЗ и пополняем B), $AB\rightarrow AC$, $AC\rightarrow ABC$, $AB\rightarrow ABC$, $AB\rightarrow BC$, $A\rightarrow AC$
   
   
3. $A\rightarrow C$ (1 и 2 ФЗ), $A\rightarrow ABC$

Всё, замыкание ($F^+$) построено. Все перечисленные зависимости образуют замыкание.

Лемма

Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.

Правило объединения

Если $X\rightarrow Y$ и $X\rightarrow Z$, то $X\rightarrow YZ$

Доказательство:

1. $X\rightarrow XY$ (1 ФЗ и пополняем X);
2. $XY\rightarrow YZ$ (2 ФЗ и пополняем Y);
3. $X\rightarrow YZ$ (по аксиоме транзитивности).

Правило декомпозиции

Если $X\rightarrow Y$, а $Z \subseteq Y$, то $X\rightarrow Z$

Доказательство:

1. $X\rightarrow Y$ (по условию);
2. $Y\rightarrow Z$ (по аксиоме рефлексивности);
3. $X\rightarrow Z$ (по аксиоме транзитивности).

Правило псевдотранзитивности

Если $X\rightarrow Y$ и $WY\rightarrow Z$, то $WX\rightarrow Z$

Доказательство:

1. $WX\rightarrow WY$ (1 ФЗ и пополняем W);
2. $WY\rightarrow Z$ (по условию);
3. $WX\rightarrow Z$ (по аксиоме транзитивности).

Замыкание множества атрибутов

Замыкание $F^+$ может включать в себя очень большое количество ФЗ. Например:

$F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n)$

$X\rightarrow Y \subseteq F^+$

$Y \subseteq (A_1, A_2 ... A_n)$ и таких подмножеств может быть $2^n$

Поэтому "в лоб" замыкание $F^+$ никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ $X\rightarrow Y$ к $F^+$

Для этого применяется замыкание множества атрибутов.

Пусть $R$ - универсальная схема отношения, а $X$ - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов $X^+$ называется совокупность атрибутов $A_{i1}, A_{i2} ... A_{ik}$ таких, что $X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik}$

Алгоритм построения

Алгоритм является итерационной процедурой.

1. полагаем $i = 0$ и $X_0^+=X$, а $X_i^+$ - замыкание множества атрибутов на i-том шаге;
2. $X _{i+1} ^+ = X _i ^+ \bigcup V$, где $V$ - такое множество атрибутов в $F$, что существует ФЗ $Y\rightarrow Z$, где $Y \subseteq X _i ^+$, $V \subseteq Z$;
3. если $X_{i+1}^+ = X_i^+$, то $X^+ = X_i^+$, иначе $i = i + 1$ и возвращаемся в пункт 2.

Пример построения

Пусть $R=(A, B, C, D, E, G)$

$F=(AB\rightarrow C, C\rightarrow A, BC\rightarrow D, ACD\rightarrow B, D\rightarrow EG, BE\rightarrow C, CG\rightarrow BD, CE\rightarrow AG)$

$X = BD$

Надо построить $X^+$:

1) $i = 0$, $X _0 ^+ = BD$

2)

$i$	$Y\rightarrow Z$, для которых $Y \subseteq X_i^+$	$V\subseteq Z$	$X_{i+1}^+ = X_i^+\bigcup V$
0	$D\rightarrow EG$	$EG$	$BDEG$
1	$BE\rightarrow C$	$C$	$BDEGC$
2	$C\rightarrow A$ $BC\rightarrow D$ $CG\rightarrow BD$ $CE\rightarrow AG$	$A$	$BDEGCA$
3	$AB\rightarrow C$ $ACD\rightarrow B$	-	$BDEGCA$

Получили, что $X_4^+ = X_3^+$, а значит $X^+ = X_3^+ = BDEGCA$

Это означает, что имеют место следующие ФЗ: $BD\rightarrow B$, $BD\rightarrow D$, $BD\rightarrow E$, $BD\rightarrow G$, $BD\rightarrow C$, $BD\rightarrow A$, и все они $\subseteq F^+$

Короче, чтобы проверить $X\rightarrow Y \subseteq F^+$, необходимо построить $X^+$