пропускаем этот шаг, так как есть ФЗ (даже не одна), включающая все атрибуты из U

3)

уменьшить число атрибутов не удаётся

4)

1 класс: A→B, B→A, K1=AB

2 класс: AC→BD, BC→AD, K2=ABCD

5)

6)

для K2:

способ 1 - как во втором семинаре

можно ли вывести AC→BD∈(BC→AD)+?

(AC)+=AC, BD⊈(AC)+, значит нельзя

можно ли вывести BC→AD∈(AC→BD)+?

(BC)+=BC, AD⊈(BC)+, значит нельзя

способ 2 - вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними.

AC→B

BC→A

выше по иерархии ничего нет, выбираем BC→AD

нет лишних ФЗ, потому...

Лекция №7 - Алгоритм (продолжение)

Алгоритм синтеза "хорошей" БД

Пример

7) редуцирование атрибутов справа ФЗ, расположенной по иерархии выше

вычёркиваем в графе A

8)

нет ФЗ с пустой правой частью, потому шаг пропускаем.

9)

ρ=(AB,BCD)=(R1,R2)

10)

проверяем

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

F=(A→B,B→A,AC→D,BC→D)

Значит, ρ обладает сохранением без потерь.

• сохранение ФЗ

1-4)

H=∅, УНП=(A→B,B→A,AC→BD,BC→AD)

H=(AC→BD,BC→A)

5)

H≠∅

6)

выполняется ли AC→BD∈(A→B,B→A,BC→D)+?

(AC)+=ACBD, BD⊂(AC)+

выполняется ли BC→A∈(A→B,B→A,BC→D)+?

(BC)+=BCAD, A⊂(BC)+

значит, ρ обладает сохранением ФЗ.

На практике, частно пренебрегают свойством сохранения ФЗ, если в БД вводятся правильные данные - не надо проверять, противоречат ли эти данные исходной ФЗ.

Таким образом, ρ обладает:

• обладает соединением без потерь;

• обладает сохранением ФЗ;

• точно находится в 3НФ.

Но мы всё равно проверим, находятся ли R1 и R2 в 3НФ Бойса-Кодда:

R1=AB:

A→B, B→A

здесь A - ключ и B - ключ.

значит, находится в НФ.

R2=BCD:

BC→D

BC - ключ.

значит, находится в НФ.

Преимущество и недостатки алгоритма

Преимущество

Алгоритм определяет стандартную (математическую) процедуру построения схемы БД.

Недостатки

• очень трудно определить всё множество ФЗ, а алгоритм критичен к набору этих ФЗ. В приципе, надо строить абстрактный экземпляр отношений (семинар №2), но надо знать и предметную область;

• при увеличении числа ФЗ возможно увеличение сложности вычисления алгоритма.

Эти недостатки сдерживают применение алгоритма на практике.

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

Кроме алгоритма есть практические приёмы нормализации схемы отношений.

Нормальные формы

1НФ

Отношение находится в 1НФ, если все его атрибуты атомарны, то есть ни один из его атрибутов нельзя разделить на более простые атрибуты, которые соответствуют каким-то другим свойствам описываемой сущности.

Также схема отношений находится в 1НФ, если не содержит таблицу или вектор в явном виде. Поэтому, если таблица скрыта в объекте, то схема будет в 1НФ.

Ясно, что отношение, находящееся в 1НФ, также может обладать избыточностью. Для её устранения предназначена вторая нормальная форма.

2НФ

Отношение находится во второй нормальной форме (сокращённо 2НФ) тогда и только тогда, когда оно находится в первой нормальной форме и каждый его неключевой атрибут неприводимо зависим от первичного ключа.

Схема отношений находится в 2НФ, если не существует ключа X, подмножества атрибутов Y⊂X и непервичного атрибута H, для которых выполняются условия:

• X→Y;

• Y→H;

• Y↛X.

A1→Ai...Aj

X=A1A2, Y=A1⊂X, H∈(Ai...Aj):

1) X→Y, так как A1A2→A1

2) Y→H, так как A1→Ai...Aj

3) Y↛X, так как A+1=A1Ai...Aj, X⊈Y+

3НФ

Подробнее на лекции №5.

A2→Ai...Aj

X=A1, Y=A2, H∈(Ai...Aj):

1) X→Y, так как A1→A2

2) Y→H, так как A2→Ai...Aj

3) Y↛X, так как A+2=A2Ai...Aj, X=A1∉Y+

Пример 1

R - схема отношения "Сотрудники".

ФЗ:

A1A5→A2A3A4

A1→A2A3A4

A3→A4

Покажем, что эта схема не находится в 2НФ:

Можно найти ключ X=A1A5, Y=A1⊂X, H∉Y, H∈(A2,A3,A4):

1) X→Y

2) Y→H

3) Y↛X

R1 тоже не находится во 2НФ, потому что X=A1, Y=A3, H=A4:

1) X→Y

2) Y→H

3) Y↛X

Предположим, вдруг оказалось, что сотрудник может занимать несколько должностей, и ещё теперь в таблице надо хранить сведения о заказе. В этом случае схема преобразуется к следующему виду:

Но анализ показывает, что в этом случае таблицы R1 и R2 не находятся в 2НФ:

R1:

A1→A2, X=A1A3, Y=A1⊂X, H=A2

1) X→Y, так как A1A3→A1

2) Y→H, так как A1→A2

3) Y↛X, так как Y+=A1A2, X⊈Y+

R2:

A5→A6, X=A1A3A5, Y=A5⊂X, H=A6

1) X→Y, так как A1A3A5→A5

2) Y→H, так как A5→A6

3) Y↛X, так как Y+=A5A6, X=A1A3A5⊈Y+

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

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

Пример 1

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

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

1. в ключи R3, R1 и R4 входят атрибуты предметной области. При изменении формата табельного номера придётся обновить его в R1 и через CASCADE в R3 и R4. Поэтому всегда желательно иметь синтетические ключи - не связанные с предметной областью (ID);

2. в сущностях R2 и R5 ключи составные. Это увеличивает размер индекса и время поиска по этому индексу.

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

Пример 2

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

U = (табельный номер, ФИО, должность, оклад, номер заказа, сведения о заказе) = (A1,A2,A3,A4,A5,A6)

F=(A1→A2,A3→A4,A5→A6)

Синтез:

1)

УНП=(A1→A2,A3→A4,A5→A6)

2)

U→∅

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

УНП=(A1→A2,A3→A4,A5→A6,A1A2A3A4A5A6→∅)

3)

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

4)

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

1. A1→A2, K1=A1A2

2. A3→A4, K2=A3A4

3. A5→A6, K3=A5A6

4. A1A2A3A4A5A6→∅, K4=A1A2A3A4A5A6

5)

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

6)

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

7)

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

8)

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

9)

ρ=(A1A3A5,A1A2,A3A4,A5A6)

10)

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

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

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

1-4) H=∅, УНП=(A1→A2,A3→A4,A5→A6)

5) H - пусто.

6) обладает сохранением ФЗ. При включении новой записи в таблицу достаточно проверять справедливость тех ФЗ, которые связаны с этой таблицей.

3) каждая схема отношения находится в 3НФ. Вот так.

А находятся ли схемы отношений R1,R2,R3,R4 в нормальной форме Бойса-Кодда?

R1:

R1=A1A3A5, A1A3A5 - ключ, значит находится в НФБК.

R2:

R2=A1A2, A1→A2, A1 - ключ, значит находится в НФБК.

R3:

R4=A3A4, A3→A4, A3 - ключ, значит находится в НФБК.

R4:

R4=A5A6, A5→A6, A5 - ключ, значит находится в НФБК.

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

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

1. ключ в R1 составной;

2. в ключах R2,R3,R4 используются атрибуты предметной области.

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

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

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

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

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

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

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

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

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

3. реализация этого физического плана.

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

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

R1×R2=R2×R1, здесь и далее R1 и R2 - экземпляры отношений.

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

(R1×R2)×R3=R1×(R2×R3)

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

Допустим, (a1...an)⊆(b1...bn), ai, bi - это атрибуты отношения R

тогда Πa1...an(Πb1...bn(R))=Πa1...an(R)

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

Допустим, F=f1∧f2

тогда σF(R)=σf1(σf2(R))

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

1)

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

тогда Πa1...an(σF(R))=σF(Πa1...an(R))

2)

Допустим, в условия поиска F входят атрибуты не только из множества a1...an, но и из b1...bn

тогда Πa1...an(σF(R))=Πa1...an(σF(Πa1...an,b1...bn(R)))

Селекция декартова произведения

Отношение f1 содержит атрибуты только из отношения R1

тогда σf1(R1×R2)=σf1(R1)×R2

Следствие:

пусть F=f1∧f2 и в f1 входят атрибуты R1, а в f2 входят из R2,

тогда σF(R1×R2)=σf1(R1)×σf2(R2)

Доказательство:

σf1∧f2(R1×R2)=σf1(σf2(R1×R2))=σf1(σf2(R2×R1))=

=σf1(R1×σf2(R2))=σf1(R1)×σf2(R2)

Закон перестановки селекции и объединения

σF(R1⋃R2)=σF(R1)⋃σF(R2)

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

σF(R1−R2)=σF(R1)−σF(R2)

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

b1...bn - это атрибуты отношения R1