ТОРА (9) - Лекция №2 - Функциональные зависимости
Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов и покрытие
Функциональные зависимости
Пусть [math]\displaystyle{ R=(A_1 ... A_n) }[/math] является функциональной схемой отношения и [math]\displaystyle{ X }[/math], [math]\displaystyle{ Y }[/math] - некоторые подмножества атрибутов этой схемы. Говорят, что [math]\displaystyle{ X }[/math] функционально определяет [math]\displaystyle{ Y }[/math] ([math]\displaystyle{ X\rightarrow Y }[/math]), если в любом экземпляре отношения со схемой [math]\displaystyle{ R }[/math] не существует двух кортежей, совпадающих по подмножеству [math]\displaystyle{ X }[/math] и не совпадающих по подмножеству [math]\displaystyle{ Y }[/math].
Иначе говоря, если два кортежа совпадают по [math]\displaystyle{ x }[/math], то они должны совпадать и по [math]\displaystyle{ y }[/math].
Например, [math]\displaystyle{ R=(A_1, A_2, A_3, A_4) }[/math], есть зависимости:
- (1): [math]\displaystyle{ A_1\rightarrow A_2 }[/math]
- (2): [math]\displaystyle{ A_1A_3\rightarrow A_4 }[/math]
Предположим, что имеет место один экземпляр отношения со схемой [math]\displaystyle{ R }[/math]
| [math]\displaystyle{ A_1 }[/math] | [math]\displaystyle{ A_2 }[/math] | [math]\displaystyle{ A_3 }[/math] | [math]\displaystyle{ A_4 }[/math] | |
|---|---|---|---|---|
| [math]\displaystyle{ R }[/math] | фирма X | улица Ленина, д.1 | сахар | 40 |
| фирма X | улица Ленина, д.1 | карамель | 50 | |
| фирма X | улица Ленина, д.1 | пастила | 90 |
Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре. А первая ФЗ (1) не имеет место быть.
Замыкание множества функциональных зависимостей
Пусть [math]\displaystyle{ R }[/math] - универсальная схема отношения, а [math]\displaystyle{ F }[/math] - исходное множество функциональной зависимости на этой схеме. Замыканием [math]\displaystyle{ F }[/math] называется всё множество функциональной зависимости, которое логически следует из [math]\displaystyle{ F }[/math] - обозначается как [math]\displaystyle{ F^+ }[/math]
Функциональная зависимость логически следует из [math]\displaystyle{ F }[/math], если её можно вывести (получить) с помощью аксиом Армстронга.
Аксиомы Армстронга
Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.
Аксиомы Армстронга являются надёжными и полными.
Надёжность - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ [math]\displaystyle{ F }[/math].
Полнота - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.
Рефлексивность
Если [math]\displaystyle{ Y \subseteq X \subseteq R }[/math],
то [math]\displaystyle{ X\rightarrow Y }[/math]. Тривиальная аксиома.
Дополнение
Если [math]\displaystyle{ X\rightarrow Y }[/math],
[math]\displaystyle{ Z \subseteq R }[/math] ([math]\displaystyle{ Z }[/math] может быть пустым),
тогда [math]\displaystyle{ X\bigcup Y\rightarrow Z }[/math] или [math]\displaystyle{ XZ\rightarrow YZ }[/math].
Транзитивность
Если [math]\displaystyle{ X\rightarrow Y }[/math],
а [math]\displaystyle{ Y\rightarrow Z }[/math],
то [math]\displaystyle{ X\rightarrow Z }[/math].
Пример построения множества ФЗ
Пусть задана УСО (универсальная схема отношения) [math]\displaystyle{ R=(A, B, C) }[/math] и зависимости [math]\displaystyle{ F=(A\rightarrow B, B\rightarrow C) }[/math].
1) тривиальные ФЗ
[math]\displaystyle{ A\rightarrow A }[/math], [math]\displaystyle{ B\rightarrow B }[/math], [math]\displaystyle{ C\rightarrow C }[/math], [math]\displaystyle{ AB\rightarrow A }[/math], [math]\displaystyle{ AB\rightarrow B }[/math], [math]\displaystyle{ AC\rightarrow A }[/math], [math]\displaystyle{ AC\rightarrow B }[/math], [math]\displaystyle{ BC\rightarrow B }[/math], [math]\displaystyle{ BC\rightarrow C }[/math], [math]\displaystyle{ ABC\rightarrow A }[/math], [math]\displaystyle{ ABC\rightarrow C }[/math], [math]\displaystyle{ AB\rightarrow AB }[/math], [math]\displaystyle{ AC\rightarrow AC }[/math], [math]\displaystyle{ BC\rightarrow BC }[/math], [math]\displaystyle{ ABC\rightarrow AB }[/math], [math]\displaystyle{ ABC\rightarrow AC }[/math], [math]\displaystyle{ ABC\rightarrow BC }[/math], [math]\displaystyle{ ABC\rightarrow ABC }[/math]
2) [math]\displaystyle{ A\rightarrow AB }[/math] (1ФЗ и пополняем A), [math]\displaystyle{ AC\rightarrow BC }[/math], [math]\displaystyle{ B\rightarrow BC }[/math] (2 ФЗ и пополняем B), [math]\displaystyle{ AB\rightarrow AC }[/math], [math]\displaystyle{ AC\rightarrow ABC }[/math], [math]\displaystyle{ AB\rightarrow ABC }[/math], [math]\displaystyle{ AB\rightarrow BC }[/math], [math]\displaystyle{ A\rightarrow AC }[/math]
3) [math]\displaystyle{ A\rightarrow C }[/math] (1 и 2 ФЗ), [math]\displaystyle{ A\rightarrow ABC }[/math]
Всё, замыкание ([math]\displaystyle{ F^+ }[/math]) построено. Все перечисленные зависимости образуют замыкание.
Лемма
Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.
Правило объединения
Если [math]\displaystyle{ X\rightarrow Y }[/math] и [math]\displaystyle{ X\rightarrow Z }[/math], то [math]\displaystyle{ X\rightarrow YZ }[/math]
Доказательство:
- [math]\displaystyle{ X\rightarrow XY }[/math] (1 ФЗ и пополняем X);
- [math]\displaystyle{ XY\rightarrow YZ }[/math] (2 ФЗ и пополняем Y);
- [math]\displaystyle{ X\rightarrow YZ }[/math] (по аксиоме транзитивности).
Правило декомпозиции
Если [math]\displaystyle{ X\rightarrow Y }[/math], а [math]\displaystyle{ Z \subseteq Y }[/math], то [math]\displaystyle{ X\rightarrow Z }[/math]
Доказательство:
- [math]\displaystyle{ X\rightarrow Y }[/math] (по условию);
- [math]\displaystyle{ Y\rightarrow Z }[/math] (по аксиоме рефлексивности);
- [math]\displaystyle{ X\rightarrow Z }[/math] (по аксиоме транзитивности).
Правило псевдотранзитивности
Если [math]\displaystyle{ X\rightarrow Y }[/math] и [math]\displaystyle{ WY\rightarrow Z }[/math], то [math]\displaystyle{ WX\rightarrow Z }[/math].
Доказательство:
- [math]\displaystyle{ WX\rightarrow WY }[/math] (1 ФЗ и пополняем W);
- [math]\displaystyle{ WY\rightarrow Z }[/math] (по условию);
- [math]\displaystyle{ WX\rightarrow Z }[/math] (по аксиоме транзитивности).
Замыкание множества атрибутов
Замыкание [math]\displaystyle{ F^+ }[/math] может включать в себя очень большое количество ФЗ. Например:
[math]\displaystyle{ F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n) }[/math]
[math]\displaystyle{ X\rightarrow Y \subseteq F^+ }[/math]
[math]\displaystyle{ Y \subseteq (A_1, A_2 ... A_n) }[/math] и таких подмножеств может быть [math]\displaystyle{ 2^n }[/math].
Поэтому "в лоб" замыкание [math]\displaystyle{ F^+ }[/math] никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ [math]\displaystyle{ X\rightarrow Y }[/math] к [math]\displaystyle{ F^+ }[/math].
Для этого применяется замыкание множества атрибутов. Пусть [math]\displaystyle{ R }[/math] - универсальная схема отношения, а [math]\displaystyle{ X }[/math] - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов [math]\displaystyle{ X^+ }[/math] называется совокупность атрибутов [math]\displaystyle{ A_{i1}, A_{i2} ... A_{ik} }[/math] таких, что [math]\displaystyle{ X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik} }[/math].
Алгоритм построения
Алгоритм является итерационной процедурой.
- полагаем [math]\displaystyle{ i = 0 }[/math] и [math]\displaystyle{ X _0 ^+ = X }[/math], а [math]\displaystyle{ X _i ^+ }[/math] - замыкание множества атрибутов на i-том шаге;
- [math]\displaystyle{ X _{i+1} ^+ = X _i ^+ \bigcup V }[/math], где V - такое множество атрибутов в F, и [math]\displaystyle{ Y\rightarrow Z }[/math], [math]\displaystyle{ Y \subseteq X _i ^+ }[/math], [math]\displaystyle{ V \subseteq Z }[/math];
- если [math]\displaystyle{ X _{i+1} ^+ = X _i ^+ }[/math], то [math]\displaystyle{ X^+ = X _i ^+ }[/math], иначе [math]\displaystyle{ i = i + 1 }[/math] и в пункт 2.
Пример построения
Пусть [math]\displaystyle{ R=(A, B, C, D, E, G) }[/math], [math]\displaystyle{ 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) }[/math]
[math]\displaystyle{ X = BD }[/math]
Надо построить [math]\displaystyle{ X = BD }[/math]
1) [math]\displaystyle{ i = 0 }[/math], [math]\displaystyle{ X _0 ^+ = BD }[/math]
2, 3)
| i | [math]\displaystyle{ Y\rightarrow Z }[/math], для которых [math]\displaystyle{ Y \subseteq X _i ^+ }[/math] | [math]\displaystyle{ V \subseteq Z }[/math] | [math]\displaystyle{ X _{i+1} ^+ = }[/math] X _i ^+ \bigcup V | ||||
|---|---|---|---|---|---|---|---|
| 0 | [math]\displaystyle{ D\rightarrow EG }[/math] | EG | [math]\displaystyle{ BDEG }[/math] | ||||
| 1 | [math]\displaystyle{ BE\rightarrow C }[/math] | C | [math]\displaystyle{ BDEGC }[/math] | ||||
| 2 | [math]\displaystyle{ C\rightarrow A }[/math] [math]\displaystyle{ BC\rightarrow D }[/math] [math]\displaystyle{ CG\rightarrow BD }[/math] [math]\displaystyle{ CE\rightarrow AG }[/math] |
A | [math]\displaystyle{ BDEGCA }[/math] | 3 | [math]\displaystyle{ AB\rightarrow C }[/math] [math]\displaystyle{ ACD\rightarrow B }[/math] |
- | [math]\displaystyle{ BDEGCA }[/math] |
Получили, что [math]\displaystyle{ X _4 ^+ = X _3 ^+ }[/math], значит [math]\displaystyle{ X^+ = X _3 ^+ = BDEGCA }[/math]. Это означает, что имеют место следующие ФЗ: [math]\displaystyle{ BD\rightarrow B }[/math], [math]\displaystyle{ BD\rightarrow D }[/math], [math]\displaystyle{ BD\rightarrow E }[/math], [math]\displaystyle{ BD\rightarrow G }[/math], [math]\displaystyle{ BD\rightarrow C }[/math], [math]\displaystyle{ BD\rightarrow A }[/math], и все они [math]\displaystyle{ \subseteq F^+ }[/math].
Короче, чтобы проверить [math]\displaystyle{ X\rightarrow Y \subseteq F^+ }[/math], необходимо построить [math]\displaystyle{ X^+ }[/math].
Покрытие
Пусть [math]\displaystyle{ F }[/math] и [math]\displaystyle{ G }[/math] - два множества ФЗ. [math]\displaystyle{ G }[/math] называется покрытием [math]\displaystyle{ F }[/math], если имеет место равенство [math]\displaystyle{ G^+ = F^+ }[/math].
Существуют различные виды покрытий. Но мы рассмотрим только один - условно-избыточное покрытие (УИП).