ВВЕДЕНИЕ ........................................................ 6

ГЛАВА 1. ОСНОВЫ ТЕОРИИ БАЗ ДАННЫХ .............................. 17
1.1  Этапы развития теории баз данных .......................... 17
1.2  Терминология систем управления базами данных .............. 21
1.3  Этапы проектирования баз данных ........................... 24
1.4  Виды классификации баз данных ............................. 25
1.5  Классификация баз данных по способам организации данных ... 28
     1.5.1  Реляционные модели ................................. 29
     1.5.2  Неструктурированные модели NoSql ................... 31
     1.5.3  Частично структурированная модель NewSQL ........... 33

ГЛАВА 2. ОСНОВЫ ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ .......... 34
2.1  Основные объекты реляционной модели ....................... 35
2.2  Оптимизация реляционной модели. Функциональные
     зависимости ............................................... 37
2.3  Свойства функциональных зависимостей ...................... 39
2.4  Декомпозиция отношений .................................... 42
2.5  Нормальные формы реляционной схемы ........................ 43

ГЛАВА 3. МЕТОДЫ КОНСТРУИРОВАНИЯ РЕЛЯЦИОННЫХ СХЕМ НА ОСНОВЕ
МЕТАДАННЫХ ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ ......................... 50
3.1  Представление функциональных зависимостей с помощью
     графов .................................................... 50
3.2  Преобразование орграфа функциональных зависимостей в
     дерево .................................................... 52
3.3  Построение реляционной модели на основе орграфа
     функциональных зависимостей ............................... 57
3.4  Декомпозиция отношения на основе орграфа простых
     функциональных зависимостей ............................... 63
3.5  Метод получения новых функциональных зависимостей на
     основе декларированных .................................... 69
3.6  Определение ключей по орграфу функциональных
     зависимостей .............................................. 75
3.7  Декомпозиция отношения на основе орграфа составных
     функциональных зависимостей ............................... 80

ГЛАВА 4. ОБЗОР СПОСОБОВ ПРЕДСТАВЛЕНИЯ РАСПРЕДЕЛЕННЫХ СТРУКТУР
И ОЦЕНКА МЕТОДОВ ИХ ОБРАБОТКИ .................................. 83
4.1  Ориентированные, взвешенные графы и деревья ............... 84
4.2  Способы представления графов .............................. 89
4.3  Матричные алгоритмы на графах ............................. 93
4.4  Методы определения трудоемкости алгоритмов ................ 94
4.5  Оптимизация вычислений за счет распараллеливания 
     алгоритмов ................................................ 99

ГЛАВА 5. ОРГАНИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНЫХ И ПАРАЛЛЕЛЬНЫХ 
ВЫЧИСЛЕНИЙ .................................................... 104
5.1  Матричный метод перебора путей в графе ................... 104
5.2  Построение параллельного алгоритма на основе его 
     последовательного аналога с последующей оптимизацией 
     по числу процессоров ..................................... 108
     5.2.1  Матричное преобразование алгоритмов и их 
            оптимизация по числу процессоров .................. 108
     5.2.2  Оптимизация алгоритма по ширине с применением 
            списков смежности ................................. 118
     5.2.3  Оптимизация алгоритма по ширине с применением
            списков следования ................................ 123
5.3  Оптимизация параллельных алгоритмов по времени
     выполнения ............................................... 127
     5.3.1  Оптимизация алгоритма по времени выполнения ....... 129
     5.3.2  Оптимизация алгоритма по времени выполнения с
            применением списков следования .................... 134
5.4  Оптимизация алгоритмов по нескольким параметрам .......... 149

ГЛАВА 6. РАСПАРАЛЛЕЛИВАНИЕ АЛГОРИТМА КОНСТРУИРОВАНИЯ 
РЕЛЯЦИОННЫХ СХЕМ .............................................. 153
6.1  Построение информационного графа алгоритма ............... 153
6.2  Оптимизация информационного графа алгоритма
     нормализации реляционных отношений ....................... 165
     6.2.1  Оптимизация параллельного алгоритма по ширине ..... 165
     6.2.2  Оптимизация параллельного алгоритма по времени .... 169
     6.2.3  Оптимизация параллельного алгоритма по плотности
            вычислений ........................................ 172

ГЛАВА 7. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ЗАПРОСОВ К БАЗАМ ДАННЫХ ..... 176
7.1  Способы хранения таблиц в СУБД MySQL ..................... 177
7.2  Способы распараллеливания запросов в клиент-серверных
     базах данных ............................................. 178

ЗАКЛЮЧЕНИЕ .................................................... 183

ПРИЛОЖЕНИЯ .................................................... 185
П1. Примеры приведения отношений к нормальным формам .......... 185
П2. Примеры вывода ключа отношения ............................ 191
П3. Тестирование методов оптимизации параллельного алгоритма .. 197

СПИСОК ЛИТЕРАТУРЫ ............................................. 203