ТОРА (9) - Лекция №4 - Хорошая схема БД - Сохранение ФЗ

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана - студенческое сообщество
Перейти к: навигация, поиск

...начало

Arrow left.png

Свойства "хорошей" схемы БД

Соединение без потерь

Теорема о свойстве соединения без потерь

Пусть $\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$
$R_1 - R_2$ $R_1\bigcap R_2$
$\Pi_{R_1}(r)$ $a_1$ $b_1$
$a_2$ $b_2$
... ...
$a_n$ $b_n$
$R_1\bigcap R_2$ $R_2 - R_1$
$\Pi_{R_2}(r)$ $b_1$ $c_1$
$b_2$ $c_2$
... ...
$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$ обладает свойством сохранения ФЗ.

Arrow right.png

продолжение...