ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь: различия между версиями
ILobster (обсуждение | вклад) |
ILobster (обсуждение | вклад) м (→Доказательство: подробнее) |
||
(не показаны 24 промежуточные версии 6 участников) | |||
Строка 1: | Строка 1: | ||
== | Пусть {{Формула|f=F}} и {{Формула|f=G}} - два множества ФЗ. | ||
{{Формула|f=G}} называется ''покрытием'' {{Формула|f=F}}, если имеет место равенство {{Формула|f=G^+ = F^+}} | |||
Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''. | |||
После выполнения 1) и 2) получаем замыкание | == Алгоритм построения условно-неизбыточного покрытия == | ||
1) если в множестве ФЗ {{Формула|f=F}} встречаются ФЗ с одинаковой левой частью {{Формула|f=X}}, то следует объединить эти ФЗ в одну ФЗ. Это следует из леммы объединения. Получившееся множество ФЗ обозначим {{Формула|f=G}}; | |||
2) для каждой ФЗ {{Формула|f=X\rightarrow Y}} из {{Формула|f=G}} заменить её на {{Формула|f=X\rightarrow X^+ - X}}; | |||
После выполнения 1) и 2) получаем замыкание {{Формула|f=G^+ = F^+}} | |||
=== Доказательство === | === Доказательство === | ||
Строка 11: | Строка 17: | ||
1) | 1) | ||
:если ФЗ | :Докажем, что если ФЗ {{Формула|f=X\rightarrow Y\in F}} (из этого следует, что {{Формула|f=Y \subseteq X^+}} (1) по определению замыкания множества аттрибутов), то эта ФЗ принадежит {{Формула|f=G^+}} | ||
:По построению G имеет место ФЗ: | :По построению {{Формула|f=G}} имеет место ФЗ: {{Формула|f=X\rightarrow X^+ - X}} (2) | ||
:Пополним эту ФЗ: | :Пополним эту ФЗ: {{Формула|f=X\rightarrow (X^+ - X)\bigcup X}}, получится, что {{Формула|f=X\rightarrow X^+}} (3) | ||
:Теперь по первой аксиоме Армстронга имеем | :Теперь по первой аксиоме Армстронга из (1) имеем {{Формула|f=X^+\rightarrow Y}} (4) | ||
:Значит, | :Значит, {{Формула|f=X\rightarrow Y \in G^+}}, по третьей аксиоме Армстронга, исходя из (3) и (4). | ||
2) | 2) | ||
: | :Докажем обратное, что если {{Формула|f=X\rightarrow Y \in G}}, то {{Формула|f=X\rightarrow Y \in F^+}} | ||
: | :По построению {{Формула|f=G}} имеем: {{Формула|f=Y = X^+ - X}} (5) | ||
: | : Для {{Формула|f=F}} имеем: | ||
:: {{Формула|f=X\rightarrow X^+}} (по определению) (6) | |||
:: {{Формула|f=X^+\rightarrow X^+ - X}} (1 аксиома Армстронга, так как {{Формула|f=X^+ - X\subseteq X^+}}) (7) | |||
:: {{Формула|f=X\rightarrow X^+ - X = Y}} (3 аксимома Армстронга из (6)и (7), и по равенству (5)) | |||
: | :В итоге получили {{Формула|f=X\rightarrow Y \in F^+}}. | ||
Теорема доказана. | |||
=== Пример === | |||
== | УСО: {{Формула|f=R = (A, B, C)}} | ||
Множество ФЗ: {{Формула|f=F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)}} | |||
1) | |||
:{{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A)}} | |||
2) | 2) | ||
:{{Формула|f=A^+ = ABC}}, {{Формула|f=A^+ - A = BC}} | |||
:{{Формула|f=B^+ = BAC}}, {{Формула|f=B^+ - B = AC}} | |||
:{{Формула|f=C^+ = CAB}}, {{Формула|f=C^+ - C = AB}} | |||
Тогда | Тогда {{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)}} будет являться УНП. | ||
== Свойства "хорошей" схемы БД == | == Свойства "хорошей" схемы БД == | ||
Строка 67: | Строка 76: | ||
=== Соединение без потерь === | === Соединение без потерь === | ||
Пусть | Чтобы схема БД обладала свойством соединения без потерь, необходимо, чтобы хотя бы одна из таблиц содержала ключ универсальной схемы отношений. | ||
Пусть {{Формула|f=\rho = (R_1 ... R_n)}} - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения {{Формула|f=r}} из {{Формула|f=R}} справедливо равенство: {{Формула|f=r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)}}, где {{Формула|f=\Pi_{R_i}(r)}} - это проекция экземпляра отношения {{Формула|f=r}} на множество атрибутов {{Формула|f=R_i}} | |||
==== Пример БД, не обладающей свойством соединения без потерь ==== | ==== Пример БД, не обладающей свойством соединения без потерь ==== | ||
{{Формула|f=R = (A, B, C)}} | |||
{{Формула|f=\rho = (AB, BC) = (R_1, R_2)}} | |||
{{Формула|f=F = (A\rightarrow B)}} | |||
Достаточно привести пример экземпляра | Достаточно привести пример экземпляра {{Формула|f=r}}, для которого равенство не выполняется: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}} | ||
|} | |} | ||
Строка 92: | Строка 103: | ||
! !! A !! B | ! !! A !! B | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} | ||
|} | |} | ||
| | | | ||
Строка 100: | Строка 111: | ||
| | | | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! | ! !! В !! С | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=b_1}} || {{Формула|f=c_2}} | ||
|} | |} | ||
|} | |} | ||
Полученное соединение не будет равняться | Полученное соединение не будет равняться {{Формула|f=r}}: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="4" | | | rowspan="4" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
|- align="center" bgcolor="#FFB6C1" | |- align="center" bgcolor="#FFB6C1" | ||
| | | {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_2}} | ||
|- align="center" bgcolor="#FFB6C1" | |- align="center" bgcolor="#FFB6C1" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}} | ||
|} | |} | ||
Строка 126: | Строка 137: | ||
==== Пример БД, обладающей свойством соединения без потерь ==== | ==== Пример БД, обладающей свойством соединения без потерь ==== | ||
{{Формула|f=R = (A, B, C)}} | |||
{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}} | |||
{{Формула|f=F = (A\rightarrow B)}} | |||
Возьмём тот же экземпляр: | Возьмём тот же экземпляр: | ||
Строка 137: | Строка 148: | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}} | ||
|} | |} | ||
Строка 147: | Строка 158: | ||
! !! A !! B | ! !! A !! B | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} | ||
|} | |} | ||
| | | | ||
Строка 155: | Строка 166: | ||
| | | | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! | ! !! A !! С | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=c_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=c_2}} | ||
|} | |} | ||
|} | |} | ||
Полученное соединение будет равняться | Полученное соединение будет равняться {{Формула|f=r}}: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
|- align="center" | |- align="center" | ||
| | | {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}} | ||
|} | |} | ||
Строка 177: | Строка 188: | ||
==== Алгоритм проверки схемы БД на свойство соединения без потерь ==== | ==== Алгоритм проверки схемы БД на свойство соединения без потерь ==== | ||
{{Формула|f=\rho = (R_1 ... R_n)}} | |||
{{Формула|f=R = (A_1 ... A_n)}} | |||
1) построить таблицу T: | 1) построить таблицу T: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! | ! !! {{Формула|f=A_1}} || {{Формула|f=A_2}} || ... || {{Формула|f=A_k}} | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_1}} | ||
| || || || | | || || || | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_2}} | ||
| || || || | | || || || | ||
|- align="center" | |- align="center" | ||
Строка 195: | Строка 206: | ||
| || || || | | || || || | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_n}} | ||
| || || || | | || || || | ||
|} | |} | ||
И заполнить таблицу T по правилу: если | И заполнить таблицу T по правилу: если {{Формула|f=A_j \in R_i}}, то {{Формула|f=T_{ij}=a}}, иначе {{Формула|f=T_{ij}=b_i}} | ||
2) изменить таблицу T - циклически просматривать ФЗ из | 2) изменить таблицу T - циклически просматривать ФЗ из {{Формула|f=F}} в любом порядке, и для очередной ФЗ {{Формула|f=X\rightarrow Y \in F}} выполнить следующие действия: | ||
* найти в таблице T строки, совпадающие по атрибутам | * найти в таблице T строки, совпадающие по атрибутам {{Формула|f=X}} (по левой части); | ||
* если хотя бы в одной такой строке значение атрибута | * если хотя бы в одной такой строке значение атрибута {{Формула|f=A_m \in Y = a}}, то во всех найденных строках присвоить {{Формула|f=A_m = a}}, иначе присвоить {{Формула|f=A_m = b_i}} ({{Формула|f=i}} - номер одной из найденных строк), {{Формула|f=b_i}} должно быть одинаково во всех указанных строках); | ||
* выполнить предыдущие два пункта для всех атрибутов | * выполнить предыдущие два пункта для всех атрибутов {{Формула|f=A_l \in Y}}; | ||
* выполнить предыдущие три пункта для всех ФЗ из | * выполнить предыдущие три пункта для всех ФЗ из {{Формула|f=F}}, циклически их просматривая. | ||
3) алгоритм останавливается, если при очередном просмотре ФЗ из | 3) алгоритм останавливается, если при очередном просмотре ФЗ из {{Формула|f=F}}: | ||
* не произошло никаких изменений в таблице T; | * не произошло никаких изменений в таблице T; | ||
* какая-нибудь строка в T не стала состоять сплошь из символов | * какая-нибудь строка в T не стала состоять сплошь из символов {{Формула|f=a}} (наличие такой строки и говорит о выполнении свойства соединения без потерь). | ||
===== Пример ===== | ===== Пример ===== | ||
Пусть | Пусть {{Формула|f=R = (A, B, C)}} | ||
{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}} | |||
{{Формула|f=F = (A\rightarrow B)}} | |||
Доказать, что | Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь. | ||
1) | 1) | ||
Строка 227: | Строка 238: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
! | ! AC | ||
| | | {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} | ||
|} | |} | ||
Строка 241: | Строка 252: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
! | ! AC | ||
| | | {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} | ||
|} | |} | ||
| | | | ||
Строка 253: | Строка 264: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
! | ! AC | ||
| | | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} | ||
|} | |} | ||
|} | |} | ||
Получили строку, сплошь состоящую из | Получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь. | ||
===== Другой пример ===== | ===== Другой пример ===== | ||
Пусть | Пусть {{Формула|f=R = (A, B, C, D, E, F, P, S)}} | ||
{{Формула|f=\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)}} | |||
{{Формула|f=F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)}} | |||
Доказать, что | Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь. | ||
1) | 1) | ||
Строка 278: | Строка 289: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
! ACDPS | ! ACDPS | ||
| | | {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! BCPS | ! BCPS | ||
| | | {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! DEF | ! DEF | ||
| | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} | ||
|} | |} | ||
Строка 298: | Строка 309: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! ACDPS | ! ACDPS | ||
| | | {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! BCPS | ! BCPS | ||
| | | {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! DEF | ! DEF | ||
| | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} | ||
|} | |} | ||
Строка 316: | Строка 327: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! ACDPS | ! ACDPS | ||
| | | {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! BCPS | ! BCPS | ||
| | | {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! DEF | ! DEF | ||
| | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} | ||
|} | |} | ||
Вот и получили строку, сплошь состоящую из | Вот и получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь. | ||
{{Forward|l=ТОРА (9) - Лекция №4 - Хорошая схема БД - Сохранение ФЗ}} | |||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | [[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | ||
[[Категория:Конспекты лекций и семинаров]] | [[Категория:Конспекты лекций и семинаров]] |
Текущая версия от 18:58, 21 января 2013
Пусть $$F$$ и $$G$$ - два множества ФЗ.
$$G$$ называется покрытием $$F$$, если имеет место равенство $$G^+ = F^+$$
Существуют различные виды покрытий. Но мы рассмотрим только один - условно-неизбыточное покрытие.
Алгоритм построения условно-неизбыточного покрытия
1) если в множестве ФЗ $$F$$ встречаются ФЗ с одинаковой левой частью $$X$$, то следует объединить эти ФЗ в одну ФЗ. Это следует из леммы объединения. Получившееся множество ФЗ обозначим $$G$$;
2) для каждой ФЗ $$X\rightarrow Y$$ из $$G$$ заменить её на $$X\rightarrow X^+ - X$$;
После выполнения 1) и 2) получаем замыкание $$G^+ = F^+$$
Доказательство
1)
- Докажем, что если ФЗ $$X\rightarrow Y\in F$$ (из этого следует, что $$Y \subseteq X^+$$ (1) по определению замыкания множества аттрибутов), то эта ФЗ принадежит $$G^+$$
- По построению $$G$$ имеет место ФЗ: $$X\rightarrow X^+ - X$$ (2)
- Пополним эту ФЗ: $$X\rightarrow (X^+ - X)\bigcup X$$, получится, что $$X\rightarrow X^+$$ (3)
- Теперь по первой аксиоме Армстронга из (1) имеем $$X^+\rightarrow Y$$ (4)
- Значит, $$X\rightarrow Y \in G^+$$, по третьей аксиоме Армстронга, исходя из (3) и (4).
2)
- Докажем обратное, что если $$X\rightarrow Y \in G$$, то $$X\rightarrow Y \in F^+$$
- По построению $$G$$ имеем: $$Y = X^+ - X$$ (5)
- Для $$F$$ имеем:
- $$X\rightarrow X^+$$ (по определению) (6)
- $$X^+\rightarrow X^+ - X$$ (1 аксиома Армстронга, так как $$X^+ - X\subseteq X^+$$) (7)
- $$X\rightarrow X^+ - X = Y$$ (3 аксимома Армстронга из (6)и (7), и по равенству (5))
- В итоге получили $$X\rightarrow Y \in F^+$$.
Теорема доказана.
Пример
УСО: $$R = (A, B, C)$$
Множество ФЗ: $$F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)$$
1)
- $$G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A)$$
2)
- $$A^+ = ABC$$, $$A^+ - A = BC$$
- $$B^+ = BAC$$, $$B^+ - B = AC$$
- $$C^+ = CAB$$, $$C^+ - C = AB$$
Тогда $$G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)$$ будет являться УНП.
Свойства "хорошей" схемы БД
"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
- соединение без потерь;
- сохранение ФЗ;
- каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
- избыточность;
- потенциальная противоречивсть;
- аномалия обновления;
- аномалия удаления.
Соединение без потерь
Чтобы схема БД обладала свойством соединения без потерь, необходимо, чтобы хотя бы одна из таблиц содержала ключ универсальной схемы отношений.
Пусть $$\rho = (R_1 ... R_n)$$ - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения $$r$$ из $$R$$ справедливо равенство: $$r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)$$, где $$\Pi_{R_i}(r)$$ - это проекция экземпляра отношения $$r$$ на множество атрибутов $$R_i$$
Пример БД, не обладающей свойством соединения без потерь
$$R = (A, B, C)$$
$$\rho = (AB, BC) = (R_1, R_2)$$
$$F = (A\rightarrow B)$$
Достаточно привести пример экземпляра $$r$$, для которого равенство не выполняется:
A | B | C | |
---|---|---|---|
$$r$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
|
|
Полученное соединение не будет равняться $$r$$:
A | B | C | |
---|---|---|---|
$$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_1$$ | $$b_1$$ | $$c_2$$ | |
$$a_2$$ | $$b_1$$ | $$c_1$$ | |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.
Пример БД, обладающей свойством соединения без потерь
$$R = (A, B, C)$$
$$\rho = (AB, AC) = (R_1, R_2)$$
$$F = (A\rightarrow B)$$
Возьмём тот же экземпляр:
A | B | C | |
---|---|---|---|
$$r$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
|
|
Полученное соединение будет равняться $$r$$:
A | B | C | |
---|---|---|---|
$$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.
Алгоритм проверки схемы БД на свойство соединения без потерь
$$\rho = (R_1 ... R_n)$$
$$R = (A_1 ... A_n)$$
1) построить таблицу T:
$$A_1$$ | $$A_2$$ | ... | $$A_k$$ | |
---|---|---|---|---|
$$R_1$$ | ||||
$$R_2$$ | ||||
... | ||||
$$R_n$$ |
И заполнить таблицу T по правилу: если $$A_j \in R_i$$, то $$T_{ij}=a$$, иначе $$T_{ij}=b_i$$
2) изменить таблицу T - циклически просматривать ФЗ из $$F$$ в любом порядке, и для очередной ФЗ $$X\rightarrow Y \in F$$ выполнить следующие действия:
- найти в таблице T строки, совпадающие по атрибутам $$X$$ (по левой части);
- если хотя бы в одной такой строке значение атрибута $$A_m \in Y = a$$, то во всех найденных строках присвоить $$A_m = a$$, иначе присвоить $$A_m = b_i$$ ($$i$$ - номер одной из найденных строк), $$b_i$$ должно быть одинаково во всех указанных строках);
- выполнить предыдущие два пункта для всех атрибутов $$A_l \in Y$$;
- выполнить предыдущие три пункта для всех ФЗ из $$F$$, циклически их просматривая.
3) алгоритм останавливается, если при очередном просмотре ФЗ из $$F$$:
- не произошло никаких изменений в таблице T;
- какая-нибудь строка в T не стала состоять сплошь из символов $$a$$ (наличие такой строки и говорит о выполнении свойства соединения без потерь).
Пример
Пусть $$R = (A, B, C)$$
$$\rho = (AB, AC) = (R_1, R_2)$$
$$F = (A\rightarrow B)$$
Доказать, что $$\rho$$ обладает свойством соединения без потерь.
1)
A | B | C | |
---|---|---|---|
AB | $$a$$ | $$a$$ | $$b_1$$ |
AC | $$a$$ | $$b_2$$ | $$a$$ |
2)
|
|
Получили строку, сплошь состоящую из $$a$$. Значит $$\rho$$ обладает свойством соединения без потерь.
Другой пример
Пусть $$R = (A, B, C, D, E, F, P, S)$$
$$\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)$$
$$F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)$$
Доказать, что $$\rho$$ обладает свойством соединения без потерь.
1)
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
ACDPS | $$a$$ | $$b_2$$ | $$a$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$a$$ |
BCPS | $$b_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ |
DEF | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$b_4$$ | $$b_4$$ |
2)
первый просмотр:
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$a$$ | $$a$$ |
ACDPS | $$a$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
BCPS | $$b_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ |
DEF | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$b_4$$ | $$b_4$$ |
второй просмотр:
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
ACDPS | $$a$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
BCPS | $$b_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ |
DEF | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$b_4$$ | $$b_4$$ |
Вот и получили строку, сплошь состоящую из $$a$$. Значит $$\rho$$ обладает свойством соединения без потерь.
продолжение...