Диссертация (Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений)
Описание файла
Файл "Диссертация" внутри архива находится в папке "Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений". PDF-файл из архива "Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст из PDF
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиЯрыгина Анна СергеевнаМетоды и средства эффективного выполнения сценариеваналитической обработки данных на основе оптимизации иприближенных вычислений05.13.17 — теоретические основы информатикиДиссертация на соискание ученой степени кандидатафизико-математических наукНаучный руководитель —доктор физико-математических наук, профессор Б.А.НовиковСанкт-Петербург20152ОглавлениеВведение7Актуальность темы исследования .
. . . . . . . . . . . . . . . . . . . .7Цель работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9Основные задачи работы . . . . . . . . . . . . . . . . . . . . . . . . . .9Положения, выносимые на защиту . . . . . . . . . . . . . . . . . . . . .10Методология и методы исследования .
. . . . . . . . . . . . . . . . . .10Степень разработанности темы . . . . . . . . . . . . . . . . . . . . . . .11Научная новизна работы . . . . . . . . . . . . . . . . . . . . . . . . . .11Достоверность и обоснованность . . . . . . . . . . . . . . . . . . . . . .13Апробация работы и публикации . .
. . . . . . . . . . . . . . . . . . . .13Структура диссертации . . . . . . . . . . . . . . . . . . . . . . . . . . .161. Оптимизация и выполнение декларативных сценариев обработки данных171.11.2Выполнение точных запросов . . . . . . . . . . . . . . . .
. . . . .171.1.1Языки запросов . . . . . . . . . . . . . . . . . . . . . . . . .181.1.2Оптимизация запросов . . . . . . . . . . . . . . . . . . . . .191.1.3Многокритериальная оптимизация . . . . . . . . . . . . . .211.1.4Параметрическая оптимизация . . . . . . . . . . . . .
. . .23Нечеткие запросы и приближенное выполнение . . . . . . . . . . .241.2.1Языки запросов . . . . . . . . . . . . . . . . . . . . . . . . .241.2.2Приближенное выполнение . . . . . . . . . . . . . . . . . .291.2.2.1Понятие качества . . . . . . . . . . . . . . . . . . .291.2.2.2Приближенное выполнение запросов . . . .
. . . .301.2.2.3Приближенное выполнение операций . . . . . . .30Оптимизация запросов в расширенных алгебрах . . . . . .311.2.3.1321.2.3Алгебраические тождества . . . . . . . . . . . . .31.2.3.21.3Адаптивное выполнение запросов34Методы адаптивного выполнения запросов . .
. . . . . . .341.3.1.1Потоковое выполнение запросов . . . . . . . . . .361.3.1.2Промежуточная материализация . . . . . . . . . .37Адаптивные алгоритмы выполнения операций . . . . . . .38Системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .391.4.1Распределенные вычисления . . .
. . . . . . . . . . . . . .391.4.1.1Языки . . . . . . . . . . . . . . . . . . . . . . . . .401.4.1.2Оптимизация . . . . . . . . . . . . . . . . . . . . .41Приближенные вычисления . . . . . . . . . . . . . . . . . .45Основные результаты . . . . . . . .
. . . . . . . . . . . . . . . . .451.3.21.4.21.52. Основные понятия2.12.22.333. . . . . . . . . . . . . . . . . .1.3.11.4Модели стоимости . . . . . . . . . . . . . . . . . .46Декларативные языки и расширенная алгебра . . . . . . . . . . .462.1.1Функция оценки . . . . . . . . .
. . . . . . . . . . . . . . .472.1.2Множество объектов . . . . . . . . . . . . . . . . . . . . . .492.1.3Q-множества . . . . . . . . . . . . . . . . . . . . . . . . . .502.1.4Алгебраические операции . . . . . . . . . . . . . . . . . . .512.1.4.1Первичная выборка . . . .
. . . . . . . . . . . . .512.1.4.2Фильтры. . . . . . . . . . . . . . . . . . . . . . .522.1.4.3Теоретико-множественные операции . . . . . . . .522.1.4.4Соединение . . . . . . . . . . . . . . . . . . . . . .542.1.4.5Агрегирование . . . . . . . . . . . . . . . . .
. . .542.1.4.6Группирующее соединение . . . . . . . . . . . . .552.1.5Алгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . .562.1.6Исполнение алгебраических операций . . . . . . . . . . . .56Оптимизация запросов . . . . . . . . . . . .
. . . . . . . . . . . . .572.2.1Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . .572.2.2Алгебраические тождества . . . . . . . . . . . . . . . . . .582.2.3Запрос и план его выполнения . . . . . . . . . . . . . . . .582.2.4Конфигурация . . . . . . . . . . . . . . . . . . . .
. . . . .592.2.5Функция стоимости . . . . . . . . . . . . . . . . . . . . . .592.2.6Модель стоимости . . . . . . . . . . . . . . . . . . . . . . .61Задачи оптимизации запросов . . . . . . . . . . . . . . . . . . . . .6342.42.52.62.3.1Задача однокритериальной оптимизации . . . . . . . . . .642.3.2Задача многокритериальной оптимизации . . . . . . .
. . .642.3.3Задача параметрической оптимизации . . . . . . . . . . . .64Приближенное выполнение . . . . . . . . . . . . . . . . . . . . . .652.4.1Приближенные алгоритмы . . . . . . . . . . . . . . . . . .652.4.2Вычислительные ресурсы . . . . . . . . . . . . . . . .
. . .662.4.3Качество . . . . . . . . . . . . . . . . . . . . . . . . . . . . .672.4.4Модель качества . . . . . . . . . . . . . . . . . . . . . . . .69Оптимизация запросов, допускающих приближенное выполнение702.5.1Задача распределения ресурсов . . . . .
. . . . . . . . . . .702.5.2Задача бикритериальной оптимизации . . . . . . . . . . . .712.5.3Параметрическая задача оптимизации . . . . . . . . . . . .712.5.4Связь задач . . . . . . . . . . . . . . . . . . . . . . . . . . .722.5.5Задача оптимизации при ограничениях . . . . . . . . . . .72Основные результаты . . . . . . . . . .
. . . . . . . . . . . . . . .733. Распределение ресурсов в плане выполнения запроса743.1Мотивирующий пример . . . . . . . . . . . . . . . . . . . . . . . .743.2Вычислительная модель . . . . . . . . . . . . . . . . . . . . . . . .763.2.1Дерево плана . . . . . . . . . . . . . . . . . . . . . . . . . .763.2.2Качество . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .773.2.3Уточнение постановки задачи . . . . . . . . . . . . . . . . .793.2.4Предположения о функциях качества . . . . . . . . . . . .80Условия оптимальности . . . . . . . . . . . . . . . . . . . . . . . .813.3.1Критическое поддерево . . .
. . . . . . . . . . . . . . . . .823.3.2Распределение ресурсов вдоль пути . . . . . . . . . . . . .833.3.3Распределение ресурсов между братьями . . . . . . . . . .86Алгоритм распределения ресурсов . . . . . . . . . . . . . . . . . .873.4.1Алгоритм и структуры данных . . . . . . . . . . . . . . . .873.4.2Горизонтальная гипер-вершина . . . . . . . . .
. . . . . . .903.4.3Вертикальная гипер-вершина . . . . . . . . . . . . . . . . .913.4.4Вычислительная сложность . . . . . . . . . . . . . . . . . .923.33.43.5Эксперименты. . . . . . . . . . . . . . . . . . . . . . . . . . . . .943.6Основные результаты . .
. . . . . . . . . . . . . . . . . . . . . . .9754. Оптимизация приближенного выполнения запросов984.1Предварительные рассуждения . . . . . . . . . . . . . . . . . . . .4.2Модель: составной сегмент . . . . . . . . . . . . . . . . . . . . . . 1014.3Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024.3.1Модель качества плана4.3.2Доминанта составных сегментов .
. . . . . . . . . . . . . . 1034.3.3Перечислители: Обход пространства планов . . . . . . . . . 1034.3.44.44.5. . . . . . . . . . . . . . . . . . . . 1024.3.3.1Итеративное улучшение . . . . . . . . . . . . . . . 1044.3.3.2Рекурсивное построение . . . . . . . . . . . . . . . 104Сжатие составного сегмента .
. . . . . . . . . . . . . . . . . 105Эксперименты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054.4.1Нетривиальный оптимальный составной сегмент . . . . . . 1064.4.2Итеративное улучшение и рекурсивный спуск4.4.3Производительность алгоритмов . . . . . . . . . . . . . . . 1104.4.4Качество алгоритмов . . . . . . . . .
. . . . . . . . . . . . . 112. . . . . . . 108Основные результаты . . . . . . . . . . . . . . . . . . . . . . . . . 1125. Архитектура системы выполнения запросов5.198114Примеры использования системы . . . . . . . . . . . . . . . . . . . 1145.1.1Нечеткие запросы . . . . . . . . . . . . . . . . . . . .
. . . 1155.1.2Анализ неоднородных данных5.1.3Извлечение данных . . . . . . . . . . . . . . . . . . . . . . . 118. . . . . . . . . . . . . . . . 1175.2Основные требования . . . . . . . . . . . . . . . . . . . . . . . . . 1195.3Архитектура . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 1205.3.1Окружение системы . . . . . . . . . . . . . . . . . . . . . . 1205.3.2Оптимизация и исполнение запросов . . . . . . . . . . . . . 1225.3.2.1Построение первичного плана . . . . . . . . . . . . 1225.3.2.2Оптимизация . . . . . . . . . . . . . . . . . . . . . 1225.3.2.2.1Оптимизация и распределение ресурсов . 1245.3.2.2.2Оптимизация через построение оптимального составного сегмента .
