ОГЛАВЛЕНИЕ
Введение
ГЛАВА 1. Конъюнктивные регулярные путевые запросы
1.1. Основные понятия и обозначения .
1.2. Модель данных и язык запросов.
1.2.1. Структура данных.
1.2.2. Язык запросов
1.2.3. Ограничения целостности
1.3. Вычисление запроса как поиск подграфа в графе.
1.4. Методы оптимизации СР3запросов
1.4.1. Индексные структуры
1.4.2. Вычисление при наличии представлений.
1.4.3. Эквивалентность и вложенность запросов.
1.4.4. Усечение запроса с использованием схемы
1.5. Выводы
ГЛАВА 2. Базовые методы вычисления запросов
2.1. Стратегии вычисления запросов
2.1.1. Вычисление элементарного запроса.
2.1.2. Стратегии вычисление СИРС запроса.
2.1.3. Сравнение стратегий .
2.2. Эвристики
2.2.1. Эвристики обхода вершин запроса
2.2.2. Обращение ребер
2.2.3. Порядок обхода исходящих рсбер.
2.2.4. Наложение локальных ограничений
2.2.5. Вычисление запроса с учетом эвристик.
2.3. Декомпозиция запросов.
2.3.1. Разложение СР3 запросов.
2.3.2. Разложение элементарных запросов.
2.4. Выводы.
ГЛАВА 3. Оценка сложности элементарного запроса
3.1. Сложность запроса и меры сложности регулярных языков
3.2. Мера сложности путевого запроса
3.2.1. Определение меры сложности путевого запроса
3.2.2. Вычисление сложности путевого запроса
3.2.3. Свойства меры сложности путевого запроса.
3.3. Оценка сложности элементарного запроса.
3.3.1. Синтаксическая сложность элементарного запроса.
3.3.2. Оценка мощности результата элементарного запроса.
3.3.3. Использование статистики базы данных.
3.4. Результаты тестирования
3.5. Выводы.
ГЛАВА 4. Построение плана вычисления запроса
4.1. Понятие плана вычисления запроса.
4.2. Определение сложности плана
4.2.1. Информативность вершины запроса.
4.2.2. Информативность ребра запроса.
4.2.3. Сложность плана
4.3. Алгоритм построения плана.
4.4. Результаты применения планов
4.5. Выводы
ГЛАВА 5. Архитектура реализованного программного комплекса
5.1. Подсистема вычисления запросов .
5.2. Подсистема хранения данных
5.3. Подсистема оптимизации запросов.
5.3.1. Построение перезаписи элементарного запроса с учетом представлений .
5.3.2. Построение плана вычисления запроса.
5.3.3. Оценка сложности плана
5.4. Выводы
Заключение
СПРСОК ИЛЛЮСТРАЦИЙ
1.1 Алгоритм поиска подграфа в графе
2.1 Алгоритм поиска вершин, достижимых относительно заданного
регулярного языка.
2.2 Построение допустимых образов методом слияния результатов .
2.3 Окрестность вершины запросы.
2.4 Тестовый запрос для оценки эффективности эвристик.
2.5 Декомпозиция запроса
3.1 Построение автомата из автомата А,.
3.2 Зависимость разности хг от р.
3.3 Результаты оценки сложности запроса.
4.1 Выразительные возможности плана.
4.2 Примеры тестовых конъюнктивных запросов
5.1 Архитектура разработанного программного комплекса
5.2 Алгоритм вычисления запроса МаМетайса
5.3 Алгоритм вычисления запроса по заданному плану
МаШетайса
5.4 Алгоритм построения максимальной перезаписи МаетаНса.
5.5 Алгоритм решения линейного языкового уравнения
МаЛетаНса
5.6 Алгоритм построения случайного плана МаМетайса.
5.7 Алгоритм поиска оптимального плана МаМетаса.
5.8 Алгоритм вычисления сложности плана МаШетаЫса
СПИСОК ТАБЛИЦ
1.1 Локальные ограничения.ЗО
2.1 Характеристики тестовых запросов
2.2 Время выполнения в секундах тестовых запросов.
2.3 Среднее время вычисления сек тестовых запросов при различных планах
4.1 Сравнительная эффективность планов вычисления запросов
5 , п 5.
4.2 Сравнительная эффективность планов вычисления запросов 3 0
ВВЕДЕНИЕ
Актуальность
- Київ+380960830922