ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь

Алгоритм построение условно-неизбыточного покрытия

1) если в множестве ФЗ <math>F</math> встречаются ФЗ с одинаковой левой частью <math>X</math>, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим <math>G</math>;

2) для каждой ФЗ <math>X\rightarrow Y</math> из <math>G</math> заменить её на <math>X\rightarrow X^+ - X</math>;

После выполнения 1) и 2) получаем замыкание <math>G^+ = F</math>

Доказательство

1. если ФЗ <math>X\rightarrow Y\in F</math>, то эта ФЗ принадежит <math>G^+</math>, а из этого следует, что <math>Y \subseteq X^+</math>

По построению G имеет место ФЗ: <math>X\rightarrow X^+ - X</math>

Пополним эту ФЗ: <math>X\rightarrow (X^+ - X)\bigcup X = X^+</math>

Теперь по первой аксиоме Армстронга имеем <math>X^+\rightarrow Y</math>

Значит, <math>X\rightarrow Y \in G^+</math>, по третьей аксиоме Армстронга.

2. <math>X\rightarrow Y \in G</math>, <math>X\rightarrow Y \in F^+</math>

<math>Y = X^+ - X</math>

<math>X\rightarrow X^+</math> (по определению)

<math>X^+\rightarrow X^+ - X</math> (1 аксиома Армстронга)

<math>X^+\rightarrow X^+ - X = Y</math> (3 аксимома Армстронга)

<math>X^+\rightarrow Y \in F^+</math>

Пример

УСО: <math>R = (A, B, C)</math>

Множество ФЗ: <math>F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)</math>

1) <math>G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A</math>

2)

<math>A^+ = ABC</math>, <math>A^+ - A = BC</math>

<math>B^+ = BAC</math>, <math>B^+ - B = AC</math>

<math>C^+ = CAB</math>, <math>C^+ - C = AB</math>

Тогда <math>G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)</math> будет являться УНП.

Свойства "хорошей" схемы БД

"Хорошая", но не оптимальная. Должна обладать следующими свойствами:

• соединение без потерь;
• сохранение ФЗ;
• каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
  • избыточность;
  • потенциальная противоречивсть;
  • аномалия обновления;
  • аномалия удаления.

Соединение без потерь

Пусть <math>\rho = (R_1 ... R_n)</math> - схема БД. Она будет обладать свойствоем соединения без потерь, если для любого экземпляра отношения <math>r</math> из <math>R</math> справедливо равенство: <math>r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)</math>, где <math>\Pi_{R_i}(r)</math> - это проекция экземпляра отношения <math>r</math> на множество атрибутов <math>R_i</math>

Пример БД, не обладающей свойством соединения без потерь

<math>R = (A, B, C)</math>

<math>\rho = (AB, BC) = (R_1, R_2)</math>

<math>F = (A\rightarrow B)</math>

Достаточно привести пример экземпляра <math>r</math>, для которого равенство не выполняется:

	A	B	C
<math>r</math>	<math>a_1</math>	<math>b_1</math>	<math>c_1</math>
	<math>a_2</math>	<math>b_1</math>	<math>c_2</math>

A B <math>\Pi_{R_1}(r)</math> <math>a_1</math> <math>b_1</math> <math>a_2</math> <math>b_1</math>

A B <math>\Pi_{R_2}(r)</math> <math>b_1</math> <math>c_1</math> <math>b_1</math> <math>c_2</math>

Полученное соединение не будет равняться <math>r</math>:

	A	B	C
<math>\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)</math>	<math>a_1</math>	<math>b_1</math>	<math>c_1</math>
	<math>a_1</math>	<math>b_1</math>	<math>c_2</math>
	<math>a_2</math>	<math>b_1</math>	<math>c_1</math>
	<math>a_2</math>	<math>b_1</math>	<math>c_2</math>

Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.

Пример БД, обладающей свойством соединения без потерь

<math>R = (A, B, C)</math>

<math>\rho = (AB, AC) = (R_1, R_2)</math>

<math>F = (A\rightarrow B)</math>

Возьмём тот же экземпляр:

	A	B	C
<math>r</math>	<math>a_1</math>	<math>b_1</math>	<math>c_1</math>
	<math>a_2</math>	<math>b_1</math>	<math>c_2</math>

A B <math>\Pi_{R_1}(r)</math> <math>a_1</math> <math>b_1</math> <math>a_2</math> <math>b_1</math>

A B <math>\Pi_{R_2}(r)</math> <math>a_1</math> <math>c_1</math> <math>a_2</math> <math>c_2</math>

Полученное соединение будет равняться <math>r</math>:

	A	B	C
<math>\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)</math>	<math>a_1</math>	<math>b_1</math>	<math>c_1</math>
	<math>a_2</math>	<math>b_1</math>	<math>c_2</math>

Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.

Алгоритм проверки схемы БД на свойство соединения без потерь

<math>\rho = (R_1 ... R_n)</math>

<math>R = (A_1 ... A_n)</math>

1) построить таблицу T:

	<math>A_1</math>	<math>A_2</math>	...	<math>A_k</math>
<math>R_1</math>
<math>R_2</math>
...
<math>R_n</math>

И заполнить таблицу T по правилу: если <math>A_j \in R_i</math>, то <math>T_{ij}=a</math>, иначе <math>T_{ij}=b_i</math>

2) изменить таблицу T - циклически просматривать ФЗ из <math>F</math> в любом порядке, и для очередной ФЗ <math>X\rightarrow Y \in F</math> выполнить следующие действия:

• найти в таблице T строки, совпадающие по атрибутам <math>X</math> (по левой части);
• если хотя бы в одной такой строке значение атрибута <math>A_m \in Y = a</math>, то во всех найденных строках присвоить <math>A_m = a</math>, иначе присвоить <math>A_m = b_i</math> (<math>i</math> - номер одной из найденных строк, <math>b_i</math> должно быть одинаково во всех указанных строках);
• выполнить предыдущие два пункта для всех атрибутов <math>A_l \in Y</math>;
• выполнить предыдущие три пункта для всех ФЗ из <math>F</math>, циклически их просматривая.

3) алгоритм останавливается, если при очередном просмотре ФЗ из <math>F</math>:

• не произошло никаких изменений в таблице T;
• какая-нибудь строка в T не стала состоять сплошь из символов <math>a</math> (наличие такой строки и говорит о выполнении свойства соединения без потерь).

Пример

Пусть <math>R = (A, B, C)</math>

<math>\rho = (AB, AC) = (R_1, R_2)</math>

<math>F = (A\rightarrow B)</math>

Доказать, что <math>\rho</math> обладает свойством соединения без потерь.

1)

	A	B	C
AB	<math>a</math>	<math>a</math>	<math>b_1</math>
BC	<math>a</math>	<math>b_2</math>	<math>a</math>

2)

A B C AB <math>a</math> <math>a</math> <math>b_1</math> BC <math>a</math> <math>b_2</math> <math>a</math>

A B C AB <math>a</math> <math>a</math> <math>b_1</math> BC <math>a</math> <math>a</math> <math>a</math>

Получили строку, сплошь состоящую из <math>a</math>. Значит <math>\rho</math> обладает свойством соединения без потерь.

Другой пример

Пусть <math>R = (A, B, C, D, E, F, P, S)</math>

<math>\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)</math>

<math>F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)</math>

Доказать, что <math>\rho</math> обладает свойством соединения без потерь.

1)

	A	B	C	D	E	F	P	S
AB	<math>a</math>	<math>a</math>	<math>b_1</math>	<math>b_1</math>	<math>b_1</math>	<math>b_1</math>	<math>b_1</math>	<math>b_1</math>
ACDPS	<math>a</math>	<math>b_2</math>	<math>a</math>	<math>a</math>	<math>b_2</math>	<math>b_2</math>	<math>a</math>	<math>a</math>
BCPS	<math>b_3</math>	<math>a</math>	<math>a</math>	<math>b_3</math>	<math>b_3</math>	<math>b_3</math>	<math>a</math>	<math>a</math>
DEF	<math>b_4</math>	<math>b_4</math>	<math>b_4</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>b_4</math>	<math>b_4</math>

2)

первый просмотр:

	A	B	C	D	E	F	P	S
AB	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>b_1</math>	<math>b_1</math>	<math>a</math>	<math>a</math>
ACDPS	<math>a</math>	<math>b_2</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>
BCPS	<math>b_3</math>	<math>a</math>	<math>a</math>	<math>b_3</math>	<math>b_3</math>	<math>b_3</math>	<math>a</math>	<math>a</math>
DEF	<math>b_4</math>	<math>b_4</math>	<math>b_4</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>b_4</math>	<math>b_4</math>

второй просмотр:

	A	B	C	D	E	F	P	S
AB	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>
ACDPS	<math>a</math>	<math>b_2</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>a</math>
BCPS	<math>b_3</math>	<math>a</math>	<math>a</math>	<math>b_3</math>	<math>b_3</math>	<math>b_3</math>	<math>a</math>	<math>a</math>
DEF	<math>b_4</math>	<math>b_4</math>	<math>b_4</math>	<math>a</math>	<math>a</math>	<math>a</math>	<math>b_4</math>	<math>b_4</math>

Вот и получили строку, сплошь состоящую из <math>a</math>. Значит <math>\rho</math> обладает свойством соединения без потерь.