Лекция №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→ A 2, A 3→ A 4, A 5→ A 6)

Синтез:

1)

УНП=(A 1→ A 2, A 3→ A 4, A 5→ A 6)

2)

U →∅

в УНП нет ФЗ, включающей все атрибуты из U. Поэтому добавляем в УНП тривиальную ФЗ:

УНП=(A 1→ A 2, A 3→ A 4, A 5→ A 6, A 1 A 2 A 3 A 4 A 5 A 6→∅)

3)

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

4)

разбиваем УНП на классы ФЗ:

1. A 1→ A 2, K 1= A 1 A 2
2. A 3→ A 4, K 2= A 3 A 4
3. A 5→ A 6, K 3= A 5 A 6
4. A 1 A 2 A 3 A 4 A 5 A 6→∅, K 4= A 1 A 2 A 3 A 4 A 5 A 6

5)

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

6)

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

7)

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

8)

пропускаем, так как в графе иерархии нет ФЗ, кроме U →∅

9)

ρ =(A 1 A 3 A 5, A 1 A 2, A 3 A 4, A 5 A 6)

10)

1) соединение без потерь

Получили строку, сплошь состоящую из a. Значит, есть соединение без потерь. Запрос на соединение всех четырёх таблиц будет выполняться правильно.

2) сохранение ФЗ:

1-4) H =∅, УНП=(A 1→ A 2, A 3→ A 4, A 5→ 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→ A 2, A 1 - ключ, значит находится в НФБК.

R 3:

R 4= A 3 A 4, A 3→ A 4, A 3 - ключ, значит находится в НФБК.

R 4:

R 4= A 5 A 6, A 5→ A 6, A 5 - ключ, значит находится в НФБК.

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

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

1. ключ в R 1 составной;
2. в ключах R 2, R 3, R 4 используются атрибуты предметной области.

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

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

 

Лекция №9 - Оптимизация запросов

 

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.

 

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

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

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

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

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