ТОРА (9) - Лекция №2 - Функциональные зависимости: различия между версиями
ILobster (обсуждение | вклад) |
ILobster (обсуждение | вклад) мНет описания правки |
||
Строка 3: | Строка 3: | ||
== Функциональные зависимости == | == Функциональные зависимости == | ||
Пусть | Пусть {{Формула|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=x}}, то они должны совпадать и по {{Формула|f=y}} | ||
Например, | Например, {{Формула|f=R=(A_1, A_2, A_3, A_4)}}, есть зависимости: | ||
* | * {{Формула|f=A_1\rightarrow A_2}} (1) | ||
* | * {{Формула|f=A_1A_3\rightarrow A_4}} (2) | ||
Предположим, что имеет место один экземпляр отношения со схемой | Предположим, что имеет место один экземпляр отношения со схемой {{Формула|f=R}} | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! | ! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}} | ||
|- align="center" | |- align="center" | ||
| rowspan="3" | | | rowspan="3" | {{Формула|f=R}} || фирма X || улица Ленина, д.1 || сахар || 40 | ||
|- align="center" | |- align="center" | ||
| фирма X || улица Ленина, д.1 || карамель || 50 | | фирма X || улица Ленина, д.1 || карамель || 50 | ||
Строка 27: | Строка 27: | ||
== Замыкание множества функциональных зависимостей == | == Замыкание множества функциональных зависимостей == | ||
Пусть | Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=F}} - исходное множество функциональной зависимости на этой схеме. Замыканием {{Формула|f=F}} называется всё множество функциональной зависимости, которое логически следует из {{Формула|f=F}} - обозначается как {{Формула|f=F^+}} | ||
Функциональная зависимость логически следует из | Функциональная зависимость логически следует из {{Формула|f=F}}, если её можно вывести (получить) с помощью аксиом Армстронга. | ||
=== Аксиомы Армстронга === | === Аксиомы Армстронга === | ||
Строка 37: | Строка 37: | ||
Аксиомы Армстронга являются надёжными и полными. | Аксиомы Армстронга являются надёжными и полными. | ||
'''Надёжность''' - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ | '''Надёжность''' - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ {{Формула|f=F}} | ||
'''Полнота''' - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга. | '''Полнота''' - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга. | ||
Строка 43: | Строка 43: | ||
==== Рефлексивность ==== | ==== Рефлексивность ==== | ||
Если | Если {{Формула|f=Y \subseteq X \subseteq R}} | ||
то | то {{Формула|f=X\rightarrow Y}}. Тривиальная аксиома. | ||
==== Дополнение ==== | ==== Дополнение ==== | ||
Если | Если {{Формула|f=X\rightarrow Y}}, | ||
{{Формула|f=Z \subseteq R}} ({{Формула|f=Z}} может быть пустым), | |||
тогда | тогда {{Формула|f=X\bigcup Y\rightarrow Z}} или {{Формула|f=XZ\rightarrow YZ}} | ||
==== Транзитивность ==== | ==== Транзитивность ==== | ||
Если | Если {{Формула|f=X\rightarrow Y}} | ||
а | а {{Формула|f=Y\rightarrow Z}} | ||
то | то {{Формула|f=X\rightarrow Z}} | ||
=== Пример построения множества ФЗ === | === Пример построения множества ФЗ === | ||
Пусть задана УСО (универсальная схема отношения) | Пусть задана УСО (универсальная схема отношения) {{Формула|f=R=(A, B, C)}} и зависимости {{Формула|f=F=(A\rightarrow B, B\rightarrow C)}} | ||
# | # {{Формула|f=A\rightarrow A}}, {{Формула|f=B\rightarrow B}}, {{Формула|f=C\rightarrow C}}, {{Формула|f=AB\rightarrow A}}, {{Формула|f=AB\rightarrow B}}, {{Формула|f=AC\rightarrow A}}, {{Формула|f=AC\rightarrow C}}, {{Формула|f=BC\rightarrow B}}, {{Формула|f=BC\rightarrow C}}, {{Формула|f=ABC\rightarrow A}}, {{Формула|f=ABC\rightarrow C}}, {{Формула|f=AB\rightarrow AB}}, {{Формула|f=AC\rightarrow AC}}, {{Формула|f=BC\rightarrow BC}}, {{Формула|f=ABC\rightarrow AB}}, {{Формула|f=ABC\rightarrow AC}}, {{Формула|f=ABC\rightarrow BC}}, {{Формула|f=ABC\rightarrow ABC}}<br><br> | ||
# | # {{Формула|f=A\rightarrow AB}} (1ФЗ и пополняем A), {{Формула|f=AC\rightarrow BC}}, {{Формула|f=B\rightarrow BC}} (2 ФЗ и пополняем B), {{Формула|f=AB\rightarrow AC}}, {{Формула|f=AC\rightarrow ABC}}, {{Формула|f=AB\rightarrow ABC}}, {{Формула|f=AB\rightarrow BC}}, {{Формула|f=A\rightarrow AC}}<br><br> | ||
# | # {{Формула|f=A\rightarrow C}} (1 и 2 ФЗ), {{Формула|f=A\rightarrow ABC}} | ||
Всё, замыкание ( | Всё, замыкание ({{Формула|f=F^+}}) построено. Все перечисленные зависимости образуют замыкание. | ||
=== Лемма === | === Лемма === | ||
Строка 79: | Строка 79: | ||
==== Правило объединения ==== | ==== Правило объединения ==== | ||
Если | Если {{Формула|f=X\rightarrow Y}} и {{Формула|f=X\rightarrow Z}}, то {{Формула|f=X\rightarrow YZ}} | ||
Доказательство: | Доказательство: | ||
# | # {{Формула|f=X\rightarrow XY}} (1 ФЗ и пополняем X); | ||
# | # {{Формула|f=XY\rightarrow YZ}} (2 ФЗ и пополняем Y); | ||
# | # {{Формула|f=X\rightarrow YZ}} (по аксиоме транзитивности). | ||
==== Правило декомпозиции ==== | ==== Правило декомпозиции ==== | ||
Если | Если {{Формула|f=X\rightarrow Y}}, а {{Формула|f=Z \subseteq Y}}, то {{Формула|f=X\rightarrow Z}} | ||
Доказательство: | Доказательство: | ||
# | # {{Формула|f=X\rightarrow Y}} (по условию); | ||
# | # {{Формула|f=Y\rightarrow Z}} (по аксиоме рефлексивности); | ||
# | # {{Формула|f=X\rightarrow Z}} (по аксиоме транзитивности). | ||
==== Правило псевдотранзитивности ==== | ==== Правило псевдотранзитивности ==== | ||
Если | Если {{Формула|f=X\rightarrow Y}} и {{Формула|f=WY\rightarrow Z}}, то {{Формула|f=WX\rightarrow Z}} | ||
Доказательство: | Доказательство: | ||
# | # {{Формула|f=WX\rightarrow WY}} (1 ФЗ и пополняем W); | ||
# | # {{Формула|f=WY\rightarrow Z}} (по условию); | ||
# | # {{Формула|f=WX\rightarrow Z}} (по аксиоме транзитивности). | ||
== Замыкание множества атрибутов == | == Замыкание множества атрибутов == | ||
Замыкание | Замыкание {{Формула|f=F^+}} может включать в себя очень большое количество ФЗ. Например: | ||
$F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n)$ | $F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n)$ | ||
{{Формула|f=X\rightarrow Y \subseteq F^+}} | |||
{{Формула|f=Y \subseteq (A_1, A_2 ... A_n)}} и таких подмножеств может быть {{Формула|f=2^n}} | |||
Поэтому "в лоб" замыкание | Поэтому "в лоб" замыкание {{Формула|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} }} | ||
=== Алгоритм построения === | === Алгоритм построения === | ||
Строка 122: | Строка 122: | ||
Алгоритм является итерационной процедурой. | Алгоритм является итерационной процедурой. | ||
# полагаем | # полагаем {{Формула|f=i = 0}} и {{Формула|f=X_0^+=X}}, а {{Формула|f=X_i^+}} - замыкание множества атрибутов на i-том шаге; | ||
# | # {{Формула|f=X _{i+1} ^+ = X _i ^+ \bigcup V}}, где V - такое множество атрибутов в 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=R=(A, B, C, D, E, G)}} | ||
{{Формула|f=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)}} | |||
{{Формула|f=X = BD}} | |||
Надо построить | Надо построить {{Формула|f=X^+}}: | ||
1) {{Формула|f=i = 0}}, {{Формула|f=X _0 ^+ = BD}} | |||
2) | |||
{| class="wikitable" | {| class="wikitable" | ||
! | ! {{Формула|f=i}} !! {{Формула|f=Y\rightarrow Z}}, для которых {{Формула|f=Y \subseteq X_i^+}} !! {{Формула|f=V\subseteq Z}} !! {{Формула|f=X_{i+1}^+ = X_i^+\bigcup V}} | ||
|- align="center" | |- align="center" | ||
| 0 || | | 0 || {{Формула|f=D\rightarrow EG}} || {{Формула|f=EG}} || {{Формула|f=BDEG}} | ||
|- align="center" | |- align="center" | ||
| 1 || | | 1 || {{Формула|f=BE\rightarrow C}} || {{Формула|f=C}} || {{Формула|f=BDEGC}} | ||
|- align="center" | |- align="center" | ||
| 2 || | | 2 || {{Формула|f=C\rightarrow A}}<br>{{Формула|f=BC\rightarrow D}}<br>{{Формула|f=CG\rightarrow BD}}<br>{{Формула|f=CE\rightarrow AG}} || {{Формула|f=A}} || {{Формула|f=BDEGCA}} | ||
|- align="center" | |- align="center" | ||
| 3 || | | 3 || {{Формула|f=AB\rightarrow C}}<br>{{Формула|f=ACD\rightarrow B}} || - || {{Формула|f=BDEGCA}} | ||
|} | |} | ||
Получили, что | Получили, что {{Формула|f=X_4^+ = X_3^+}} | ||
значит | значит {{Формула|f=X^+ = X_3^+ = BDEGCA}} | ||
Это означает, что имеют место следующие ФЗ: $BD\rightarrow B$, | Это означает, что имеют место следующие ФЗ: $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^+}} | ||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | [[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | ||
[[Категория:Конспекты лекций и семинаров]] | [[Категория:Конспекты лекций и семинаров]] |
Версия от 15:03, 22 сентября 2012
Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.
Функциональные зависимости
Пусть $$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^+$$