Диссертация (1149731)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиЯрыгина Анна СергеевнаМетоды и средства эффективного выполнения сценариеваналитической обработки данных на основе оптимизации иприближенных вычислений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Оптимизация через построение оптимального составного сегмента .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации