ТОРА (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$$ (из этого следует, что $$Y \subseteq X^+$$ (1) по определению замыкания множества аттрибутов), то эта ФЗ принадежит $$G^+$$

По построению $$G$$ имеет место ФЗ: $$X\rightarrow X^+ - X$$ (2)

Пополним эту ФЗ: $$X\rightarrow (X^+ - X)\bigcup X$$, получится, что $$X\rightarrow X^+$$ (3)

Теперь по первой аксиоме Армстронга из (1) имеем $$X^+\rightarrow Y$$ (4)

Значит, $$X\rightarrow Y \in G^+$$, по третьей аксиоме Армстронга, исходя из (3) и (4).

2)

Докажем обратное, что если $$X\rightarrow Y \in G$$, то $$X\rightarrow Y \in F^+$$

По построению $$G$$ имеем: $$Y = X^+ - X$$ (5)

Для $$F$$ имеем:

$$X\rightarrow X^+$$ (по определению) (6)

$$X^+\rightarrow X^+ - X$$ (1 аксиома Армстронга, так как $$X^+ - X\subseteq X^+$$) (7)

$$X\rightarrow X^+ - X = Y$$ (3 аксимома Армстронга из (6)и (7), и по равенству (5))

В итоге получили $$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$$

A B $$\Pi_{R_1}(r)$$ $$a_1$$ $$b_1$$ $$a_2$$ $$b_1$$

В С $$\Pi_{R_2}(r)$$ $$b_1$$ $$c_1$$ $$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$$

A B $$\Pi_{R_1}(r)$$ $$a_1$$ $$b_1$$ $$a_2$$ $$b_1$$

A С $$\Pi_{R_2}(r)$$ $$a_1$$ $$c_1$$ $$a_2$$ $$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 B C AB $$a$$ $$a$$ $$b_1$$ AC $$a$$ $$b_2$$ $$a$$

A B C AB $$a$$ $$a$$ $$b_1$$ AC $$a$$ $$a$$ $$a$$

Получили строку, сплошь состоящую из $$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$$ обладает свойством соединения без потерь.

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