ТОРА (9) - Лекция №6 - Алгоритм построения хорошей БД
Содержание
Третья нормальная форма
Пример аномалий у 3НФ
$R = (A, B, C, D)$ и $F = (A\rightarrow B, B\rightarrow A, AC\rightarrow D)$
Два ключа:
- первый - $AC$:
- $(AC)^+=ACBD = R$
- $A^+=AB\neq R$
- $C^+ = C\neq R$
- второй - $BC$:
- $(BC)^+=BCAD = R$
- $B^+ = BA\neq R$
Покажем, что в этом случае $R$ находится в 3НФ:
1)
- неключевой атрибут $H$, $H = D$
2)
- $Y\rightarrow H$, $H\notin Y$, $Y = AC$
3)
- $X = BC$, $X = AC$
Нельзя подобрать нужную тройку, потому $R$ находится в 3НФ. Однако, отношение всё равно обладает аномалиями:
- избыточности: наименование поставщика повторяется для каждой поставляемой делали;
- противоречивости при изменении наименования поставщика надо изменить его во всех записях, куда оно входит;
- включения: нельзя включить информацию о поставщике, если он ничего не поставляет;
- удаления: при удалении детали удаляется информация о поставщике.
Для устранения этого вводится усиленная 3НФ - Бойса-Кодда.
Нормальная форма Бойса-Кодда
ФЗ $X\rightarrow Y$ является неприводимой, если для любого подмножества $Z\subset X$ выполняется $Z\nrightarrow Y$ или $Z\rightarrow Y\notin F^+$
Пусть есть отношение $R$ и $F$ включает в себя нетривиальные неприводимые ФЗ. Тогда отношение $R$ находится в нормальной форме Бойса-Кодда, если для любого $X\rightarrow Y\in F$ => $X$ - ключ.
Пример:
$R_1 = AB$, $F_1 = (A\rightarrow B, B\rightarrow A)$, $A$ - ключ, $B$ - ключ.
или
$R_2 = ACD$, $F_2 = (AC\rightarrow D)$, $AC$ - ключ.
Алгоритм синтеза "хорошей" БД
Пусть $U$ - универсальная схема отношения (множество всех атрибутов предметной области) и $F$ - множество ФЗ.
Перед выполнением алгоритма можно привести все ФЗ к одному атрибуту в правой части (по свойству декомпозиции) и удалить лишние ФЗ. Но это не обязательно.
Алгоритм:
- построить УНП для $F$;
- если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из $U$, то добавить в УНП тривиальную ФЗ $U\rightarrow\varnothing$. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД;
- привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ);
- разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости $X_i\rightarrow Y_i$ и $X_j\rightarrow Y_j$ будем называть эквивалентными, если $X_iY_i = X_jY_j$. Далее введём обозначение $K_r = X_iY_i$ - множество атрибутов в левой и правой частях ФЗ $r$-того класса эквивалентности;
- построить граф иерархии полученных на предыдущем шаге классов эквивалентности (если это возможно). Правило построения: $j$-ый узел соединяем снизу с $i$-ым узлом, если $K_j\subset K_i$. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности;
- из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора:
- удалить из класса эквивалентности лишние ФЗ;
- если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части;
- если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) атрибуты справа у ФЗ, расположенных выше в графе иерархии;
- если в результате не удалось выбрать ни одной, то выбрать произвольную;
- редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути:
- пусть $X\rightarrow Y$ - это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше;
- для тривиальной ФЗ $U\rightarrow\varnothing$ атрибуты вычёркиваются слева;
- исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ $U\rightarrow\varnothing$). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся;
- каждую оставшуюся в графе иерархий ФЗ $V\rightarrow W$ заменить на множество $VW$. Получившееся множество схем отношений обозначить как $\rho$;
- для полученной на предыдущем шаге схемы БД проверить:
- обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы $U$ в эту схему;
- обладает ли $\rho$ свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию $X\rightarrow Y\notin\Pi_{R_i}(F)$, для построения новых схем отношений, то есть добавить в $\rho$ $XY$.
После выполнения всех шагов полученная схема $\rho$:
- обладает свойством соединения без потерь;
- обладает свойством сохранения ФЗ;
- находится в 3НФ или НФБК;
- содержит минимальное число схем отношений.
Пример
$U = (поставщик, фирма, деталь, количество) = (A, B, C, D)$
$F = (A\rightarrow B, B\rightarrow A, AC\rightarrow D, BC\rightarrow D)$
Строим $\rho$:
1)
- $УНП = (A\rightarrow B, B\rightarrow A, AC\rightarrow BD, BC\rightarrow AD)$
2)
- пропускаем этот шаг, так как есть ФЗ (даже не одна), включающая все атрибуты из $U$
3)
- уменьшить число атрибутов не удаётся
4)
- 1 класс: $A\rightarrow B$, $B\rightarrow A$, $K_1 = AB$
- 2 класс: $AC\rightarrow BD$, $BC\rightarrow AD$, $K_2 = ABCD$
5)
6)
- для $K_2$:
- способ 1 - как во втором семинаре
- можно ли вывести $AC\rightarrow BD\in(BC\rightarrow AD)^+$?
- $(AC)^+=AC$, $BD\nsubseteq(AC)^+$, значит нельзя
- можно ли вывести $BC\rightarrow AD\in(AC\rightarrow BD)^+$?
- $(BC)^+=BC$, $AD\nsubseteq(BC)^+$, значит нельзя
- способ 1 - как во втором семинаре
- способ 2 - вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними.
- $AC\rightarrow B$
- $BC\rightarrow A$
- выше по иерархии ничего нет, выбираем $BC\rightarrow AD$
- способ 2 - вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними.
- нет лишних ФЗ, потому...
- для $K_1$:
продолжение...