Введение
ГЛАВА 1. Конъюнктивные регулярные путевые запросы 13
1.1. Основные понятия и обозначения 13
1.2. Модель данных и язык запросов 18
1.2.1. Структура данных 18
1.2.2. Язык запросов 20
1.2.3. Ограничения целостности 27
1.3. Вычисление запроса как поиск подграфа в графе 35
1.4. Методы оптимизации CRPQ-запросов 38
1.4.1. Индексные структуры 38
1.4.2. Вычисление при наличии представлений 42
1.4.3. Эквивалентность и вложенность запросов 44
1.4.4. Усечение запроса с использованием схемы 47
1.5. Выводы 50
ГЛАВА 2. Базовые методы вычисления запросов 52
2.1. Стратегии вычисления запросов 53
2.1.1. Вычисление элементарного запроса 53
2.1.2. Стратегии вычисление CRPQ запроса 54
2.1.3. Сравнение стратегий 56
2.2. Эвристики 58
2.2.1. Эвристики обхода вершин запроса 58
2.2.2. «Обращение» ребер 59
2.2.3. Порядок обхода исходящих ребер 60
2.2.4. Наложение локальных ограничений 61
2.2.5. Вычисление запроса с учетом эвристик 62
2.3. Декомпозиция запросов 64
2.3.1. Разложение CRPQ запросов 64
2.3.2. Разложение элементарных запросов 65
2.4. Выводы 71
ГЛАВА 3. Оценка сложности элементарного запроса 73
3.1. Сложность запроса и меры сложности регулярных языков 73
3.2. Мера сложности путевого запроса 77
3.2.1. Определение меры сложности путевого запроса 77
3.2.2. Вычисление сложности путевого запроса 79
3.2.3. Свойства меры сложности путевого запроса 85
3.3. Оценка сложности элементарного запроса 86
3.3.1. Синтаксическая сложность элементарного запроса 86
3.3.2. Оценка мощности результата элементарного запроса 88
3.3.3. Использование статистики базы данных 90
3.4. Результаты тестирования 94
3.5. Выводы 95
ГЛАВА 4. Построение плана вычисления запроса 97
4.1. Понятие плана вычисления запроса 98
4.2. Определение сложности плана 99
4.2.1. Информативность вершины запроса 100
4.2.2. Информативность ребра запроса 103
4.2.3. Сложность плана 104
4.3. Алгоритм построения плана 105
4.4. Результаты применения планов 106
4.5. Выводы 110
ГЛАВА 5. Архитектура реализованного программного комплекса 111
5.1. Подсистема вычисления запросов 112
5.2. Подсистема хранения данных 114
5.3. Подсистема оптимизации запросов 115
5.3.1. Построение перезаписи элементарного запроса с учетом представлений 116
5.3.2. Построение плана вычисления запроса 118
5.3.3. Оценка сложности плана 120
5.4. Выводы 121
Заключение
