Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

§1.

Основные функции систем управления базами данных (СУБД) . . . . . . . . . . . . .

5

1.1.

Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.

Преимущества использования баз данных . . . . . . . . . . . . . . . . . . . . .

7

1.3.

Функции систем управления базами данных . . . . . . . . . . . . . . . . . . . .

8

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

§2.

Реляционная модель данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.

Структуры данных. Фундаментальные свойства отношений . . . . . . . . . . .

9

2.2.

Целостность данных. Реляционные ключи . . . . . . . . . . . . . . . . . . . . .

10

2.3.

Манипулирование данными . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

§3. Реляционная алгебра Кодда . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

3.1.

Операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Объединение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Пересечение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Разность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

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

16

Сокращение (выборка, ограничение, селекция) . . . . . . . . . . . . . . . . . .

16

Проекция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Соединения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Деление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.2.

Приоритеты операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.3.

Базис алгебры и ства операций . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

Базис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

Свойства операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.4.

Ограничения реляционной алгебры . . . . . . . . . . . . . . . . . . . . . . . . .

22

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

§4.

Реляционное исчисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

4.1.

Исчисление кортежей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

Эквивалентность исчисления кортежей и реляционной алгебры . . . . . . . . .

24

4.2.

Исчисление доменов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

§5. Случаи неполной информации и ω-значения . . . . . . . . . . . . . . . . . . . . . . .

26

5.1.

Концепция трехзначной логики . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

Логические операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

Кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Арифметические операции и операции сравнения . . . . . . . . . . . . . . . .

27

5.2.

ω-значения и домены . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

5.3.

ω-значения и операторы реляционной алгебры . . . . . . . . . . . . . . . . . . .

28

5.4.

ω-значения и агрегирующие функции . . . . . . . . . . . . . . . . . . . . . . .

28

5.5.

Проблема интерпретации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

5.6.

ω-значения и ограничения целостности . . . . . . . . . . . . . . . . . . . . . .

29

Первичные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Внешние ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

§6.

Семантическое проектирование реляционных баз данных на основе ER-модели . . .

30

6.1.

Ограниченность реляционной модели при проектировании баз данных . . . . .

30

6.2.

Общий подход семантического моделирования . . . . . . . . . . . . . . . . . .

30

6.3.

Модель «сущность–связь». ER-диаграмма . . . . . . . . . . . . . . . . . . . . .

31

Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

Диаграмма «сущностей–связей» . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Проектирование базы данных с помощью ER-модели . . . . . . . . . . . . . .

33

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

§7.

Проектирование реляционных баз данных при помощи нормализации . . . . . . . . .

35

7.1.

Жизненный цикл системы баз данных . . . . . . . . . . . . . . . . . . . . . . .

35

7.2.

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

36

Понятие функциональной зависимости . . . . . . . . . . . . . . . . . . . . . .

36

Тривиальные и нетривиальные зависимости . . . . . . . . . . . . . . . . . . .

36

Замыкание множества зависимостей . . . . . . . . . . . . . . . . . . . . . . .

37

Неприводимые множества зависимостей . . . . . . . . . . . . . . . . . . . . .

38

Декомпозиция без потерь и функциональные зависимости . . . . . . . . . . . .

39

Диаграммы функциональных зависимостей . . . . . . . . . . . . . . . . . . .

39

Сохранение независимости в смысле Риссанена . . . . . . . . . . . . . . . . .

40

7.3.

Многозначные зависимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

7.4.

Нормализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

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

42

Первая, вторая и третья нормальные формы . . . . . . . . . . . . . . . . . . .

42

Нормальная форма Бойса–Кодда . . . . . . . . . . . . . . . . . . . . . . . . .

44

Четвертая нормальная форма . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

Зависимости соединения и пятая нормальная форма . . . . . . . . . . . . . . .

45

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

§8.

Основные принципы хранения данных во внешней памяти . . . . . . . . . . . . . . .

47

8.1.

Страничная организация хранения данных . . . . . . . . . . . . . . . . . . . . .

47

8.2.

Управление буферами внутренней памяти . . . . . . . . . . . . . . . . . . . . .

49

8.3.

Простая файловая организация страниц . . . . . . . . . . . . . . . . . . . . . .

50

Неупорядоченный файл . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

Упорядоченный файл . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

8.4.

Индексирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

Индексно-прямой метод доступа . . . . . . . . . . . . . . . . . . . . . . . . .

52

Индексно-последовательный метод доступа . . . . . . . . . . . . . . . . . . .

53

Индекс на основе B+-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

Хэширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

8.5.

Кластеризованные и некластеризованные отношения в Oracle Database . . . . .

56

Индексированные кластеры . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

Хэшированные кластеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

§9. Управление транзакциями и синхронизация в реляционных СУБД . . . .

. . . . . . .

57

9.1.

Понятие транзакции . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

58

9.2.

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

. . . . . . .

60

9.3.

Изолированность транзакций . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

61

9.4.

Синхронизационные блокировки . . . . . . . . . . . . . . . . . . .

. . . . . . .

62

Простые блокировки . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

62

Гранулированные (намеренные) блокировки . . . . . . . . . . . .

. . . . . . .

63

Предикатные блокировки . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

66

Тупиковые ситуации . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

67

9.5.

Метод временных меток . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

68

9.6.

Механизм выделения версий данных . . . . . . . . . . . . . . . . .

. . . . . . .

68

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

69

§10. Журнализация и восстановление в реляционных СУБД . . . . . . . . . .

. . . . . . .

69

10.1. Журнализация и буферизация . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

70

10.2. Индивидуальный откат транзакции . . . . . . . . . . . . . . . . . .

. . . . . . .

71

10.3. Восстановление после мягкого сбоя . . . . . . . . . . . . . . . . .

. . . . . . .

71

10.4. Восстановление после жесткого сбоя . . . . . . . . . . . . . . . . .

. . . . . . .

73

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

73

§11. Выполнение и оптимизация запросов в реляционных СУБД . . . . . . .

. . . . . . .

73

11.1. Процесс оптимизации запроса . . . . . . . . . . . . . . . . . . . .

. . . . . . .

74

Преобразование запроса во внутреннюю форму . . . . . . . . . .

. . . . . . .

74

Преобразование запроса в каноническую форму . . . . . . . . . .

. . . . . . .

75

Выбор потенциальных низкоуровневых процедур . . . . . . . . .

. . . . . . .

76

Генерация различных вариантов планов вычисления запроса и выбор плана с ми-

нимальными затратами . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

77

11.2. Низкоуровневая оптимизация операции выборки . . . . . . . . . .

. . . . . . .

77

11.3. Низкоуровневая оптимизация операции соединения . . . . . . . . .

. . . . . . .

78

11.4. Низкоуровневая оптимизация операций проекции, объединения,

пересечения

и разности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

79

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

80