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