ТОРА (9) - Лекция №4 - Хорошая схема БД - Сохранение ФЗ: различия между версиями
ILobster (обсуждение | вклад) |
ILobster (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 188: | Строка 188: | ||
: 1) построить условно-неизбыточное покрытие (УНП), взять {{Формула|f=H = \varnothing}}; | : 1) построить условно-неизбыточное покрытие (УНП), взять {{Формула|f=H = \varnothing}}; | ||
: 2) каждую ФЗ из УНП | : 2) каждую ФЗ из УНП разбить на совокупность ФЗ с одним атрибутом в правой части, | ||
:: то есть заменить | :: то есть заменить | ||
::: {{Формула|f=X\rightarrow A_1 A_2 ... A_k}} | ::: {{Формула|f=X\rightarrow A_1 A_2 ... A_k}} | ||
Строка 195: | Строка 195: | ||
:: Обозначить полученную ФЗ как {{Формула|f=G}}; | :: Обозначить полученную ФЗ как {{Формула|f=G}}; | ||
: 3) выбрать очередную ФЗ из {{Формула|f=G}}. Найти такую схему отношения {{Формула|f=R_i}}, для которой справедливо включение {{Формула|f=XA\subseteq R_i}}. Если такой схемы отношений не существует, то поместить ФЗ {{Формула|f=X\rightarrow A}} в множество {{Формула|f=H}}; | : 3) выбрать очередную ФЗ из {{Формула|f=G}}. Найти такую схему отношения {{Формула|f=R_i}}, для которой справедливо включение {{Формула|f=XA\subseteq R_i}}. | ||
::Если такой схемы отношений не существует, то поместить ФЗ {{Формула|f=X\rightarrow A}} в множество {{Формула|f=H}}; | |||
: 4) если все ФЗ из {{Формула|f=G}} рассмотрены, то перейти к следующему пункту, иначе к предыдущему; | : 4) если все ФЗ из {{Формула|f=G}} рассмотрены, то перейти к следующему пункту, иначе к предыдущему; |
Текущая версия от 12:40, 20 января 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\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$$ обладает свойством сохранения ФЗ.
продолжение...