Введение
1. Оптимизация и выполнение декларативных сценариев обработки данных 17
1.1 Выполнение точных запросов 17
1.1.1 Языки запросов 18
1.1.2 Оптимизация запросов 19
1.1.3 Многокритериальная оптимизация 21
1.1.4 Параметрическая оптимизация 23
1.2 Нечеткие запросы и приближенное выполнение 24
1.2.1 Языки запросов 24
1.2.2 Приближенное выполнение
1.2.2.1 Понятие качества 29
1.2.2.2 Приближенное выполнение запросов 30
1.2.2.3 Приближенное выполнение операций 30
1.2.3 Оптимизация запросов в расширенных алгебрах 31
1.2.3.1 Алгебраические тождества з
1.2.3.2 Модели стоимости 33
1.3 Адаптивное выполнение запросов 34
1.3.1 Методы адаптивного выполнения запросов 34
1.3.1.1 Потоковое выполнение запросов 36
1.3.1.2 Промежуточная материализация 37
1.3.2 Адаптивные алгоритмы выполнения операций 38
1.4 Системы 39
1.4.1 Распределенные вычисления 39
1.4.1.1 Языки 40
1.4.1.2 Оптимизация 41
1.4.2 Приближенные вычисления 45
1.5 Основные результаты 45
2. Основные понятия 46
2.1 Декларативные языки и расширенная алгебра 46
2.1.1 Функция оценки 47
2.1.2 Множество объектов 49
2.1.3 Q-множества 50
2.1.4 Алгебраические операции
2.1.4.1 Первичная выборка 51
2.1.4.2 Фильтры 52
2.1.4.3 Теоретико-множественные операции 52
2.1.4.4 Соединение 54
2.1.4.5 Агрегирование 54
2.1.4.6 Группирующее соединение
2.1.5 Алгебры 56
2.1.6 Исполнение алгебраических операций 56
2.2 Оптимизация запросов 57
2.2.1 Выражения 57
2.2.2 Алгебраические тождества 58
2.2.3 Запрос и план его выполнения 58
2.2.4 Конфигурация 59
2.2.5 Функция стоимости 59
2.2.6 Модель стоимости 61
2.3 Задачи оптимизации запросов 63
2.3.1 Задача однокритериальной оптимизации 64
2.3.2 Задача многокритериальной оптимизации 64
2.3.3 Задача параметрической оптимизации 64
2.4 Приближенное выполнение 65
2.4.1 Приближенные алгоритмы 65
2.4.2 Вычислительные ресурсы 66
2.4.3 Качество 67
2.4.4 Модель качества 69
2.5 Оптимизация запросов, допускающих приближенное выполнение 70
2.5.1 Задача распределения ресурсов 70
2.5.2 Задача бикритериальной оптимизации 71
2.5.3 Параметрическая задача оптимизации 71
2.5.4 Связь задач 72
2.5.5 Задача оптимизации при ограничениях 72
2.6 Основные результаты 73
3. Распределение ресурсов в плане выполнения запроса 74
3.1 Мотивирующий пример 74
3.2 Вычислительная модель
3.2.1 Дерево плана 76
3.2.2 Качество 77
3.2.3 Уточнение постановки задачи 79
3.2.4 Предположения о функциях качества 80
3.3 Условия оптимальности 81
3.3.1 Критическое поддерево 82
3.3.2 Распределение ресурсов вдоль пути 83
3.3.3 Распределение ресурсов между братьями 86
3.4 Алгоритм распределения ресурсов 87
3.4.1 Алгоритм и структуры данных 87
3.4.2 Горизонтальная гипер-вершина 90
3.4.3 Вертикальная гипер-вершина 91
3.4.4 Вычислительная сложность
3.5 Эксперименты 94
3.6 Основные результаты 97
4. Оптимизация приближенного выполнения запросов 98
4.1 Предварительные рассуждения 98
4.2 Модель: составной сегмент 101
4.3 Алгоритмы
4.3.1 Модель качества плана 102
4.3.2 Доминанта составных сегментов 103
4.3.3 Перечислители: Обход пространства планов
4.3.3.1 Итеративное улучшение 104
4.3.3.2 Рекурсивное построение 104
4.3.4 Сжатие составного сегмента 105
4.4 Эксперименты 105
4.4.1 Нетривиальный оптимальный составной сегмент 106
4.4.2 Итеративное улучшение и рекурсивный спуск 108
4.4.3 Производительность алгоритмов 110
4.4.4 Качество алгоритмов 112
4.5 Основные результаты 112
5. Архитектура системы выполнения запросов 114
5.1 Примеры использования системы 114
5.1.1 Нечеткие запросы 115
5.1.2 Анализ неоднородных данных 117
5.1.3 Извлечение данных
5.2 Основные требования 119
5.3 Архитектура
5.3.1 Окружение системы 120
5.3.2 Оптимизация и исполнение запросов
5.3.2.1 Построение первичного плана 122
5.3.2.2 Оптимизация
5.3.2.2.1 Оптимизация и распределение ресурсов 124
5.3.2.2.2 Оптимизация через построение оптимального составного сегмента 126
5.3.2.3 Исполнение 126
5.4 Расширение системы 127
5.4.1 Трансформации 127
5.4.2 Модели стоимости 128
5.4.3 Модели качества 128
5.4.4 Операции
5.4.4.1 Библиотека операций 130
5.4.4.2 Операции первичной выборки 131
5.4.4.3 Унарные операции 132
5.4.4.4 Бинарные операции 133
5.5 Основные результаты 135
Заключение 136
Библиография
