ТОРА (9) - Лекция №8 - Алгоритм (продолжение)

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Перейти к навигации Перейти к поиску
Версия для печати больше не поддерживается и может содержать ошибки обработки. Обновите закладки браузера и используйте вместо этого функцию печати браузера по умолчанию.

...начало

Практические приёмы нормализации

Пример 1

Поэтому вновь перестроим схему:

Указанная схема имеет два недостатка:

  1. в ключи $$R_3$$, $$R_1$$ и $$R_4$$ входят атрибуты предметной области. При изменении формата табельного номера придётся обновить его в $$R_1$$ и через CASCADE в $$R_3$$ и $$R_4$$. Поэтому всегда желательно иметь синтетические ключи - не связанные с предметной областью (ID);
  2. в сущностях $$R_2$$ и $$R_5$$ ключи составные. Это увеличивает размер индекса и время поиска по этому индексу.

В силу этого, схему БД предлагается реорганизовать следующим образом (ввести синтетические ключи):

Пример 2

Разработать схему БД для предыдущего примера с применением алгоритма синтеза.

$$U$$ = (табельный номер, ФИО, должность, оклад, номер заказа, сведения о заказе) = $$(A_1, A_2, A_3, A_4, A_5, A_6)$$

$$F = (A_1\rightarrow A_2, A_3\rightarrow A_4, A_5\rightarrow A_6)$$

Синтез:

1)

$$УНП = (A_1\rightarrow A_2, A_3\rightarrow A_4, A_5\rightarrow A_6)$$

2)

$$U\rightarrow\varnothing$$
в УНП нет ФЗ, включающей все атрибуты из $$U$$. Поэтому добавляем в УНП тривиальную ФЗ:
$$УНП = (A_1\rightarrow A_2, A_3\rightarrow A_4, A_5\rightarrow A_6, A_1 A_2 A_3 A_4 A_5 A_6\rightarrow\varnothing)$$

3)

все нетривиальные ФЗ в УНП являются неприводимыми (в левой части один атрибут). Поэтому шаг пропускаем.

4)

разбиваем УНП на классы ФЗ:
  1. $$A_1\rightarrow A_2$$, $$K_1 = A_1 A_2$$
  2. $$A_3\rightarrow A_4$$, $$K_2 = A_3 A_4$$
  3. $$A_5\rightarrow A_6$$, $$K_3 = A_5 A_6$$
  4. $$A_1 A_2 A_3 A_4 A_5 A_6\rightarrow\varnothing$$, $$K_4 = A_1 A_2 A_3 A_4 A_5 A_6$$

5)

строим граф иерархии:

6)

пропускаем, так как в каждом классе только одна ФЗ.

7)

выполняем редуцирование атрибутов ФЗ:

8)

пропускаем, так как в графе иерархии нет ФЗ, кроме $$U\rightarrow\varnothing$$

9)

$$\rho = (A_1 A_3 A_5, A_1 A_2, A_3 A_4, A_5 A_6)$$

10)

1) соединение без потерь
$$A_1$$ $$A_2$$ $$A_3$$ $$A_4$$ $$A_5$$ $$A_6$$
$$R_1$$ $$a$$ $$b_1$$ $$a$$ $$b_1$$ $$a$$ $$b_1$$
$$R_2$$ $$a$$ $$a$$ $$b_2$$ $$b_2$$ $$b_2$$ $$b_2$$
$$R_3$$ $$b_3$$ $$b_3$$ $$a$$ $$a$$ $$b_3$$ $$b_3$$
$$R_4$$ $$b_4$$ $$b_4$$ $$b_4$$ $$b_4$$ $$a$$ $$a$$
$$A_1$$ $$A_2$$ $$A_3$$ $$A_4$$ $$A_5$$ $$A_6$$
$$R_1$$ $$a$$ $$a$$ $$a$$ $$a$$ $$a$$ $$a$$
$$R_2$$ $$a$$ $$a$$ $$b_2$$ $$b_2$$ $$b_2$$ $$b_2$$
$$R_3$$ $$b_3$$ $$b_3$$ $$a$$ $$a$$ $$b_3$$ $$b_3$$
$$R_4$$ $$b_4$$ $$b_4$$ $$b_4$$ $$b_4$$ $$a$$ $$a$$
Получили строку, сплошь состоящую из $$a$$. Значит, есть соединение без потерь. Запрос на соединение всех четырёх таблиц будет выполняться правильно.
2) сохранение ФЗ:
1-4) $$H = \varnothing$$, $$УНП = (A_1\rightarrow A_2, A_3\rightarrow A_4, A_5\rightarrow A_6)$$
5) $$H$$ - пусто.
6) обладает сохранением ФЗ. При включении новой записи в таблицу достаточно проверять справедливость тех ФЗ, которые связаны с этой таблицей.
3) каждая схема отношения находится в 3НФ. Вот так.

А находятся ли схемы отношений $$R_1, R_2, R_3, R_4$$ в нормальной форме Бойса-Кодда?

$$R_1$$:

$$R_1 = A_1 A_3 A_5$$, $$A_1 A_3 A_5$$ - ключ, значит находится в НФБК.

$$R_2$$:

$$R_2 = A_1 A_2$$, $$A_1\rightarrow A_2$$, $$A_1$$ - ключ, значит находится в НФБК.

$$R_3$$:

$$R_4 = A_3 A_4$$, $$A_3\rightarrow A_4$$, $$A_3$$ - ключ, значит находится в НФБК.

$$R_4$$:

$$R_4 = A_5 A_6$$, $$A_5\rightarrow A_6$$, $$A_5$$ - ключ, значит находится в НФБК.

В конце концов, получаем такую схему БД:

Но у неё тоже есть недостатки:

  1. ключ в $$R_1$$ составной;
  2. в ключах $$R_2, R_3, R_4$$ используются атрибуты предметной области.

Перестроим схему с синтетическими ключами:

Сравнивая результаты Примера 1 и Примера 2, видим, что алгоритм синтеза даёт меньшее число схем отношений.