ТОРА (9) - Лекция №4 - Хорошая схема БД - Сохранение ФЗ
...начало
Свойства "хорошей" схемы БД
Соединение без потерь
Теорема о свойстве соединения без потерь
Пусть $\rho=(R_1, R_2)$ и $F$ - множество ФЗ.
$\rho$ обладает свойством соединения без потерь тогда и только тогда, когда выполняется хотя бы одно из:
- $R_1\bigcap R_2\rightarrow R_1 - R_2$ (1)
- $R_1\bigcap R_2\rightarrow R_2 - R_1$ (2)
Доказательство
1)
| $R_1 - R_2$ | $R_1\bigcap R_2$ | $R_2 - R_1$ | |||||||
|---|---|---|---|---|---|---|---|---|---|
| $A_1$ | ... | $A_k$ | $A_{k+1}$ | ... | $A_m$ | $A_{m+1}$ | ... | $A_n$ | |
| $R_1$ | $a$ | ... | $a$ | $a$ | ... | $a$ | $b_1$ | ... | $b_1$ |
| $R_2$ | $b_2$ | ... | $b_2$ | $a$ | ... | $a$ | $a$ | ... | $a$ |
| $R_1 - R_2$ | $R_1\bigcap R_2$ | $R_2 - R_1$ | |||||||
|---|---|---|---|---|---|---|---|---|---|
| $A_1$ | ... | $A_k$ | $A_{k+1}$ | ... | $A_m$ | $A_{m+1}$ | ... | $A_n$ | |
| $R_1$ | $a$ | ... | $a$ | $a$ | ... | $a$ | $b_1$ | ... | $b_1$ |
| $R_2$ | $a$ | ... | $a$ | $a$ | ... | $a$ | $a$ | ... | $a$ |
- Получили строку, сплошь состоящую из $a$.
2)
- Теперь докажем обратное, что если $\rho$ обладает соединением без потерь, то имеет место одна из ФЗ: (1) или (2).
- $r=\Pi_{R_1}(r)\bowtie\Pi_{R_2}(r)$ (3)
- $r$ - это $R_1\bigcup R_2$ (экземпляр универсальной схемы отношений)
| $R_1 - R_2$ | $R_1\bigcap R_2$ | $R_2 - R_1$ |
|---|---|---|
| $a_1$ | $b_1$ | $c_1$ |
| $a_2$ | $b_2$ | $c_2$ |
| ... | ... | ... |
| $a_n$ | $b_n$ | $c_n$ |
|
|
- Если выполняется равенство (3), то возможны два варианта:
- 1) $b_i\neq b_j$, $i\neq j$;
- 2) некоторые $b_i$ совпадают, $b_1 = b_2$.
- Тогда для выполнения равенства (3) необходимо, чтобы выполнялось одно из двух:
- $a_1 = a_2$;
- $c_1 = c_2$.
| $R_1 - R_2$ | $R_1\bigcap R_2$ | $R_2 - R_1$ | |
|---|---|---|---|
| $\Pi_{R_1}(r)\bowtie\Pi_{R_2}(r)$ | $a_1$ | $b_1$ | $c_1$ |
| $a_1$ | $b_1(=b_2)$ | $c_2$ | |
| $a_2$ | $b_2(=b_1)$ | $c_1$ | |
| $a_2$ | $b_2$ | $c_2$ | |
| $a_3$ | $b_3$ | $c_3$ | |
| ... | ... | ... | |
| $N+2$ | $a_n$ | $b_n$ | $c_n$ |
- 2 и 3 кортежи - лишние. Чтобы они не были лишними, они должны совпадать с одним из других кортежей, чтобы их можно было вычеркнуть.
- Предположим, $a_1 = a_2$, тогда что-то там насовпадало и 2 и 3 кортежи можно вычеркнуть.
- Аналогичные рассуждения можно провести для случая, когда $c_1 = c_2$, но тогда получаем:
- для варианта $b_i\neq b_j$ имеют место обе ФЗ : (1) и (2);
- для варианта с некоторыми совпадающими $b_i$ работает либо (1), либо (2).
- Всё, теорема доказана.
Следствие из теоремы
Пусть $R_1$ и $R_2$ - это сущности БД и они связаны между собой. Тогда схема БД обладает соединением без потерь, если общий атрибут $R_1$ и $R_2$ содержит ключ одной из этих схем отношений.
$R_1\bigcap R_2 = A$
$R_1 - R_2 = B$
$R_1\bigcap R_2\rightarrow R_1 - R_2$, потому что $A\rightarrow B$, так как является ключом.
Свойство сохранения ФЗ
Пусть дана схема БД $\rho=(R_1 ... R_n)$ и $F$ - множество ФЗ.
Проекцией $F$ на $R_i$ называется такое множество ФЗ, принадлежащее $F^+$, что $XY\subseteq R_i$, $\Pi_{R_i}(F)$
Схема $\rho$ обладает свойством сохранения ФЗ, если:
$(\bigcup_{i=1}^n\Pi_{R_i}(F))^+ = F^+$ - ФЗ могут быть декомпозированны по схеме отношений (тогда проверку надо будет выполнять только в рамках отдельных таблиц при включении новой записи).
Пример схемы БД без свойства сохранения ФЗ
$R=(A,B,C)$ - универсальная схема отношений.
$F=(A\rightarrow B, B\rightarrow C)$
$\rho=(AB, AC)=(R_1, R_2)$
Надо доказать, что $\rho$ не обладает свойством сохранения ФЗ.
Первая проекция: $\Pi_{R_1}(F) = F_1 = (A\rightarrow A, B\rightarrow B, AB\rightarrow A, AB\rightarrow B, AB\rightarrow AB, A\rightarrow B, A\rightarrow AB)$
Вторая проекция: $\Pi_{R_2}(F) = F_2 = (A\rightarrow A, C\rightarrow C, AC\rightarrow A, AC\rightarrow C, AC\rightarrow AC, A\rightarrow C, A\rightarrow AC)$
$B\rightarrow C\in F^+$ по определению.
$B\rightarrow C\notin (F_1\bigcup F_2)^+$ - не работает, так что эта БД не обладает свойством сохранения ФЗ.
$B^+ = B$, $C\notin B^+$
Пример схемы БД со свойством сохранения ФЗ
$R=(A,B,C)$ - универсальная схема отношений.
$F=(A\rightarrow B, B\rightarrow C)$
$\rho=(AB, BC)=(R_1, R_2)$
Надо доказать, что $\rho$ обладает свойством сохранения ФЗ.
Первая проекция: $\Pi_{R_1}(F) = F_1 = ($тривиальные ФЗ, $A\rightarrow B, A\rightarrow AB)$
Вторая проекция: $\Pi_{R_2}(F) = F_2 = ($тривиальные ФЗ, $B\rightarrow C, B\rightarrow BC)$
$(F_1\bigcup F_2)^+ = ($тривиальные ФЗ, $A\rightarrow B, A\rightarrow AB, B\rightarrow C, B\rightarrow BC, A\rightarrow C, A\rightarrow AC)$, а это и есть по определению само $F^+$, что и доказывает, что данная схема БД обладает свойством сохранения ФЗ.
Алгоритм проверки схемы БД на обладание свойством сохранения ФЗ
$\rho = (R_1 ... R_n)$
Алгоритм:
- 1) построить условно-неизбыточное покрытие (УНП), взять $H = \varnothing$;
- 2) каждую ФЗ из УНП разбить на совокупность ФЗ с одним атрибутом в правой части,
- то есть заменить
- $X\rightarrow A_1 A_2 ... A_k$
- на
- $X\rightarrow A_1$, $X\rightarrow A_2$, ..., $X\rightarrow A_k$.
- Обозначить полученную ФЗ как $G$;
- то есть заменить
- 3) выбрать очередную ФЗ из $G$. Найти такую схему отношения $R_i$, для которой справедливо включение $XA\subseteq R_i$.
- Если такой схемы отношений не существует, то поместить ФЗ $X\rightarrow A$ в множество $H$;
- 4) если все ФЗ из $G$ рассмотрены, то перейти к следующему пункту, иначе к предыдущему;
- 5) если $H$ пусто, то завершить алгоритм. $\rho$ обладает свойством сохранения ФЗ. Иначе перейти к следующему пункту;
- 6) просмотреть все ФЗ из $H$. Если какая-либо ФЗ $X\rightarrow A \in H$ не выводится из множества $G - H$, то завершить алгоритм. $\rho$ не обладает свойством сохранения ФЗ. Иначе завершить алгоритм, и тогда $\rho$ обладает свойством сохранения ФЗ.
продолжение...
