ТОРА (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$

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

A B $\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 B $\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$
BC	$a$	$b_2$	$a$

2)

A B C AB $a$ $a$ $b_1$ BC $a$ $b_2$ $a$

A B C AB $a$ $a$ $b_1$ BC $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$ обладает свойством соединения без потерь.