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

...начало

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

Пример 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_1 = A_3 A_4$$
3. $$A_5\rightarrow A_6$$, $$K_1 = A_5 A_6$$
4. $$A_1 A_2 A_3 A_4 A_5 A_6\rightarrow\varnothing$$, $$K_1 = 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, видим, что алгоритм синтеза даёт меньшее число схем отношений.

Оптимизация SQL-запросов

Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения.

Шаги оптимизатора:

1. строится логический план выполнения запроса (дерево логических операций);
2. на основе логического плана строится физический план выполнения запроса (дерево физических операций);
3. реализация этого физического плана.

Законы реляционной алгебры

Закон коммутативности декартова произведения отношений

$$R_1\times R_2 = R_2\times R_1$$, здесь и далее $$R_1$$ и $$R_2$$ - экземпляры отношений.

Закон ассоциативности декартова произведения

$$(R_1\times R_2)\times R_3 = R_1\times (R_2\times R_3)$$

Закон каскада проекций

Допустим, $$(a_1 ... a_n)\subseteq (b_1 ... b_n)$$, $${a_i}$$, $${b_i}$$ - $$R$$

тогда $$\Pi_{a_1 ... a_n}(\Pi_{b_1 ... b_n}(R)) = \Pi_{a_1 ... a_n}(R)$$

Закон каскада селекций

Допустим, $$F = f_1\bigwedge f_2$$

тогда $$\sigma_F(R) = \sigma_{f_1}(\sigma_{f_2}(R))$$

Закон перестановки проекции и селекции

1)

Допустим, в условия поиска $$F$$ входят атрибуты только из множества $$a_1 ... a_n$$

тогда $$\Pi_{a_1 ... a_n}(\sigma_F(R)) = \sigma_F(\Pi_{a_1 ... a_n}(R))$$

2)

Допустим, в условия поиска $$F$$ входят атрибуты не только из множества $$a_1 ... a_n$$, но и из $$b_1 ... b_n$$

тогда $$\Pi_{a_1 ... a_n}(\sigma_F(R)) = \Pi_{a_1 ... a_n}(\sigma_F(\Pi_{a_1 ... a_n, b_1 ... b_n}(R)))$$

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