Оглавление

Лекция №1 - Операции реляционной алгебры 4

Определения 4

Схема отношения 4

Степень схемы отношения 4

Экземпляр отношения 4

Кортеж 4

Схема БД 4

Примеры схем БД 5

Пример "плохой" схемы БД 5

Пример "хорошей" схемы БД 5

Основные операции реляционной алгебры 5

Объединение отношений 5

Пересечение отношений 6

Декартово произведение 6

Проекция 7

Селекция 7

Естественное соединение 8

Лекция №2 - Функциональные зависимости 10

Функциональные зависимости 10

Замыкание множества функциональных зависимостей 10

Аксиомы Армстронга 11

Пример построения множества ФЗ 11

Лемма 12

Замыкание множества атрибутов 12

Алгоритм построения 13

Лекция №3 - Хорошая схема БД - Соединение без потерь 15

Алгоритм построения условно-неизбыточного покрытия 15

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

Пример 16

Свойства "хорошей" схемы БД 16

Соединение без потерь 16

Лекция №4 - Хорошая схема БД - Сохранение ФЗ 21

Свойства "хорошей" схемы БД 21

Соединение без потерь 21

Свойство сохранения ФЗ 23

Лекция №5 - Третья нормальная форма 26

Свойства "хорошей" схемы БД 26

Свойство сохранения ФЗ 26

Ключ схемы отношения 27

Алгоритм построения ключа 27

Пример построения ключа 28

Третья нормальная форма 29

Пример 1 29

Пример 2 31

Лекция №6 - Алгоритм построения хорошей БД 33

Третья нормальная форма 33

Пример аномалий у 3НФ 33

Нормальная форма Бойса-Кодда 34

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

Пример 35

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

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

Пример 37

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

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

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

Пример 1 41

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

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

Пример 1 43

Пример 2 44

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

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

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

Оптимизация формул реляционной алгебры 50

Логический план 50

Лекция №10 - Логический и физический план запроса 54

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

Логический план 54

Физический план 55

Отличие физического плана от логического 57

Лекция №11 - Оценки 60

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

Физический план 60

Лекция №12 - Оценки (продолжение) 64

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

Физический план 64

Лекция №13 - Оценки (продолжение) 68

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

Физический план 68

Лекция №14 - Оценки (продолжение) 72

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

Физический план 72

Лекция №15 - Пример оценки 78

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

Методы соединения таблиц 78

Лекция №1 - Операции реляционной алгебры

Определения

Схема отношения

Это поименованная совокупность атрибутов.

R=(A1,...,An), где Ai - некоторый атрибут из домена отношения.

R=(идентификатор поставщика, адрес, товар, цена)=(A1,A2,A3,A4).

Здесь (A1,A3) - ключ, определяющий запись.

Степень схемы отношения

Это количество атрибутов в схеме.

Для R=(A1,A2,A3,A4) степень равна 4.

Экземпляр отношения

Это конкретная таблица с данной схемой отношения.

R=(идентификатор поставщика, адрес, товар, цена).

Кортеж

Любая одна строка в таблице экземпляра отношения.

Схема БД

A - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

R1,...,Rn - совокупность атрибутов.

Тогда ρ=(R1,...,Rn) называется схемой БД.

Пример:

A=(A1,A2,A3,A4)

и две схемы: R1=(A1,A2) и R2=(A1,A3,A4)

Так как R1⋃R2=A, то ρ=(R1,R2).

Примеры схем БД

Пример "плохой" схемы БД

Пусть A=(идентификатор поставщика, адрес, товар, цена)

и есть одна схема ρ=R1=A

Данная схема БД обладает следующими недостатками (аномалиями):

• избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;

• потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;

• аномалия включения кортежа. В выбранном отношении R1 пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;

• аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.

Первопричиной этих недостатков является то, что R1 не находится в 3НФ

Пример "хорошей" схемы БД

Пусть A=(идентификатор поставщика, адрес, товар, цена)

R1=(идентификатор, адрес)

R2=(товар, цена)

Схема ρ=(R1,R2) находится в 3НФ и не обладает перечисленными выше недостатками.

Основные операции реляционной алгебры

Объединение отношений

R=R1⋃R2

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо R1, либо R2.

Дублирование кортежей не допускается.

Пересечение отношений

R=R1⋂R2

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и R1, и R2

Декартово произведение

R,S - две схемы отношения со степенями k1 и k2

t=R×S

Декартово произведение - это отношение t со степенью k1+k2, кортежи которого получаются конкатенацией кортежей из отношений R и S.

Проекция

t=ΠAi1...Aik(R)

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов Ai1...Aik исходного отношения R.

Селекция

t=σF(R)

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению R и удовлетворяет логическому условию F.

Естественное соединение

t=R⋈S

Определение этой операции следует из способа построения естественного соединения.

Построение естественного соединения:

1) построить декартово произведение R×S

2) выбрать из этого произведения кортежи по условию R.Ai1=S.Ai1...R.Aik=S.Aik, где Ai...Ak - общие атрибуты в схемах отношений R и S (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

3) удалить из полученного отношения S.Ai1...S.Aik, потому что они будут дублирующими.

Лекция №2 - Функциональные зависимости

Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.

Функциональные зависимости

Пусть R=(A1...An) является функциональной схемой отношения и X, Y - некоторые подмножества атрибутов этой схемы. Говорят, что X функционально определяет Y (X→Y), если в любом экземпляре отношения со схемой R не существует двух кортежей, совпадающих по подмножеству X и не совпадающих по подмножеству Y

Иначе говоря, если два кортежа совпадают по X, то они должны совпадать и по Y

Например, R=(A1,A2,A3,A4), есть зависимости:

• A1→A2 (1)

• A1A3→A4 (2)

Предположим, что имеет место один экземпляр отношения со схемой R

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

А первая ФЗ (1) не имеет место быть (в третьей строке другой номер дома портит всю картину).

Замыкание множества функциональных зависимостей

Пусть R - универсальная схема отношения, а F - исходное множество функциональных зависимостей на этой схеме. Замыканием F называется всё множество функциональных зависимостей, которое логически следует из F - обозначается как F+

Функциональная зависимость логически следует из F, если её можно вывести (получить) с помощью аксиом Армстронга.

Аксиомы Армстронга

Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.

Аксиомы Армстронга являются надёжными и полными.

Надёжность - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ F

Полнота - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.

Рефлексивность

Если Y⊆X⊆R

то X→Y. Тривиальная аксиома.

Дополнение

Если X→Y и Z⊆R (Z может быть пустым),

тогда X⋃Z→Y⋃Z или XZ→YZ

Транзитивность

Если X→Y, а Y→Z,

то X→Z

Пример построения множества ФЗ

Пусть задана УСО (универсальная схема отношения) R=(A,B,C) и зависимости F=(A→B,B→C)

1. A→A, B→B, C→C, AB→A, AB→B, AC→A, AC→C, BC→B, BC→C, ABC→A, ABC→C, AB→AB, AC→AC, BC→BC, ABC→AB, ABC→AC, ABC→BC, ABC→ABC

2. A→AB (1ФЗ и пополняем A), AC→BC, B→BC (2 ФЗ и пополняем B), AB→AC, AC→ABC, AB→ABC, AB→BC, A→AC

3. A→C (1 и 2 ФЗ), A→ABC

Всё, замыкание (F+) построено. Все перечисленные зависимости образуют замыкание.

Лемма

Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.

Правило объединения

Если X→Y и X→Z, то X→YZ

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

1. X→XY (1 ФЗ и пополняем X);

2. XY→YZ (2 ФЗ и пополняем Y);

3. X→YZ (по аксиоме транзитивности).

Правило декомпозиции

Если X→Y, а Z⊆Y, то X→Z

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

1. X→Y (по условию);

2. Y→Z (по аксиоме рефлексивности);

3. X→Z (по аксиоме транзитивности).

Правило псевдотранзитивности

Если X→Y и WY→Z, то WX→Z

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

1. WX→WY (1 ФЗ и пополняем W);

2. WY→Z (по условию);

3. WX→Z (по аксиоме транзитивности).

Замыкание множества атрибутов

Замыкание F+ может включать в себя очень большое количество ФЗ. Например:

F=(X→A1,X→A2...X→An)