ТОРА (9) - Лекция №2 - Функциональные зависимости: различия между версиями
ILobster (обсуждение | вклад) м (→Алгоритм построения: формула) |
ILobster (обсуждение | вклад) м (→Замыкание множества атрибутов: оформление) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 5: | Строка 5: | ||
Пусть {{Формула|f=R=(A_1 ... A_n)}} является функциональной схемой отношения и {{Формула|f=X}}, {{Формула|f=Y}} - некоторые подмножества атрибутов этой схемы. Говорят, что {{Формула|f=X}} функционально определяет {{Формула|f=Y}} ({{Формула|f=X\rightarrow Y}}), если в любом экземпляре отношения со схемой {{Формула|f=R}} не существует двух кортежей, совпадающих по подмножеству {{Формула|f=X}} и не совпадающих по подмножеству {{Формула|f=Y}} | Пусть {{Формула|f=R=(A_1 ... A_n)}} является функциональной схемой отношения и {{Формула|f=X}}, {{Формула|f=Y}} - некоторые подмножества атрибутов этой схемы. Говорят, что {{Формула|f=X}} функционально определяет {{Формула|f=Y}} ({{Формула|f=X\rightarrow Y}}), если в любом экземпляре отношения со схемой {{Формула|f=R}} не существует двух кортежей, совпадающих по подмножеству {{Формула|f=X}} и не совпадающих по подмножеству {{Формула|f=Y}} | ||
Иначе говоря, если два кортежа совпадают по {{Формула|f= | Иначе говоря, если два кортежа совпадают по {{Формула|f=X}}, то они должны совпадать и по {{Формула|f=Y}} | ||
Например, {{Формула|f=R=(A_1, A_2, A_3, A_4)}}, есть зависимости: | Например, {{Формула|f=R=(A_1, A_2, A_3, A_4)}}, есть зависимости: | ||
Строка 114: | Строка 114: | ||
Поэтому "в лоб" замыкание {{Формула|f=F^+}} никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ {{Формула|f=X\rightarrow Y}} к {{Формула|f=F^+}} | Поэтому "в лоб" замыкание {{Формула|f=F^+}} никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ {{Формула|f=X\rightarrow Y}} к {{Формула|f=F^+}} | ||
Для этого применяется ''замыкание множества атрибутов''. Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=X}} - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов {{Формула|f=X^+}} называется совокупность атрибутов {{Формула|f=A_{i1}, A_{i2} ... A_{ik} }} таких, что {{Формула|f=X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik} }} | Для этого применяется ''замыкание множества атрибутов''. | ||
Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=X}} - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов {{Формула|f=X^+}} называется совокупность атрибутов {{Формула|f=A_{i1}, A_{i2} ... A_{ik} }} таких, что {{Формула|f=X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik} }} | |||
=== Алгоритм построения === | === Алгоритм построения === | ||
Строка 121: | Строка 123: | ||
# полагаем {{Формула|f=i = 0}} и {{Формула|f=X_0^+=X}}, а {{Формула|f=X_i^+}} - замыкание множества атрибутов на i-том шаге; | # полагаем {{Формула|f=i = 0}} и {{Формула|f=X_0^+=X}}, а {{Формула|f=X_i^+}} - замыкание множества атрибутов на i-том шаге; | ||
# {{Формула|f=X _{i+1} ^+ = X _i ^+ \bigcup V}}, где V - такое множество атрибутов в {{Формула|f=F}}, что существует ФЗ {{Формула|f=Y\rightarrow Z}}, где {{Формула|f=Y \subseteq X _i ^+}}, {{Формула|f=V \subseteq Z}}; | # {{Формула|f=X _{i+1} ^+ = X _i ^+ \bigcup V}}, где {{Формула|f=V}} - такое множество атрибутов в {{Формула|f=F}}, что существует ФЗ {{Формула|f=Y\rightarrow Z}}, где {{Формула|f=Y \subseteq X _i ^+}}, {{Формула|f=V \subseteq Z}}; | ||
# если {{Формула|f=X_{i+1}^+ = X_i^+}}, то {{Формула|f=X^+ = X_i^+}}, иначе {{Формула|f=i = i + 1}} и возвращаемся в пункт 2. | # если {{Формула|f=X_{i+1}^+ = X_i^+}}, то {{Формула|f=X^+ = X_i^+}}, иначе {{Формула|f=i = i + 1}} и возвращаемся в пункт 2. | ||
Строка 152: | Строка 154: | ||
Получили, что {{Формула|f=X_4^+ = X_3^+}}, а значит {{Формула|f=X^+ = X_3^+ = BDEGCA}} | Получили, что {{Формула|f=X_4^+ = X_3^+}}, а значит {{Формула|f=X^+ = X_3^+ = BDEGCA}} | ||
Это означает, что имеют место следующие ФЗ: | Это означает, что имеют место следующие ФЗ: {{Формула|f=BD\rightarrow B}}, {{Формула|f=BD\rightarrow D}}, {{Формула|f=BD\rightarrow E}}, {{Формула|f=BD\rightarrow G}}, {{Формула|f=BD\rightarrow C}}, {{Формула|f=BD\rightarrow A}}, и все они {{Формула|f=\subseteq F^+}} | ||
Короче, чтобы проверить {{Формула|f=X\rightarrow Y \subseteq F^+}}, необходимо построить {{Формула|f=X^+}} | Короче, чтобы проверить {{Формула|f=X\rightarrow Y \subseteq F^+}}, необходимо построить {{Формула|f=X^+}} |
Текущая версия от 18:46, 21 января 2013
Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.
Функциональные зависимости
Пусть $$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)$$
- $$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^+$$