кафедра компьютерных и информационных технологий
курс лекций
В настоящем курсе рассматриваются вопросы организации баз данных и знаний. Это важная тема, без основательного знакомства с которой, в наше время, невозможно стать квалифицированным специалистом в сфере информационных технологий.
Основное назначение данного курса – систематическое введение в идеи и методы, используемые в современных системах управления базами данных. В курсе не рассматривается какая-либо одна популярная СУБД; излагаемый материал в равной степени относится к любой современной системе. Как показывает опыт, без знания основ теории баз данных трудно на серьезном уровне работать с конкретными системами, как бы хорошо они не были документированы.
Содержание
ЛЕКЦИЯ 1. Понятие СУБД. Функции СУБД............................................... 7
1.1 Введение..................................................................................................... 7
1.2 Понятие БД и СУБД................................................................................... 7
1.3 Уровни абстракции в СУБД. Функции абстрактных данных.................. 9
1.4 Представления.......................................................................................... 10
1.5 Функции СУБД......................................................................................... 11
1.6 Экспертные системы и базы знаний........................................................ 11
ЛЕКЦИЯ 2. Модели БД.............................................................................. 13
2.1 Обзор ранних (дореляционных) СУБД.................................................. 13
2.2 Системы, основанные на инвертированных списках.............................. 13
2.3 Иерархическая модель............................................................................. 14
2.4 Сетевая модель......................................................................................... 16
2.5 Основные достоинства и недостатки ранних СУБД............................... 17
ЛЕКЦИЯ 3. Реляционная модель и ее характеристики. Целостность в реляционной модели 18
3.1 Представление информации в реляционных БД.................................... 18
3.2 Домены 19
3.3 Отношения. Свойства и виды отношений............................................... 20
3.4 Целостность реляционных данных......................................................... 21
3.5 Потенциальные и первичные ключи....................................................... 22
3.6 Внешние ключи........................................................................................ 22
3.7 Ссылочная целостность........................................................................... 23
3.8 Значения NULL и поддержка ссылочной целостности........................... 24
ЛЕКЦИЯ 4. Реляционная алгебра.............................................................. 25
4.1 Понятие реляционной алгебры............................................................... 25
4.2 Замкнутость в реляционной алгебре....................................................... 25
4.3 Традиционные операции над множествами............................................ 25
4.4 Свойства основных операций реляционной алгебры............................ 27
4.5 Специальные реляционные операции..................................................... 28
ЛЕКЦИЯ 5. Вопросы проектирования БД................................................. 34
5.1 Понятие проектирования БД................................................................... 34
5.2 Функциональные зависимости................................................................. 35
5.3 Тривиальные и нетривиальные зависимости.......................................... 36
5.4 Замыкание множества зависимостей и правила вывода Армстронга... 36
5.5 Неприводимое множество зависимостей................................................. 38
5.6 Нормальные формы – основные понятия............................................... 38
5.7 Декомпозиция без потерь и функциональные зависимости................... 39
5.8 Диаграммы функциональных зависимостей........................................... 40
ЛЕКЦИЯ 6. Проектирование БД. Нормальные формы отношений......... 42
6.1 Первая нормальная форма. Возможные недостатки отношения в 1НФ 42
6.2 Вторая нормальная форма. Возможные недостатки отношения во 2НФ 44
6.3 Третья нормальная форма. Возможные недостатки отношения в 3НФ 45
6.4 Нормальная форма Бойса-Кодда............................................................ 46
ЛЕКЦИЯ 7. Проектирование БД. Нормальные формы отношений (продолжение) 49
7.1 Многозначные зависимости..................................................................... 49
7.2 Четвертая нормальная форма.................................................................. 51
7.3 Зависимости соединения.......................................................................... 51
7.4 Пятая нормальная форма........................................................................ 53
7.5 Итоговая схема процедуры нормализации............................................ 53
ЛЕКЦИЯ 8. Проектирование БД методом сущность-связь. ER-диаграммы 55
8.1 Возникновение семантического моделирования.................................... 55
8.2 Основные понятия метода........................................................................ 55
8.3 Диаграммы ER-экземпляров и ER-типа.................................................. 56
8.4 Правила формирования отношений....................................................... 59
8.5 Методология IDEF1 (самостоятельное изучение).................................. 62
ЛЕКЦИЯ 9. Язык SQL................................................................................ 66
9.1 История создания и развития SQL.......................................................... 66
9.2 Основные понятия SQL............................................................................ 66
9.3 Запросы на чтение данных. Оператор SELECT..................................... 71
9.4 Многотабличные запросы на чтение (объединения).............................. 75
ЛЕКЦИЯ 10. Язык SQL (продолжение)....................................................... 77
10.1 Объединения и стандарт SQL2.............................................................. 77
10.2 Итоговые запросы на чтение. Агрегатные функции............................. 80
10.3 Запросы с группировкой (предложение GROUP BY).......................... 80
10.4 Вложенные запросы............................................................................... 82
ЛЕКЦИЯ 11. Язык SQL. (продолжение)...................................................... 86
11.1 Внесение изменений в базу данных....................................................... 86
11.2 Удаление существующих данных (Оператор DELETE)...................... 87
11.3 Обновление существующих данных (Оператор UPDATE)................. 87
11.4 Определение структуры данных в SQL................................................ 88
11.5 Понятие представления.......................................................................... 91
11.6 Представления в SQL............................................................................. 92
11.7 Системный каталог (самостоятельное изучение).................................. 93
ЛЕКЦИЯ 12. Обеспечение безопасности БД................................................ 99
12.1 Общие положения.................................................................................. 99
12.2 Методы обеспечения безопасности..................................................... 100
12.3 Избирательное управление доступом................................................. 101
12.4 Обязательное управление доступом................................................... 102
12.5 Шифрование данных............................................................................ 102
12.6 Контрольный след выполняемых операций....................................... 102
12.7 Поддержка мер обеспечения безопасности в языке SQL................... 103
12.8 Директивы GRANT и REVOKE.......................................................... 103
12.9 Представления и безопасность............................................................ 105
ЛЕКЦИЯ 13. Физическая организация БД: структуры хранения и методы доступа 106
13.1 Доступ к базе данных........................................................................... 106
13.2 Кластеризация...................................................................................... 108
13.3 Индексирование................................................................................... 108
13.4 Структуры типа Б-дерева.................................................................... 111
13.5 Хеширование........................................................................................ 114
ЛЕКЦИЯ 14. Оптимизация запросов......................................................... 116
14.1 Оптимизация в реляционных СУБД.................................................... 116
14.2 Пример оптимизации реляционного выражения............................... 116
14.3 Обзор процесса оптимизации.............................................................. 117
14.4 Преобразование выражений................................................................ 119
ЛЕКЦИЯ 15. Восстановление после сбоев................................................. 123
15.1 Понятие восстановления системы........................................................ 123
15.2 Транзакции........................................................................................... 123
15.3 Алгоритм восстановления после сбоя системы.................................. 125
15.4 Параллелизм. Проблемы параллелизма............................................. 127
15.5 Понятие блокировки............................................................................ 129
15.6 Решение проблем параллелизма......................................................... 130
15.7 Тупиковые ситуации............................................................................ 132
15.8 Способность к упорядочению............................................................. 133
15.9 Уровни изоляции транзакции.............................................................. 134
15.10 Поддержка в языке SQL.................................................................... 135
ЛЕКЦИЯ 16. Технологии СУБД................................................................. 136
16.1 Распределенные базы данных............................................................. 136
16.2 Принципы функционирования распределенной БД........................... 136
16.3 Системы типа клиент/сервер................................................................ 139
16.4 Серверы баз данных............................................................................ 139
ЛЕКЦИЯ 17. Современные постреляционные модели БД........................ 141
17.1 Системы управления базами данных следующего поколения........... 141
17.2 Ориентация на расширенную реляционную модель.......................... 141
17.3 Объектно-ориентированные СУБД..................................................... 143
1.1 Введение
1.2 Понятие БД и СУБД
1.3 Уровни абстракции в СУБД. Функции абстрактных данных
1.4 Представления
1.5 Функции СУБД
1.6 Экспертные системы и базы знаний
Исторически сложившееся развитие вычислительных систем обусловило необходимость хранения в электронном (машиночитаемом) виде все большего количества информации. Одновременно с совершенствованием и дальнейшим развитием вычислительных систем росли объемы информации, подлежащей обработке и хранению. Сложности, возникшие при решении на практике задач структурированного хранения и эффективной обработки возрастающих объемов информации, стимулировали исследования в соответствующих областях. Задачи хранения и обработки данных были формализованы. Была создана теоретическая база для решения задач такого класса, результатом реализации на практике которой стали системы, предназначенные для организации обработки, хранения и предоставления доступа к информации. Позже такие системы стали называть системами баз данных.
Одновременно с развитием систем баз данных, происходило интенсивное развитие средств вычислительной техники, используемой для работы с большими объемами информации. Вычислительная мощность и, особенно, объемы запоминающих устройств первых вычислительных систем были недостаточны для хранения и обработки информации в объемах, необходимых на практике.