ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь
Пусть $$F$$ и $$G$$ - два множества ФЗ.
$$G$$ называется покрытием $$F$$, если имеет место равенство $$G^+ = F^+$$
Существуют различные виды покрытий. Но мы рассмотрим только один - условно-неизбыточное покрытие.
Алгоритм построения условно-неизбыточного покрытия
1) если в множестве ФЗ $$F$$ встречаются ФЗ с одинаковой левой частью $$X$$, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим $$G$$;
2) для каждой ФЗ $$X\rightarrow Y$$ из $$G$$ заменить её на $$X\rightarrow X^+ - X$$;
После выполнения 1) и 2) получаем замыкание $$G^+ = F$$
Доказательство
1)
- если ФЗ $$X\rightarrow Y\in F$$, то эта ФЗ принадежит $$G^+$$, а из этого следует, что $$Y \subseteq X^+$$
- По построению G имеет место ФЗ: $$X\rightarrow X^+ - X$$
- Пополним эту ФЗ: $$X\rightarrow (X^+ - X)\bigcup X = X^+$$
- Теперь по первой аксиоме Армстронга имеем $$X^+\rightarrow Y$$
- Значит, $$X\rightarrow Y \in G^+$$, по третьей аксиоме Армстронга.
2)
- $$X\rightarrow Y \in G$$, $$X\rightarrow Y \in F^+$$
- $$Y = X^+ - X$$
- $$X\rightarrow X^+$$ (по определению)
- $$X^+\rightarrow X^+ - X$$ (1 аксиома Армстронга)
- $$X^+\rightarrow X^+ - X = Y$$ (3 аксимома Армстронга)
- $$X^+\rightarrow Y \in F^+$$
Пример
УСО: $$R = (A, B, C)$$
Множество ФЗ: $$F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)$$
1)
- $$G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A$$
2)
- $$A^+ = ABC$$, $$A^+ - A = BC$$
- $$B^+ = BAC$$, $$B^+ - B = AC$$
- $$C^+ = CAB$$, $$C^+ - C = AB$$
Тогда $$G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)$$ будет являться УНП.
Свойства "хорошей" схемы БД
"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
- соединение без потерь;
- сохранение ФЗ;
- каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
- избыточность;
- потенциальная противоречивсть;
- аномалия обновления;
- аномалия удаления.
Соединение без потерь
Чтобы схема БД обладала свойством соединения без потерь, необходимо, чтобы хотя бы одна из таблиц содержала ключ универсальной схемы отношений.
Пусть $$\rho = (R_1 ... R_n)$$ - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения $$r$$ из $$R$$ справедливо равенство: $$r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)$$, где $$\Pi_{R_i}(r)$$ - это проекция экземпляра отношения $$r$$ на множество атрибутов $$R_i$$
Пример БД, не обладающей свойством соединения без потерь
$$R = (A, B, C)$$
$$\rho = (AB, BC) = (R_1, R_2)$$
$$F = (A\rightarrow B)$$
Достаточно привести пример экземпляра $$r$$, для которого равенство не выполняется:
A | B | C | |
---|---|---|---|
$$r$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
|
|
Полученное соединение не будет равняться $$r$$:
A | B | C | |
---|---|---|---|
$$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_1$$ | $$b_1$$ | $$c_2$$ | |
$$a_2$$ | $$b_1$$ | $$c_1$$ | |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.
Пример БД, обладающей свойством соединения без потерь
$$R = (A, B, C)$$
$$\rho = (AB, AC) = (R_1, R_2)$$
$$F = (A\rightarrow B)$$
Возьмём тот же экземпляр:
A | B | C | |
---|---|---|---|
$$r$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
|
|
Полученное соединение будет равняться $$r$$:
A | B | C | |
---|---|---|---|
$$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_1$$ | $$c_2$$ |
Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.
Алгоритм проверки схемы БД на свойство соединения без потерь
$$\rho = (R_1 ... R_n)$$
$$R = (A_1 ... A_n)$$
1) построить таблицу T:
$$A_1$$ | $$A_2$$ | ... | $$A_k$$ | |
---|---|---|---|---|
$$R_1$$ | ||||
$$R_2$$ | ||||
... | ||||
$$R_n$$ |
И заполнить таблицу T по правилу: если $$A_j \in R_i$$, то $$T_{ij}=a$$, иначе $$T_{ij}=b_i$$
2) изменить таблицу T - циклически просматривать ФЗ из $$F$$ в любом порядке, и для очередной ФЗ $$X\rightarrow Y \in F$$ выполнить следующие действия:
- найти в таблице T строки, совпадающие по атрибутам $$X$$ (по левой части);
- если хотя бы в одной такой строке значение атрибута $$A_m \in Y = a$$, то во всех найденных строках присвоить $$A_m = a$$, иначе присвоить $$A_m = b_i$$ (}}i}} - номер одной из найденных строк, $$b_i$$ должно быть одинаково во всех указанных строках);
- выполнить предыдущие два пункта для всех атрибутов $$A_l \in Y$$;
- выполнить предыдущие три пункта для всех ФЗ из $$F$$, циклически их просматривая.
3) алгоритм останавливается, если при очередном просмотре ФЗ из $$F$$:
- не произошло никаких изменений в таблице T;
- какая-нибудь строка в T не стала состоять сплошь из символов $$a$$ (наличие такой строки и говорит о выполнении свойства соединения без потерь).
Пример
Пусть $$R = (A, B, C)$$
$$\rho = (AB, AC) = (R_1, R_2)$$
$$F = (A\rightarrow B)$$
Доказать, что $$\rho$$ обладает свойством соединения без потерь.
1)
A | B | C | |
---|---|---|---|
AB | $$a$$ | $$a$$ | $$b_1$$ |
AC | $$a$$ | $$b_2$$ | $$a$$ |
2)
|
|
Получили строку, сплошь состоящую из $$a$$. Значит $$\rho$$ обладает свойством соединения без потерь.
Другой пример
Пусть $$R = (A, B, C, D, E, F, P, S)$$
$$\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)$$
$$F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)$$
Доказать, что $$\rho$$ обладает свойством соединения без потерь.
1)
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
ACDPS | $$a$$ | $$b_2$$ | $$a$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$a$$ |
BCPS | $$b_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ |
DEF | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$b_4$$ | $$b_4$$ |
2)
первый просмотр:
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$a$$ | $$a$$ |
ACDPS | $$a$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
BCPS | $$b_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ |
DEF | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$b_4$$ | $$b_4$$ |
второй просмотр:
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
ACDPS | $$a$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
BCPS | $$b_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ |
DEF | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$b_4$$ | $$b_4$$ |
Вот и получили строку, сплошь состоящую из $$a$$. Значит $$\rho$$ обладает свойством соединения без потерь.