ТОРА (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 | улица Ленина, д.1 | пастила | 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 Y\rightarrow Z$$ или $$XZ\rightarrow YZ$$
Транзитивность
Если $$X\rightarrow Y$$
а $$Y\rightarrow Z$$
то $$X\rightarrow Z$$
Пример построения множества ФЗ
Пусть задана УСО (универсальная схема отношения) $$R=(A, B, C)$$ и зависимости $$F=(A\rightarrow B, B\rightarrow C)$$
- $$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$$
- $$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$$
- $$A\rightarrow C$$ (1 и 2 ФЗ), $$A\rightarrow ABC$$
Всё, замыкание ($$F^+$$) построено. Все перечисленные зависимости образуют замыкание.
Лемма
Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.
Правило объединения
Если $$X\rightarrow Y$$ и $$X\rightarrow Z$$, то $$X\rightarrow YZ$$
Доказательство:
- $$X\rightarrow XY$$ (1 ФЗ и пополняем X);
- $$XY\rightarrow YZ$$ (2 ФЗ и пополняем Y);
- $$X\rightarrow YZ$$ (по аксиоме транзитивности).
Правило декомпозиции
Если $$X\rightarrow Y$$, а $$Z \subseteq Y$$, то $$X\rightarrow Z$$
Доказательство:
- $$X\rightarrow Y$$ (по условию);
- $$Y\rightarrow Z$$ (по аксиоме рефлексивности);
- $$X\rightarrow Z$$ (по аксиоме транзитивности).
Правило псевдотранзитивности
Если $$X\rightarrow Y$$ и $$WY\rightarrow Z$$, то $$WX\rightarrow Z$$
Доказательство:
- $$WX\rightarrow WY$$ (1 ФЗ и пополняем W);
- $$WY\rightarrow Z$$ (по условию);
- $$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}$$
Алгоритм построения
Алгоритм является итерационной процедурой.
- полагаем $$i = 0$$ и $$X_0^+=X$$, а $$X_i^+$$ - замыкание множества атрибутов на i-том шаге;
- $$X _{i+1} ^+ = X _i ^+ \bigcup V$$, где V - такое множество атрибутов в F, и $$Y\rightarrow Z$$, $$Y \subseteq X _i ^+$$, $$V \subseteq Z$$;
- если $$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^+$$