ТОРА (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$$

$$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$$ обладает свойством сохранения ФЗ.

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