ТОРА (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^+$$