Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Ярыгина Анна Сергеевна

• Ярыгина Анна Сергеевна
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Ярыгина Анна Сергеевна

Цель работы

Основные задачи работы

Положения, выносимые на защиту

Методология и методы исследования

Степень разработанности темы..............................................И

Научная новизна работы

Достоверность и обоснованность

Апробация работы и публикации

Структура диссертации

1. Оптимизация и выполнение декларативных сценариев обработки данных

1.1 Выполнение точных запросов

1.1.1 Языки запросов

1.1.2 Оптимизация запросов

1.1.3 Многокритериальная оптимизация

1.1.4 Параметрическая оптимизация

1.2 Нечеткие запросы и приближенное выполнение

1.2.1 Языки запросов

1.2.2 Приближенное выполнение

1.2.2.1 Понятие качества

1.2.2.2 Приближенное выполнение запросов

1.2.2.3 Приближенное выполнение операций

1.2.3 Оптимизация запросов в расширенных алгебрах

1.2.3.1 Алгебраические тождества

1.2.3.2 Модели стоимости

1.3 Адаптивное выполнение запросов

1.3.1 Методы адаптивного выполнения запросов

1.3.1.1 Потоковое выполнение запросов

1.3.1.2 Промежуточная материализация

1.3.2 Адаптивные алгоритмы выполнения операций

1.4 Системы

1.4.1 Распределенные вычисления

1.4.1.1 Языки

1.4.1.2 Оптимизация

1.4.2 Приближенные вычисления

1.5 Основные результаты

2. Основные понятия

2.1 Декларативные языки и расширенная алгебра

2.1.1 функция оценки

2.1.2 Множество объектов

2.1.3 (^-множества

2.1.4 Алгебраические операции

2.1.4.1 Первичная выборка

2.1.4.2 Фильтры

2.1.4.3 Теоретико-множественные операции

2.1.4.4 Соединение

2.1.4.5 Агрегирование

2.1.4.6 Группирующее соединение

2.1.5 Алгебры

2.1.6 Исполнение алгебраических операций

2.2 Оптимизация запросов

2.2.1 Выражения

2.2.2 Алгебраические тождества

2.2.3 Запрос и план его выполнения

2.2.4 Конфигурация

2.2.5 функция стоимости

2.2.6 Модель стоимости

2.3 Задачи оптимизации запросов

2.3.1 Задача однокритериальной оптимизации

2.3.2 Задача многокритериальной оптимизации

2.3.3 Задача параметрической оптимизации

2.4 Приближенное выполнение

2.4.1 Приближенные алгоритмы

2.4.2 Вычислительные ресурсы

2.4.3 Качество

2.4.4 Модель качества

2.5 Оптимизация запросов, допускающих приближенное выполнение

2.5.1 Задача распределения ресурсов

2.5.2 Задача бикритериальной оптимизации

2.5.3 Параметрическая задача оптимизации

2.5.4 Связь задач

2.5.5 Задача оптимизации при ограничениях

2.6 Основные результаты

3. Распределение ресурсов в плане выполнения запроса

3.1 Мотивирующий пример

3.2 Вычислительная модель

3.2.1 Дерево плана

3.2.2 Качество

3.2.3 Уточнение постановки задачи

3.2.4 Предположения о функциях качества

3.3 Условия оптимальности

3.3.1 Критическое поддерево

3.3.2 Распределение ресурсов вдоль пути

3.3.3 Распределение ресурсов между братьями

3.4 Алгоритм распределения ресурсов

3.4.1 Алгоритм и структуры данных

3.4.2 Горизонтальная гипер-вершина

3.4.3 Вертикальная гипер-вершина

3.4.4 Вычислительная сложность

3.5 Эксперименты

3.6 Основные результаты

4. Оптимизация приближенного выполнения запросов

4.1 Предварительные рассуждения

4.2 Модель: составной сегмент

4.3 Алгоритмы

4.3.1 Модель качества плана

4.3.2 Доминанта составных сегментов

4.3.3 Перечислители: Обход пространства планов

4.3.3.1 Итеративное улучшение

4.3.3.2 Рекурсивное построение

4.3.4 Сжатие составного сегмента

4.4 Эксперименты

4.4.1 Нетривиальный оптимальный составной сегмент

4.4.2 Итеративное улучшение и рекурсивный спуск

4.4.3 Производительность алгоритмов

4.4.4 Качество алгоритмов

4.5 Основные результаты

5. Архитектура системы выполнения запросов

5.1 Примеры использования системы

5.1.1 Нечеткие запросы

5.1.2 Анализ неоднородных данных

5.1.3 Извлечение данных

5.2 Основные требования

5.3 Архитектура

5.3.1 Окружение системы

5.3.2 Оптимизация и исполнение запросов

5.3.2.1 Построение первичного плана

5.3.2.2 Оптимизация

5.3.2.2.1 Оптимизация и распределение ресурсов

5.3.2.2.2 Оптимизация через построение оптимального составного сегмента

5.3.2.3 Исполнение

5.4 Расширение системы

5.4.1 Трансформации

5.4.2 Модели стоимости

5.4.3 Модели качества

5.4.4 Операции

5.4.4.1 Библиотека операций

5.4.4.2 Операции первичной выборки

5.4.4.3 Унарные операции

5.4.4.4 Бинарные операции

5.5 Основные результаты

Заключение

Библиография

Введение Актуальность темы исследования

Проблема эффективного анализа больших объемов данных в реальном времени остается актуальной на протяжении десятилетий. Около 10 лет назад Gray указывал [1] на то, что объемы хранимых данных значительно превышают возможности их обработки. В последующие годы эта проблема стала значительно острее. С одной стороны, в дополнение к быстрому росту объемов накопленной относительно статической информации, в частности, в Интернет, стремительно возрастают объемы доступной динамической информации, например, в социальных сетях, и потоков данных, генерируемых разнообразными сенсорами. С другой стороны, возможности обработки данных развиваются медленнее: это относится как к техническим возможностям оборудования и алгоритмам анализа данных, так и к средствам спецификации и программной реализации необходимых вычислений.

В документе [2] детально проработано понятие больших данных (big data) и показана практическая значимость их анализа в различных предметных областях. Многие исследования в области анализа данных концентрируются вокруг этого понятия? которое со временем вобрало в себя более широкий спектр значений. Когда говорят о больших данных, как правило, имеют ввиду не только большие объемы данных, но и их разнообразие и качество, а также необходимость их своевременной обработки. В качестве примеров систем анализа больших данных можно привести описанные в [3-6].

Разнообразие больших данных связано с множеством типов данных, одновременно задействованных в сложном аналитическом сценарии. Информационные ресурсы, различающиеся по типу хранимых данных, таких как структурированные и слабо-структурированные, и характеру доступа к ним, например, файлы, потоки и реляционные СУБД, могут быть использованы в одном про-

цессе обработки данных. Системы анализа данных могут быть неоднородны с точки зрения модели, динамики, надежности и типа данных, а также по типу запросов на их извлечение и анализ. Необходимость одновременного анализа данных, извлеченных из разнородных источников, появляется в различных приложениях и прикладных областях, в том числе при расширенном поиске, персонализации и аналитической обработке.

Высокоуровневые декларативные языки являются эффективным инструментом описания таких сложных аналитических сценариев, поскольку они позволяют скрыть сложность работы в неоднородной среде и организации параллельных вычислений. Системы, интегрирующие в себе разные подходы к анализу данных, как правило, используют промежуточные алгебраические языки, которые в дополнение к базовой выразительности традиционных декларативных языков запросов: фильтрации, теоретико-множественных операций и операций соединения - включают в себя их нечеткие расширения и специализированные операции для определенных классов задач: например, средства анализа естественных языков или изображений [7-13].

Скорость генерации и накопления данных, например в социальных сетях и разнообразными сенсорами, ведет к стремительному увеличению объемов анализируемых данных. Это приводит к необходимости решения вопросов, связанных со скоростью анализа, так как во многом именно рост объемов данных приводит к увеличению времени их обработки.

Необходимость увеличения скорости анализа данных, диктуемая реальностью предметных областей, подразумевает не только увеличение вычислительных мощностей, но и проработку на других уровнях. Возможный подход к решению этой проблемы анализа больших объемов данных также основан на использовании декларативных языков запросов. Подобные языки используются в традиционных системах баз данных на протяжении десятилетий. Они обеспечивают не только возможности высокоуровневой спецификации требуемых вычислений, но и высокую эффективность их выполнения, так как открывают широкие возможности для автоматического выбора наиболее эффективных алгоритмов массовой обработки данных.

Любой сложный аналитический сценарий, например на основе нечеткой модели данных, как правило, оказывается ресурсоемким. Ожидается, что декларативный подход к исполнению таких сценариев анализа данных из раз-

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

При решении задачи современного анализа данных возникает необходимость в приближенном выполнении запросов, поскольку все чаще точные вычисления невозможны или бессмысленны. Растущий спрос на обработку больших объемов данных за ограниченное время, а также современные методы анализа данных на основе подобия вызывают необходимость в приближенных вычислениях. Например, описанные в [14,15] системы поддерживают приближенное параллельное выполнение запросов в реальном времени, предоставляя пользователю статистические гарантии качества неточного результата.

Значительная часть элементов традиционной архитектуры выполнения декларативных запросов, включая компиляцию в промежуточный алгебраический язык, оптимизацию и интерпретацию алгебраического выражения, требует пересмотра в контексте новых моделей данных, классов систем хранения и доступа, и вычислительных архитектур.

Таким образом, современные проблемы анализа больших данных требуют создания методов и средств, обеспечивающих реализацию систем, которые позволят единообразно формулировать запросы к разнородным данным и описывать их обработку; реализуют эффективное выполнение сложных сценариев анализа данных на основе их оптимизации; и будут поддерживать приближенное выполнение запросов в реальном времени, то есть будут обеспечивать предсказуемое и контролируемое время ответа на запрос.

Введение диссертации (часть автореферата) на тему «Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений»

Цель работы

Целью исследования являлась разработка методов оптимизации для приближенного выполнения сценариев нечеткого анализа данных.

Основные задачи работы

Для достижения цели были поставлены и решены следующие задачи:

• Разработать систему понятий и теоретическую модель оптимизации и контролируемого приближенного выполнения нечетких запросов;

•

чества вычислительных ресурсов среди операций в плане приближенного выполнения запроса;

•

запросов, допускающих приближенное выполнение, ориентированные на специфические ограничения на количество вычислительных ресурсов и качество ответа.

Положения, выносимые на защиту

Положения, выносимые на защиту:

мализующую оптимизацию и контролируемое приближенное выполнение декларативных запросов, на основе модели стоимости и качества операций;

раций в плане выполнения запроса и решена задача выбора оптимального распределения;

чества вычислительных ресурсов среди операций в плане выполнения запроса на основе моделей качества;

•

тированные на специфические в контексте приближенного выполнения, ограничения на количество вычислительных ресурсов и качество ответа.

Методология и методы исследования

Объектом исследования являлась совокупность моделей, методов, инструментов оптимизации и приближенного выполнения сценариев анализа данных.

и

Предметом исследования являлись задачи распределения ресурсов и би критериальном оптимизации запросов, допускающих контролируемое приближенное выполнение. Методология работы основана на обобщении, индукции и дедукции, математическом моделировании, анализе и синтезе теоретического и практического материала. В работе использовались методы исследования операций; методы теории баз данных; методы теории алгоритмов; принципы построения архитектур программных систем; практика программной инженерии.

Степень разработанности темы

Следующие аспекты темы были проработаны исследовательским сообществом к моменту начала работы над темой диссертации. Алгоритмы контролируемого приближенного выполнения отдельных задач анализа данных и ограниченных классов запросов описаны во многих статьях. Методы оптимизации для точного выполнения запросов проработаны в классической теории баз данных. Модели стоимости реляционных операций используются в оптимизаторах запросов современных СУБД. Концепции качества данных исследованы главным образом для структурированных данных. Задачи многокритериальной и параметрической оптимизации исследованы в контексте точного выполнения запросов. Архитектуры, существующих систем оптимизации и приближенного исполнения сценариев анализа данных, поддерживают работу с ограниченными классами запросов и методов приближенного выполнения.

Научная новизна работы

Возможности контролируемого приближенного выполнения запросов в системах анализа данных проработаны нами для сценариев общего вида. В контексте приближенного выполнения запросов возникает ряд новых задач оптимизации, которые были решены в этой работе.

Расширенная модель стоимости операций, предложенная в работе, формализует связь между количеством вычислительных ресурсов и качеством результата приближенных вычислений и лежит в основе последующей оптимизации запросов, допускающих приближенное выполнение.

В работе поставлена и решена задача распределения ограниченного коли-

чества вычислительных ресурсов между операциями в плане приближенного выполнения сложного сценария анализа данных.

Разработано решение специфической бикритериальной задачи оптимизации запросов, допускающих приближенное выполнение, основанное на компактном представлении зависимости оптимального плана от ограничений на исполнение запроса.

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

Теоретическая и практическая значимость работы

Теоретическою ценность для дальнейших исследований представляют обзор и классификация методов и систем оптимизации и приближенного выполнения сценариев анализа данных, алгоритм распределения ресурсов на основе точного теоретического решения задачи и подход к бикритериальной оптимизации запросов, допускающих приближенное исполнение.

Разработанная теоретическая модель и предложенная архитектура системы оптимизации и приближенного выполнения запросов может быть использована для расширения систем анализа данных возможностью контролируемого учета ограничений на вычислительные ресурсы и качество результата. Это позволяет реагировать на потребность аналитиков в своевременном получении результата и в работе в реальном времени.

Разработанные теоретические модели, алгоритмы и экспериментальная среда могут быть использованы для прототипирования прикладных систем анализа больших данных в различных предметных областях, например, при финансовом мониторинге, социологическом и экономическом анализе.

Достоверность и обоснованность

Достоверность и обоснованность результатов работы подтверждается использованием строгого математического аппарата, доказательствами лемм, подтверждением теоретических положений вычислительными экспериментами.

Апробация работы и публикации

Материалы работы докладывались и обсуждались на всероссийских и международных конференциях:

1) 15-ая Восточно-европейская конференция "Advances in Databases and Information Systems"(20-23 сентября 2011 г., Вена, Австрия)

2) Семинар аспирантов в рамках 16-й Восточно-европейской конференции "Advances in Databases and Information Systems"(17-20 сентября 2012 г., Познань, Польша)

3) 16-ая Восточно-европейская конференция "Advances in Databases and Information Systems"(17-20 сентября 2012 г., Познань, Польша)

4) 10-ый Коллоквиум молодых исследователей "Spring Researchers Colloquium on Databases and Information Systems"(30-31 мая 2014 г., Великий Новгород, Россия)

5) 19-ая Восточно-европейская конференция "Advances in Databases and Information Systems"(9-11 сентября 2015 г., Пуатье, Франция)

Полученные результаты прошли апробацию на научном семинаре «Проблемы современных информационно-вычислительных систем» под руководством д. ф.-м. п., проф. В. А. Васенина (25 ноября 2014 года), на семинаре Московской Секции ACM SIGMOD (26 февраля 2015 года), а также неоднократно на семинарах группы исследования методов организации информации и кафедры Информационно-аналитических систем в Санкт-Петербургском Государственном Университете.

Все результаты диссертации опубликованы в 9 научных работах [16-24] и 1 переводе [25]. Из них: 1 публикация [22] представлена в журнале, входящем в

утвержденный приказом Минобрнауки России от 25 июля 2014 г. №793 перечень рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук; 3 статьи [17,19,25] есть в индексах Web of Science и 8 работ [16-20,23-25] опубликованы в рецензируемых зарубежных журналах, включенных в Scopus.

1) Yarygina A., Novikov В. Вi-objective optimization for approximate query evaluation // 19th East European Conference on Advances in Databases and Information Systems and Associated Satellite Events (ADBIS 2015) / Ed. by Tadeusz Morzy, Patrick Valduriez, Ladjel Bellatreche et al.— Communications in Computer and Information Science (CCIS).— Springer Berlin Heidelberg, 2015.^ P. 153^161. (A.C. Ярыгиной принадлежит сведение общей задачи оптимизации к би-критериальной и параметрической, разработка алгоритма, проведение вычислительных экспериментов; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности)

2) Yarygina A., Novikov В. A prototype architecture for approximate realtime query optimization and processing // The Tenth Spring Researchers Colloquium on Databases and Information Systems

2014.— 2014.— P. 24^31. (A.C. Ярыгиной принадлежит детальная проработка архитектуры системы анализа данных; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности)

3) Yarygina A., Novikov В. Optimizing resource allocation for approximate real-time query processing // Computer Science and Information Systems.— 2014.— Vol. 11.— P. 69^88. (A.C. Ярыгиной принадлежит доказательство лемм, идея и реализация алгоритма, проведение вычислительных экспериментов; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности, формальная модель качества)

4) Ярыгина А. Методы выполнения и оптимизации приближенных запросов в неоднородных системах // Программирование.— 2013.—Vol. 39.— Р. 33-44.

5) Yarygina A. Execution and optimization techniques for approximate queries in heterogeneous systems // Programming and Computer Software — 2013.^Vol. 39, no. 6.--P. 309^317.

6) Novikov В., Vassilieva N., Yarygina A. Querying big data // Proceedings of the 13th International Conference on Computer Systems and Technologies.— CompSysTech '12.— New York, NY, USA : ACM, 2012.— P. 1^10. (A.C. Ярыгиной принадлежит проработка алгебраических свойств операций и соотношений между ними; Б.А. Новикову принадлежит концептуальная модель исполнителя декларативных сценариев; Н.С. Васильевой обоснование актуальности задачи в контексте анализа больших данных)

7) Yarygina A., Novikov В. Optimizing the resource allocation for approximate query processing // Advances in Databases and Information Systems / Ed. by Tadeusz Morzy, Theo Harder, Robert Wrembel.— Vol. 186 of Advances in Databases and Information Systems.— Poznan, Poland : Springer Berlin Heidelberg, 2012.— P. 297^308. (A.C. Ярыгиной принадлежит анализ литературы, реализация алгоритма, проведение вычислительных экспериментов; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности, формальная модель качества, идея алгоритма)

8) Dolmatova О., Yarygina A., Novikov В. Cost models for approximate query evaluation algorithms / / Databases and Information Systems. Tenth International Baltic Conference on Databases and Information Systems. Local Proceedings, Materials of Doctoral Consortium. / Ed. by A. Caplinskas, G. Dzemyda, A. Lupeikiene, O. Vasilecas.— Vilnius: Zara, 2012.— P. 20^28. (A.C. Ярыгиной принадлежит разработка расширенных моделей стоимости и качества для ряда операций; О.А. Долматовой принадлежит реализация моделей и проведение экспериментальной оценки; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности)

9) Новиков Б. А., Ярыгина А. С. Задачи оптимизации запросов в распределенной среде неоднородных информационных ресурсов // Математика,

экономика, менеджмент: 100 лет со дня рождения Л.В. Канторовича / Ed. by Иосиф Владимирович Романовский.^ Санкт-Петербургский гос. университет, 2012. 7 9 февраля.^ Р. 57-59. (А.С. Ярыги ной принадлежит общая постановка задачи оптимизации запросов; Б.А. Новикову принадлежит позиционирование задачи в контексте методов исследования операций)

10) Yarygina A., Novikov В., Vassilieva N. Processing complex similarity queries: A systematic approach // ABDIS 2011 Research Communications: Proceedings II of the 5th East-European Conference on Advances in Databases and Information Systems 20 -23 September 2011, Vienna / Ed. by Maria Bielikova, Johann Eder, A Min Tjoa.— Austrian Computer Society, 2011.—September.— P. 212^221. (A.C. Ярыгиiioii принадлежит сравнительный анализ методов синтеза и нормализации, реализация алгоритмов, проведение вычислительных экспериментов; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности, алгебраическая систематизация методов синтеза; Н.С. Васильевой принадлежит реализация методов вычисления оценок подобия изображений)

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

Структура диссертации

Диссертационная работа состоит из введения, 5 глав, заключения и списка литературы. Общий объем диссертации - 149 страниц. Список литературы содержит 100 названий.

Глава 1. Оптимизация и выполнение декларативных сценариев обработки данных

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

Обзор включает в себя анализ работ исследовательского сообщества, посвященных точному выполнению и оптимизации декларативных запросов в традиционных системах баз данных. Особое внимание в этой главе уделено существующим подходам к работе с нечеткими запросами, а также методам приближенного выполнения сценариев анализа данных. Завершает обзор обсуждение современных систем анализа больших данных на основе распределенных и приближенных вычислений.

В обзоре, в силу его ограниченности, не освещены такие важные и смежные темы как распределенное выполнение запросов, алгоритмы точного и приближенного выполнения конкретных алгебраических операций и соответствующие модели стоимости, а также вопросы, связанные с качеством данных и точностью ответа на запрос.

1.1. Выполнение точных запросов

В этом разделе обсуждаются реляционные языки запросов: лежащая в их основе алгебра, а также методы оптимизации и выполнения запросов стали

стартовой точкой в разработке более сложных систем обработки декларативных сценариев анализа данных.

Этой теме посвящено множество более ранних обзоров, например [26], тем не менее, анализ существующих методов выполнения и оптимизации точных запросов в нашей работе носит не только исторических характер, но и позволяет описать контекст, ввести основные понятия, необходимые для дальнейшего изложения.

1.1.1. Языки запросов

В основе реляционных баз данных лежит реляционная алгебра, представляющая собой замкнутую систему операций над отношениями в реляционной модели данных. Первоначальный набор операций был предложен Codd [27]. В процессе развития реляционной теории и практики были предложены новые производные операции. Поскольку многие операции выразимы друг через друга, в составе реляционной алгебры можно выделить несколько вариантов базиса, например предложенный в [28].

Запрос, сформулированный на некотором декларативном языке, например SQL, в реляционной СУБД преобразуется в выражение в терминах операций алгебры. Важно отметить, что нетривиальный исходный запрос может быть представлен в виде алгебраического выражения многими способами, и большинство алгебраических операций реализуется несколькими алгоритмами. Это делает возможным выполнение декларативного запроса многими способами, то есть на основе нескольких планов его выполнения.

В [29] описываются основные этапы выполнения запроса в реляционной базе данных, и выделены следующие модули:

• парсер,

• оптимизатор,

Данная схема используется в большинстве систем выполнения декларативных запросов. Парсер получает на входе запрос на некотором декларативном

языке и преобразует его в выражение на языке реляционного типа. Оптимизатор перебирает пространство эквивалентных планов выполнения запроса и выбирает план, который рассматривается как оптимальный. Генератор кода по выбранному плану строит последовательность команд обращения к исполнителю запроса.

В обзоре [26] обсуждаются основы конструирования систем управления базами данных, включая архитектуру и такие подходы к выполнению запросов, как итеративное вычисление сложных планов, параллельное выполнение и его реализация. В статье также рассматриваются основные алгоритмы выполнения некоторых базовых реляционных операций; детально обсуждаются алгоритмы, реализующие реляционные операции агрегирования и соединения на основе вложенных циклов, сортировки, слияния и хеширования.

Важно отметить, что во многих СУБД при выполнении запроса исполнителем алгебраические операции реализованы как операции над потоками данных. Операция, читает аргументы из отдельных потоков данных и записывает результат в выходной поток по мере его формирования. Такой подход позволяет отказаться от материализации данных, передаваемых между операциями внутри одного запроса. Конечно, реализация операции, например, сортировки, может использовать внутреннюю материализацию промежуточных результатов.

Мы будем различать первичные источники, представляющие собой потоки данных (streams), и потоки (pipelines), возникающие при выполнении запроса. В дальнейшем, если это не будет следовать из контекста, мы будем уточнять, что подразумевается под потоком данных.

1.1.2. Оптимизация запросов

Обсудим детально этап оптимизации, поскольку он является существенным для систем, предоставляющих возможность использования декларативных языков, когда в запросе не специфицирован процесс построения ответа, и оптимизация становится возможной и полезной. В обзоре [29] рассматривается задача оптимизации запросов, архитектура оптимизатора, основанного на моделях стоимости, а также основные алгоритмы поиска наилучшего плана. Обзор классических методов оптимизации запросов также представлен в работе [30].

Оптимизатор выбирает из множества эквивалентных планов выполнения

запроса в некотором смысле наилучший. Эффективность планов может оцениваться разными способами в зависимости от цели оптимизации. Более формально задача оптимизатора состоит в том, чтобы найти план, функция стоимости (например, время выполнения плана или получения первого кортежа ответа) которого минимальна.

В зависимости от характера функции стоимости выделяют оптимизаторы:

• применяющие правила преобразования плана выполнения запроса в эквивалентный ему, которые заведомо приводят к уменьшению значения неявной функции стоимости;

Оптимизаторы, явно использующие функцию стоимости плана, строятся на основе моделей стоимости операций [29,31]. Модели стоимости позволяют получать оценку значения реальной функции стоимости плана выполнения запроса. В обзоре [32] обсуждаются методы построения моделей стоимости операций на основе сбора статистики, и анализируется применимость разных типов гистограмм.

При оптимизации запросов на основе моделей стоимости можно выделить два основных подхода к поиску оптимального плана [29-31]:

— Алгоритм динамического программирования;

— Жадный алгоритм;

— Метод ветвей и границ;

— Метод случайного поиска;

— Генетические алгоритмы.

Подход сверху-вниз позволяет сокращать пространство просматриваемых планов на основе метода ветвей и границ; но эффективные алгоритмы перечисления планов, как правило ограничены внутренними соединениями и простыми

бинарными предикатами. В статье [33] предложен алгоритм перечисления планов выполнения запроса сверху-вниз, преодолевающий эти ограничения. Подход основан на том, что гиперграфы запросов разбиваются на простые графы, с тем, чтобы избежать анализа неэффективных разбиений.

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

Идея генерации оптимизаторов запросов на основе набора трансформаций обсуждалась в ранних работах в этой области [34,35]: такой подход позволяет строить оптимизаторы для систем на основе расширенного набора операций и тождеств на уровне логической (операции) и физической (алгоритмы) алгебры.

1.1.3. Многокритериальная оптимизация

Задача многокритериальной оптимизации запросов рассматривается в [36-39]: среди множества планов выполнения запроса ищутся те, которые минимизирует значение функции стоимости, вычисленной на основе совокупности критериев, таких как время выполнения запроса, денежные затраты, потеря качества в результате.

Задача оптимизации классических 8Р.1 запросов в контексте параллельных вычислений рассматривается в [40]. В работе сформулирована задача оптимизации запроса, в которой строится план оптимизирующий время выполнения запроса при условии ограничений на пропускную способность и производительность. В такой постановке задачи оптимизации не выполняется принцип оптимальности, согласно которому, если два плана отличаются только двумя подпланами, то ниже стоимость того, у которого ниже стоимость подплана. Принцип оптимальности, существенный для алгоритмов оптимизации запросов на основе динамического программирования, не выполняется также и во многих задачах многокритериальной оптимизации запросов.

Авторы [36] предложили два приближенных алгоритма решения задачи многокритериальной оптимизации основанных на принципе приближенной оптимальности, провели анализ их сложности и экспериментально сравнили с точным алгоритмом, основанным на предложенном в [40].

В работе [36] задача оптимизации определяется вектором критериев; функцией стоимости, вычисляемой как взвешенная сумма от значений критериев; и множеством ограничений на значения критериев оптимизации. Множество запросов, рассмотренных в работе, определяется запросами, описываемыми множеством соединяемых таблиц, то есть план выполнения запроса определятся порядком выполнения соединений и алгоритмами вычисления соединений и сканирования таблиц. Предложенные приближенные алгоритмы позволяют строить приближенное решение задачи многокритериальной оптимизации с гарантированным качеством, выбираемым извне. В реализованном прототипе рассмотрены следующие критерии: загрузка ввода-вывода, загрузка процессора, число используемых ядер, загрузка жесткого диска, загрузка буфера, потребление энергии и ошибка кортежей.

В статье [38] представлена среда для параллельного приближенного выполнения запросов на основе случайных выборок. Разработанная система поддерживает приближенное выполнение БРЛА запросов в реальном времени, предоставляя статистические гарантии качества результата. В [38] предложено решение специфической задачи многокритериальной оптимизации запросов по времени выполнения и качеству результата: на первом этапе выбирается оптимальное множество выборок из таблиц, затем строится оптимальная последовательность соединений.

В работах, лежащих в основе этого диссертационного исследования, [16, 17, 19] также рассматривается специфическая задача бикритериальной оптимизации по качеству приближенного результата и количеству вычислительных ресурсов. В отличие от методов, описанных в [38], в этих работах рассматривается более широкий класс сценариев анализа данных и учитываются средства приближенных вычислений, не ограничивающиеся использованием случайных выборок.

Авторы [37] решают специфическую задачу многокритериальной оптимизации, строя аддитивную метрику полезности запроса на основе комбинации стоимости и покрытия запроса.

Задача оптимизации запросов по времени вычислений и потребляемой энергии рассмотрена в [39]: в предложенном подходе оптимизируется агрегированная стоимость запроса, вычисленная на основе этих критериев.

В работах [37-39] рассмотрена задача многокритериальной оптимизации

решается для специфической комбинации критериев, для которой выполняется принцип оптимальности.

В статье [41] разделены задача оптимизации порядка выполнения соединений и многокритериальная оптимизация: на первом этапе строится оптимальное по времени вычислений дерево соединений, а затем операторы соединения назначаются вычислителям, оптимизируя остальные критерии в предположении, что построенный порядок соединения оптимален для всех критериев.

Похожая идея была использована наших работах [16,17,19]: сначала строится план выполнения запроса в предположении о возможности точных вычислений; а затем решается задача распределения фиксированного количества вычислительных ресурсов, с тем, чтобы учесть ограничения на приближенное выполнение.

Авторы [42] предложили алгоритмы оптимизации распределения операторов запроса между параллельными вычислителями, но не решают задачу оптимизации дерева выполнения запроса.

Многокритериальная оптимизация сценариев обработки данных, отличных от традиционных реляционных запросов, рассмотрена в [43,44].

1.1.4. Параметрическая оптимизация

Задача параметрической оптимизации запросов, рассмотренная в [45] состоит в том, чтобы построить в момент оптимизации такое множество планов, в котором для всех возможных значений параметров запроса имеется хотя бы один оптимальный план, который выбирается в момент выполнения запроса. Авторы предлагают подход к решению задачи параметрической оптимизации запросов, основанный на последовательном фиксировании значений неизвестных параметров и решении классической задачи оптимизации.

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

Обобщенный подход к многокритериальной параметрической оптимизации БРЛ запросов предложен в [47]. Пространство параметров может быть разделе-

но на регионы Парето, каждому из которых соответствует доминирующий план исполнения запроса. Родовой алгоритм, предложенный в [47], основан на динамическом программировании: оптимальный план строится на основе своих под-планов. Каждому (под) плану ставится в соответствие регион его релевантности в пространстве параметров, который постепенно сужается по мере сопоставления (под)плана с эквивалентными. Планы с пустыми регионами релевантности исключаются из дальнейшего рассмотрения. Если все функции стоимости кусочно-линейны, то регионы релевантности представляют собой многогранники.

Список литературы диссертационного исследования кандидат наук Ярыгина Анна Сергеевна, 2016 год

Библиография

[1] Gray, J. The next database revolution / Jim Gray // Proceedings of the 2004 ACM SIGMOD international conference on Management of data / ACM.^ 2004. - P. 1-4.

[2] Big data: The next frontier for innovation, competition, and productivity / James Manyika, Michael Chui, Brad Brown et al. — 2011.

[3] Dean, J. Mapreduce: Simplified data processing on large clusters / Jeffrey Dean, Sanjay Ghemawat // OSDI. — USENIX Association, 2004. — P. 137-150.

[4] Asterix: an open source system for big data management and analysis / Sattam Alsubaiee, Yasser Altowim, Hotham Altwaijry et al. // Proceedings of the VLDB Endowment. - 2012. - Vol. 5, no. 12. - P. 1898-1901.

[5] Bruno, N. Continuous cloud-scale query optimization and processing / Nicolas Bruno, Sapna Jain, Jingren Zhou // PVLDB. — 2013. — Vol. 6, no. 11. — P. 961-972.

[6] Scope: parallel databases meet mapreduce / Jingren Zhou, Nicolas Bruno, Ming-Chuan Wu et al. // The VLDB Journal^The International Journal on Very Large Data Bases. - 2012. - Vol. 21, no. 5. - P. 611-636.

[7] Chaudhuri, S. Integrating db and ir technologies: What is the sound of one hand clapping? / Surajit Chaudhuri, Raghu Ramakrishnan, Gerhard Weikum // CIDR. — 2005. — P. 1-12.

[8] A multi-similarity algebra / S. Adali, P. Bonatti, M. L. Sapino, V. S. Subrahmanian // SIGMOD Rec. - 1998. - Vol. 27. - P. 402-413.

[9] Montesi, D. A similarity based relational algebra for web and multimedia data / Danilo Montesi, Alberto Trombetta, Peter A. Dearnley // Inf. Process. Manage. - 2003. - Vol. 39, no. 2. - P. 307-322.

[10] Imprecision and user preferences in multimedia queries: A generic algebraic approach / Paolo Ciaccia, Danilo Montesi, Wilma Penzo, Alberto Trombetta // Foundations of Information and Knowledge Systems. — Springer, 2000. — P. 50-71.

[11] Schmitt, I. Similarity relational calculus and its reduction to a similarity algebra / Ingo Schmitt, Nadine Schulz // FoIKS / Ed. by Dietmar Seipel, Jose Maria Turull Torres. — Vol. 2942 of Lecture Notes in Computer Science. — Springer, 2004. — P. 252-272.

[12] Atnafu, S. Similarity-based algebra for multimedia database systems / Solomon Atnafu, Lionel Brunie, Harald Kosch // ADC.^ 2001.— P. 115— 122.

[13] Budikova, P. Query language for complex similarity queries / Petra Budikovä, Michal Batko, Pavel Zezula // ADBIS / Ed. by Tadeusz Morzy, Theo Härder, Robert Wrembel. — Vol. 7503 of Lecture Notes in Computer Science. — Springer, 2012. — P. 85-98.

[14] Blinkdb: queries with bounded errors and bounded response times on very large data / Sameer Agarwal, Barzan Mozafari, Aurojit Panda et al. // EuroSys / Ed. by Zdenek Hanzalek, Hermann Härtig, Miguel Castro, M. Frans Kaashoek. - ACM, 2013. - P. 29-42.

[15] Sidirourgos, L. Sciborq: Scientific data management with bounds on runtime and quality / Lefteris Sidirourgos, Martin L. Kersten, Peter A. Boncz // CIDR. — 2011. — P. 296-301.

[16] Yarygina, A. A prototype architecture for approximate real-time query optimization and processing / Anna Yarygina, Boris Novikov // The Tenth Spring Researchers Colloquium on Databases and Information Systems 2014. — 2014. — P. 24-31.

[17] Yarygina, A. Optimizing resource allocation for approximate real-time query processing / A. Yarygina, B. Novikov // Computer Science and Information Systems. - 2014. - Vol. 11. - P. 69-88.

[18] Novikov, B. Querying big data / Boris Novikov, Natalia Vassilieva, Anna Yarygina // Proceedings of the 13th International Conference on Computer Systems and Technologies.^ CompSysTech '12.— New York, NY, USA: ACM, 2012. — P. 1-10.

[19] Yarygina, A. Optimizing the resource allocation for approximate query processing / Anna Yarygina, Boris Novikov // Advances in Databases and Information Systems / Ed. by Tadeusz Morzy, Theo Harder, Robert Wrembel. — Vol. 186 of Advances in Databases and Information Systems.^ Poznan, Poland: Springer Berlin Heidelberg, 2012. — P. 297-308.

[20] Dolmatova, O. Cost models for approximate query evaluation algorithms / Oxana Dolmatova, Anna Yarygina, Boris Novikov // Databases and Information Systems. Tenth International Baltic Conference on Databases and Information Systems. Local Proceedings, Materials of Doctoral Consortium. / Ed. by A. Caplinskas, G. Dzemyda, A. Lupeikiene, O. Vasilecas. — Vilnius: Zara, 2012. — P. 20-28.

[21] Новиков, Б. А. Задачи оптимизации запросов в распределенной среде неоднородных информационных ресурсов / Борис Асенович Новиков, Анна Сергеена Ярыгина // Математика, экономика, менеджмент: 100 лет со дня рождения Л.В. Канторовича / Ed. by Иосиф Владимирович Романовский. — Санкт-Петербургский гос. университет, 2012. — 7-9 февраля. — Р. 57-59.

[22] Ярыгина, А. Методы выполнения и оптимизации приближенных запросов в неоднородных системах / А. Ярыгина // Программирование. — 2013. — Vol. 39. - Р. 33-44.

[23] Yarygina, A. Bi-objective optimization for approximate query evaluation / Anna Yarygina, Boris Novikov // 19th East European Conference on Advances in Databases and Information Systems and Associated Satellite Events (ADBIS 2015) / Ed. by Tadeusz Morzy, Patrick Valduriez, Ladjel Bellatreche

et al. — Communications in Computer and Information Science (CCIS).— Springer Berlin Heidelberg, 2015. — P. 153-161.

[24] Yarygina, A. Processing complex similarity queries: A systematic approach / Anna Yarygina, Boris Novikov, Natalia Vassilieva // ABDIS 2011 Research Communications: Proceedings II of the 5th East-European Conference on Advances in Databases and Information Systems 20 - 23 September 2011, Vienna / Ed. by Maria Bielikova, Johann Eder, A Min Tjoa. — Austrian Computer Society, 2011. — September. — P. 212-221.

[25] Yarygina, A. Execution and optimization techniques for approximate queries in heterogeneous systems / A. Yarygina // Programming and Computer Software. - 2013. - Vol. 39, no. 6. - P. 309-317.

[26] Graefe, G. Query evaluation techniques for large databases / Goetz Graefe // ACM Comput. Surv. - 1993. - Vol. 25, no. 2. - P. 73-170.

[27] Codd, E. F. A relational model of data for large shared data banks / E. F. Codd // Commun. ACM. - 1970. - Vol. 13, no. 6. - P. 377-387.

[28] Darwen, H. The third manifesto / Hugh Darwen, C. J. Date // SIGMOD Record. - 1995. - Vol. 24, no. 1. - P. 39-49.

[29] Ioannidis, Y. E. Query optimization / Yannis E. Ioannidis // ACM Comput. Surv. _ 1996. - Vol. 28, no. 1. - P. 121-123.

[30] Kossmann, D. Iterative dynamic programming: a new class of query optimization algorithms / Donald Kossmann, Konrad Stocker // ACM Trans. Database Syst. - 2000. - Vol. 25, no. 1. - P. 43-82.

[31] Steinbrunn, M. Heuristic and randomized optimization for the join ordering problem / Michael Steinbrunn, Guido Moerkotte, Alfons Kemper // VLDB j _ 1997. _ v0i. 6, no. 3. - P. 191-208.

[32] Ioannidis, Y. E. The history of histograms (abridged) / Yannis E. Ioannidis // VLDB. - 2003. - P. 19-30.

[33] Fender, P. Counter strike: generic top-down join enumeration for hypergraphs / Pit Fender, Guido Moerkotte // Proceedings of the VLDB Endowment. - 2013. - Vol. 6, no. 14. - P. 1822-1833.

[34] Graefe, G. The exodus optimizer generator / Goetz Graefe, David J. DeWitt // Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data. - SIGMOD '87. - New York, NY, USA: ACM, 1987. -P. 160-172.

[35] Graefe, G. The volcano optimizer generator: Extensibility and efficient search / Goetz Graefe, William J McKenna // Data Engineering, 1993. Proceedings. Ninth International Conference on / IEEE. — 1993. — p. 209-218.

[36] Trümmer, I. Approximation schemes for many-objective query optimization / Immanuel Trümmer, Christoph Koch // SIGMOD Conference / Ed. by Curtis E. Dyreson, Feifei Li, M. Tamer Özsu. — ACM, 2014. P. 1299-1310.

[37] Havasu: A multi-objective, adaptive query processing framework for web data integration / Subbarao Kambhampati, Ullas Nambiar, Zaiqing Nie, Sreelakshmi Vaddi // ASU CSE / Citeseer. - 2002.

[38] Blink and it's done: interactive queries on very large data / Sameer Agarwal, Anand P Iyer, Aurojit Panda et al. // Proceedings of the VLDB Endowment. - 2012. - Vol. 5, no. 12. - P. 1902-1905.

[39] Xu, Z. Pet: reducing database energy cost via query optimization / Ziehen Xu, Yi-Cheng Tu, Xiaorui Wang // Proceedings of the VLDB Endowment.^ 2012. — Vol. 5, no. 12. — P. 1954-1957.

[40] Ganguly, S. Query optimization for parallel execution / Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy // Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data. SIGMOD '92.— New York, NY, USA: ACM, 1992. - P. 9-18.

[41] Garofalakis, M. N. Multi-dimensional resource scheduling for parallel queries / Minos N Garofalakis, Yannis E Ioannidis // ACM SIGMOD Record / ACM. -Vol. 25. - 1996. - P. 365-376.

[42] Papadimitriou, C. H. Multiobjective query optimization / Christos H Papadimitriou, Mihalis Yannakakis // Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems / ACM. - 2001. - P. 52-59.

[43] Schedule optimization for data processing flows on the cloud / Herald Kllapi, Eva Sitaridi, Manolis M Tsangaris, Yannis Ioannidis // Proceedings of the 2011 ACM SIGMOD International Conference on Management of data / ACM.^ 2011. — p. 289-300.

[44] Optimizing analytic data flows for multiple execution engines / Alkis Simitsis, Kevin Wilkinson, Malu Castellanos, Umeshwar Dayal // Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data / ACM. - 2012. - P. 829-840.

[45] Bizarro, P. Progressive parametric query optimization / Pedro Bizarro, Nicolas Bruno, David J DeWitt // Knowledge and Data Engineering, IEEE Transactions on. - 2009. - Vol. 21, no. 4. - P. 582-594.

[46] Hulgeri, A. Parametric query optimization for linear and piecewise linear cost functions / Arvind Hulgeri, S Sudarshan // Proceedings of the 28th international conference on Very Large Data Bases / VLDB Endowment. — 2002. — P. 167-178.

[47] Trümmer, I. Multi-objective parametric query optimization / Immanuel Trümmer, Christoph Koch // PVLDB. — 2014. — Vol. 8, no. 3. — P. 221-232.

[48] Ranksql: query algebra and optimization for relational top-k queries / Chengkai Li, Kevin Chen-Chuan Chang, Ihab F Ilyas, Sumin Song // Proceedings of the 2005 ACM SIGMOD international conference on Management of data / ACM. - 2005. - P. 131-142.

[49] Fagin, R. Fuzzy queries in multimedia database systems / Ronald Fagin // Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. — PODS '98. — New York, NY, USA: ACM, 1998,- P. 1-10.

[50] Fagin, R. A formula for incorporating weights into scoring rules / Ronald Fagin, Edward L. Wimmers // Theor. Comput. Sei. — 2000. — Vol. 239, no. 2. — P. 309-338.

[51] Kießling, W. Foundations of preferences in database systems / ß

Very Large Data Bases / VLDB Endowment. - 2002. - P. 311-322. ß

ß

conference on Very Large Data Bases / VLDB Endowment. — 2002. — P. 9901001.

[53] Overview and framework for data and information quality research / Stuart E. Madnick, Richard Y. Wang, Yang W. Lee, Hongwei Zhu // J. Data and Information Quality. - 2009. - Vol. 1, no. 1. - P. 2:1-2:22.

[54] Naumann, F. Quality-driven integration of heterogeneous information systems / Felix Naumann, Ulf Leser, Johann Christoph Freytag. — 1999.

[55] Hu, Y. Supporting time-constrained sql queries in oracle / Ying Hu, Seema Sundara, Jagannathan Srinivasan // Proceedings of the 33rd international conference on Very large data bases. — VLDB '07. — VLDB Endowment, 2007. — P. 1207-1218.

[56] Babcock, B. Dynamic sample selection for approximate query processing / Brian Babcock, Surajit Chaudhuri, Gautam Das // Proceedings of the 2003 ACM SIGMOD international conference on Management of data. — SIGMOD '03. — New York, NY, USA: ACM, 2003. — P. 539-550.

[57] Accuracy estimation in approximate query processing / Carlo Dell'Aquila, Francesco Di Tria, Ezio Lefons, Filippo Tangorra // Proceedings of the 14th WSEAS international conference on Computers: part of the 14th WSEAS CSCC multiconference - Volume II. - ICCOMP'IO. - Stevens Point, Wisconsin, USA: World Scientific and Engineering Academy and Society (WSEAS), 2010. — P. 452-458.

[58] Chaudhuri, S. Optimized stratified sampling for approximate query processing / Surajit Chaudhuri, Gautam Das, Vivek Narasayya // ACM Trans. Database Syst. — 2007. — Vol. 32, no. 2.

[59] Scalable approximate query processing with the dbo engine / Chris Jermaine, Subramanian Arumugam, Abhijit Pol, Alin Dobra // ACM Trans. Database Syst. - 2008. - Vol. 33, no. 4. - P. 23:1-23:54.

[60] Tran, T. Approximate and incremental processing of complex queries against the web of data / Thanh Tran, Günter Ladwig, Andreas Wagner // Proceedings of the 22nd international conference on Database and expert systems applications - Volume Part II.— DEXA'll.— Berlin, Heidelberg: Springer-Verlag, 2011.— P. 171-187.

[61] Fagin, R. Optimal aggregation algorithms for middleware / Ronald Fagin, Amnon Lotem, Moni Naor //J. Comput. Syst. Sei. — 2003. — Vol. 66, no. 4. — P. 614-656.

[62] Theobald, M. Top-k query evaluation with probabilistic guarantees / Martin Theobald, Gerhard Weikum, Ralf Schenkel // VLDB / Ed. by Mario A. Nascimento, M. Tamer Ozsu, Donald Kossmann et al. — Morgan Kaufmann, 2004. - P. 648-659.

[63] Anytime measures for top-k algorithms / Benjamin Arai, Gautam Das, Dimitrios Gunopulos, Nick Koudas // VLDB / Ed. by Christoph Koch, Johannes Gehrke, Minos N. Garofalakis et al. - ACM, 2007. - P. 914-925.

[64] Joining the results of heterogeneous search engines / Daniele Braga, Alessandro Campi, Stefano Ceri, Alessandro Raffio // Inf. Syst. — 2008. — Vol. 33, no. 7-8. - P. 658-680.

[65] Schnaitter, K. Depth estimation for ranking query optimization / Karl Schnaitter, Joshua Spiegel, Neoklis Polyzotis // VLDB J. — 2009. — Vol. 18, no. 2. - P. 521-542.

[66] Schnaitter, K. Optimal algorithms for evaluating rank joins in database systems / Karl Schnaitter, Neoklis Polyzotis // ACM Trans. Database Syst. — 2008. - Vol. 35, no. 1. - P. 6:1-6:47.

[67] Streaming multiple aggregations using phantoms / Rui Zhang, Nick Koudas, Beng Chin Ooi et al. // The VLDB Journal. - 2010. - Vol. 19. - P. 557-583.

[68] Jiang, Q. A framework for supporting quality of service requirements in a data stream management system: Ph. D. thesis. — Arlington, TX, USA: University of Texas at Arlington, 2005. - AAI3181900.

[69] Rank-aware query optimization / Ihab F Ilyas, Rahul Shah, Walid G Aref et al. // Proceedings of the 2004 ACM SIGMOD international conference on Management of data / ACM. - 2004. - P. 203-214.

[70] Deshpande, A. Adaptive query processing / Amol Deshpande, Zachary G. Ives, Vijayshankar Raman // Foundations and Trends in Databases. — 2007. — Vol. 1, no. 1. — P. 1-140.

[71] Babu, S. Proactive re-optimization / Shivnath Babu, Pedro Bizarro, David DeWitt // Proceedings of the 2005 ACM SIGMOD international conference on Management of data. — SIGMOD '05. — New York, NY, USA: ACM, 2005. — P. 107-118.

[72] Adaptive join processing in pipelined plans / Kwanchai Eurviriyanukul, Norman W. Paton, Alvaro A. A. Fernandes, Steven J. Lynden // Proceedings of the 13th International Conference on Extending Database Technology. — KD BT TO. — New York, NY, USA: ACM, 2010. — P. 183-194.

[73] Nehme, R. V. Self-tuning query mesh for adaptive multi-route query processing / Rimma V Nehme, Elke A Rundensteiner, Elisa Bertino // Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology / ACM. — 2009. — P. 803-814.

[74] Bobineau, C. A strategy to develop adaptive and interactive query brokers / Christophe Bobineau, Christine Collet, Tuyet-Trinh Vu // 12th International Database Engineering and Applications Symposium (IDEAS 2008), September 10-12, 2008, Coimbra, Portugal. — 2008. — P. 237-247.

[75] Rox: run-time optimization of xqueries / Riham Abdel Kader, Peter Boncz, Stefan Manegold, Maurice van Keulen // Proceedings of the 35th SIGMOD international conference on Management of data. — SIGMOD '09. — New York, NY, USA: ACM, 2009. — P. 615-626.

[76] Robust query processing through progressive optimization / Volker Markl, Vijayshankar Raman, David Simmen et al. // Proceedings of the 2004 ACM SIGMOD international conference on Management of data. — SIGMOD '04. — New York, NY, USA: ACM, 2004. — P. 659-670.

[77] Graefe, G. New algorithms for join and grouping operations / Goetz Graefe // Comput. Sei. - 2012. - Vol. 27, no. 1. - P. 3-27.

[78] Time-completeness trade-offs in record linkage using adaptive query processing / Roald Lengu, Paolo Missier, Alvaro AA Fernandes et al. // Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology / ACM. — 2009. — P. 851-861.

[79] Adaptive rank-aware query optimization in relational databases / Ihab F. Ilyas, Walid G. Aref, Ahmed K. Elmagarmid et al. // ACM Trans. Database Syst. - 2006. - Vol. 31, no. 4. - P. 1257-1304.

[80] Farag, F. Adaptive query processing in data stream management systems under limited memory resources / Fatima Farag, Moustafa A. Hammad, Reda Alhajj // PIKM / Ed. by Anisoara Nica, Aparna S. Yarde. ACM, 2010. — P. 9-16.

[81] The stratosphere platform for big data analytics / Alexander Alexandrov, Rico Bergmann, Stephan Ewen et al. // The VLDB Journal^The International Journal on Very Large Data Bases. — 2014. — Vol. 23, no. 6. — P. 939-964.

[82] Pig latin: a not-so-foreign language for data processing / Christopher Olston, Benjamin Reed, Utkarsh Srivastava et al. // SIGMOD Conference / Ed. by Jason Tsong-Li Wang. - ACM, 2008. - P. 1099-1110.

[83] Hive - a petabyte scale data warehouse using hadoop / Ashish Thusoo, Joydeep Sen Sarma, Namit Jain et al. // ICDE / Ed. by Feifei Li, Mirella M. Moro, Shahram Ghandeharizadeh et al. — IEEE, 2010.^ P. 9961005.

[84] Hyracks: A flexible and extensible foundation for data-intensive computing / Vinayak Borkar, Michael Carey, Raman Grover et al. // Data Engineering

(ICDE), 2011 IEEE 27th International Conference on / IEEE. — 2011. — P. 1151-1162.

[85] Jaql: A scripting language for large scale semistructured data analysis / Kevin S. Beyer, Vuk Ercegovac, Rainer Gemulla et al. // PVLDB. — 2011. — Vol. 4, no. 12. - P. 1272-1283.

[86] Kossmann, D. The state of the art in distributed query processing / Donald Kossmann // ACM Comput. Surv. - 2000. - Vol. 32, no. 4. - P. 422 469.

[87] Pentaris, F. Query optimization in distributed networks of autonomous database systems / Fragkiskos Pentaris, Yannis Ioannidis // ACM Trans. Database Syst. - 2006. - Vol. 31, no. 2. - P. 537-583.

[88] Lim, H. Stubby: A transformation-based optimizer for mapreduce workflows / Harold Lim, Herodotos Herodotou, Shivnath Babu // PVLDB. — 2012. — Vol. 5, no. 11. — P. 1196-1207.

[89] Herodotou, H. Profiling, what-if analysis, and cost-based optimization of mapreduce programs / Herodotos Herodotou, Shivnath Babu // Proceedings of the VLDB Endowment. - 2011. - Vol. 4, no. 11. - P. 1111-1122.

[90] Ysmart: Yet another sql-to-mapreduce translator / Rubao Lee, Tian Luo, Yin Huai et al. // Distributed Computing Systems (ICDCS), 2011 31st International Conference on / IEEE. — 2011. — P. 25-36.

[91] Mrshare: sharing across multiple queries in mapreduce / Tomasz Nykiel, Michalis Potamias, Chaitanya Mishra et al. // Proceedings of the VLDB Endowment. - 2010. - Vol. 3, no. 1-2. - P. 494-505.

[92] Query optimization for massively parallel data processing / Sai Wu, Feng Li, Sharad Mehrotra, Beng Chin Ooi // Proceedings of the 2nd ACM Symposium on Cloud Computing. — SOCC '11.- New York, NY, USA: ACM, 2011.-P. 12:1-12:13.

[93] Zhou, J. Incorporating partitioning and parallel plans into the scope optimizer / Jingren Zhou, P-A Larson, Ronnie Chaiken // Data Engineering

(ICDE), 2010 IEEE 26th International Conference on / IEEE. — 2010.^ P. 1060-1071.

[94] Data integration flows for business intelligence / Umeshwar Dayal, Malu Castellanos, Alkis Simitsis, Kevin Wilkinson // Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology / ACM. - 2009. - P. 1-11.

[95] Lavariega, J. C. An object algebra approach to multidatabase query decomposition in donaji / Juan C. Lavariega, Susan D. Urban // Distrib. Parallel Databases. - 2002. - July. - Vol. 12. - P. 27-71.

[96] Bertino, E. Integration of heterogeneous data repositories by using object-oriented views / Elisa Bertino // Interoperability in Multidatabase Systems, 1991. IMS'91. Proceedings., First International Workshop on / IEEE. — 1991. _ p. 22-29.

[97] Eliassen, F. Managing identity in global object views / Frank Eliassen // Research Issues in Data Engineering, 1995: Distributed Object Management, Proceedings. RIDE-DOM'95. Fifth International Workshop on / IEEE. — 1995 _ p 70^77.

[98] Kalinichenko, L. A. Heterogeneous information model unification as a prerequisite to resource schema mapping / L. A. Kalinichenko, S. A. Stupnikov // Information Systems: People, Organizations, Institutions, and Technologies. — Springer, 2010. - P. 373-380.

[99] Atzeni, P. Schema and data translation: A personal perspective / Paolo Atzeni // Advances in Databases and Information Systems / Springer. — 2007. - P. 14-27.

[100] Schema mediation in peer data management systems / Alon Y Halevy, Zachary G Ives, Dan Suciu, Igor Tatarinov // Data Engineering, 2003. Proceedings. 19th International Conference on / IEEE. — 2003. — P. 505-516.