ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь
Пусть $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$, то эта ФЗ принадежит $G^+$, а из этого следует, что $Y \subseteq X^+$
- По построению G имеет место ФЗ: $X\rightarrow X^+ - X$
- Пополним эту ФЗ: $X\rightarrow (X^+ - X)\bigcup X = X^+$
- Теперь по первой аксиоме Армстронга имеем $X^+\rightarrow Y$
- Значит, $X\rightarrow Y \in G^+$, по третьей аксиоме Армстронга.
2)
- $X\rightarrow Y \in G$, $X\rightarrow Y \in F^+$
- $Y = X^+ - X$
- $X\rightarrow X^+$ (по определению)
- $X^+\rightarrow X^+ - X$ (1 аксиома Армстронга)
- $X^+\rightarrow X^+ - X = Y$ (3 аксимома Армстронга)
- $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$ |
BC | $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$ обладает свойством соединения без потерь.