ТОРА (9) - Лекция №4 - Хорошая схема БД - Сохранение ФЗ: различия между версиями
ILobster (обсуждение | вклад) мНет описания правки |
|||
Строка 48: | Строка 48: | ||
{| class="wikitable" | {| class="wikitable" | ||
! {{Формула|f=R_1 - R_2}} !! {{Формула|f=R_1\ | ! {{Формула|f=R_1 - R_2}} !! {{Формула|f=R_1\bigcap R_2}} !! {{Формула|f=R_2 - R_1}} | ||
|- align="center" | |- align="center" | ||
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | | {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | ||
Строка 62: | Строка 62: | ||
| valign="top" | | | valign="top" | | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! {{Формула|f=R_1 - R_2}} !! {{Формула|f=R_1\ | ! !! {{Формула|f=R_1 - R_2}} !! {{Формула|f=R_1\bigcap R_2}} | ||
|- align="center" | |- align="center" | ||
| rowspan="4" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} | | rowspan="4" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} | ||
Строка 76: | Строка 76: | ||
| | | | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! {{Формула|f=R_1\ | ! !! {{Формула|f=R_1\bigcap R_2}} !! {{Формула|f=R_2 - R_1}} | ||
|- align="center" | |- align="center" | ||
| rowspan="4" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | | rowspan="4" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} |
Версия от 01:14, 15 января 2013
Продолжение предыдущей лекции.
Свойства "хорошей" схемы БД
Соединение без потерь
Теорема о свойстве соединения без потерь
Пусть $$\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\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)$$
Алгоритм:
- построить условно-неизбыточное покрытие (УНП), взять $$H = \varnothing$$;
- каждую ФЗ из УНП заменить на совокупность ФЗ с одним атрибутом в правой части, то есть заменить $$X\rightarrow A_1$$ ... $$X\rightarrow A_k$$ на $$Y = A_1 ... A_k$$. Обозначить полученную ФЗ как $$G$$;
- выбрать очередную ФЗ из $$G$$. Найти такую схему отношения $$R_i$$, для которой справедливо включение $$XA\subseteq R_i$$. Если такой схемы отношений не существует, то поместить ФЗ $$X\rightarrow A$$ в множество $$H$$;
- если все ФЗ из $$G$$ рассмотрены, то перейти к следующему пункту, иначе к предыдущему;
- если $$H$$ пусто, то завершить алгоритм. $$\rho$$ обладает свойством сохранения ФЗ. Иначе перейти к следующему пункту;
- просмотреть все ФЗ из $$H$$. Если какая-либо ФЗ $$X\rightarrow A \in H$$ не выводится из множества $$G - H$$, то завершить алгоритм. $$\rho$$ не обладает свойством сохранения ФЗ. Иначе завершить алгоритм, и тогда $$\rho$$ обладает свойством сохранения ФЗ.