ТОРА (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$ (из этого следует, что $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$ обладает свойством соединения без потерь.
продолжение...
