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

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

Продолжение предыдущей лекции.

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

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

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

Пусть $$\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\bigcup 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$$ ... $$X\rightarrow A_k$$ на $$Y = A_1 ... 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$$ обладает свойством сохранения ФЗ.