Диссертация (1149731), страница 4
Текст из файла (страница 4)
Cost models forapproximate query evaluation algorithms // Databases andInformation Systems. Tenth International Baltic Conference onDatabases and Information Systems. Local Proceedings, Materialsof Doctoral Consortium. / Ed. by A. Caplinskas, G. Dzemyda, A.Lupeikiene, O. Vasilecas.— Vilnius: Zara, 2012.— P. 20–28. (А.С.Ярыгиной принадлежит разработка расширенных моделей стоимости икачества для ряда операций; О.А.
Долматовой принадлежит реализациямоделей и проведение экспериментальной оценки; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности)9) Новиков Б. А., Ярыгина А. С. Задачи оптимизации запросов в распределенной среде неоднородных информационных ресурсов // Математика,16экономика, менеджмент: 100 лет со дня рождения Л.В. Канторовича / Ed.by Иосиф Владимирович Романовский.— Санкт-Петербургский гос. университет, 2012.—7–9 февраля.— P.
57–59. (А.С. Ярыгиной принадлежитобщая постановка задачи оптимизации запросов; Б.А. Новикову принадлежит позиционирование задачи в контексте методов исследования операций)10) Yarygina A., Novikov B., Vassilieva N. Processing complexsimilarity queries: A systematic approach // ABDIS 2011 ResearchCommunications: Proceedings II of the 5th East-EuropeanConference 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.
(А.С. Ярыгиной принадлежит сравнительный анализ методовсинтеза и нормализации, реализация алгоритмов, проведение вычислительных экспериментов; Б.А. Новикову принадлежит общая постановказадачи и обоснование ее актуальности, алгебраическая систематизацияметодов синтеза; Н.С. Васильевой принадлежит реализация методов вычисления оценок подобия изображений)Все исследования, результаты которых изложены в диссертационной работе, проведены лично автором в процессе научной деятельности. Из совместныхпубликаций в результаты диссертационной работы включен лишь тот материал,который непосредственно принадлежит автору.Структура диссертацииДиссертационная работа состоит из введения, 5 глав, заключения и списка литературы. Общий объем диссертации - 149 страниц.
Список литературысодержит 100 названий.17Глава 1. Оптимизация и выполнениедекларативных сценариев обработки данныхВысокоуровневые декларативные запросы могут использоваться для описания сценариев сложной аналитической обработки в среде распределенныхнеоднородных информационных ресурсов. Одновременное резкое увеличениеобъемов и разнообразия типов данных, доступных для массовой обработки в информационных сетях, и ужесточение требований по времени их анализа, привело к необходимости пересмотра известных методов выполнения и оптимизациизапросов.
В этой главе представлен обзор подходов к выполнению и оптимизации декларативных запросов; обсуждаются открытые проблемы и возможныенаправления их решения.Обзор включает в себя анализ работ исследовательского сообщества, посвященных точному выполнению и оптимизации декларативных запросов в традиционных системах баз данных. Особое внимание в этой главе уделено существующим подходам к работе с нечеткими запросами, а также методам приближенного выполнения сценариев анализа данных. Завершает обзор обсуждениесовременных систем анализа больших данных на основе распределенных и приближенных вычислений.В обзоре, в силу его ограниченности, не освещены такие важные и смежныетемы как распределенное выполнение запросов, алгоритмы точного и приближенного выполнения конкретных алгебраических операций и соответствующиемодели стоимости, а также вопросы, связанные с качеством данных и точностью ответа на запрос.1.1.
Выполнение точных запросовВ этом разделе обсуждаются реляционные языки запросов: лежащая вих основе алгебра, а также методы оптимизации и выполнения запросов стали18стартовой точкой в разработке более сложных систем обработки декларативныхсценариев анализа данных.Этой теме посвящено множество более ранних обзоров, например [26], темне менее, анализ существующих методов выполнения и оптимизации точныхзапросов в нашей работе носит не только исторических характер, но и позволяет описать контекст, ввести основные понятия, необходимые для дальнейшегоизложения.1.1.1.
Языки запросовВ основе реляционных баз данных лежит реляционная алгебра, представляющая собой замкнутую систему операций над отношениями в реляционноймодели данных. Первоначальный набор операций был предложен Codd [27].В процессе развития реляционной теории и практики были предложены новые производные операции. Поскольку многие операции выразимы друг черездруга, в составе реляционной алгебры можно выделить несколько вариантовбазиса, например предложенный в [28].Запрос, сформулированный на некотором декларативном языке, напримерSQL, в реляционной СУБД преобразуется в выражение в терминах операцийалгебры.
Важно отметить, что нетривиальный исходный запрос может бытьпредставлен в виде алгебраического выражения многими способами, и большинство алгебраических операций реализуется несколькими алгоритмами. Этоделает возможным выполнение декларативного запроса многими способами, тоесть на основе нескольких планов его выполнения.В [29] описываются основные этапы выполнения запроса в реляционнойбазе данных, и выделены следующие модули:∙ парсер,∙ оптимизатор,∙ генератор кода,∙ исполнитель.Данная схема используется в большинстве систем выполнения декларативных запросов. Парсер получает на входе запрос на некотором декларативном19языке и преобразует его в выражение на языке реляционного типа.
Оптимизатор перебирает пространство эквивалентных планов выполнения запроса ивыбирает план, который рассматривается как оптимальный. Генератор кода повыбранному плану строит последовательность команд обращения к исполнителю запроса.В обзоре [26] обсуждаются основы конструирования систем управлениябазами данных, включая архитектуру и такие подходы к выполнению запросов, как итеративное вычисление сложных планов, параллельное выполнениеи его реализация. В статье также рассматриваются основные алгоритмы выполнения некоторых базовых реляционных операций; детально обсуждаютсяалгоритмы, реализующие реляционные операции агрегирования и соединенияна основе вложенных циклов, сортировки, слияния и хеширования.Важно отметить, что во многих СУБД при выполнении запроса исполнителем алгебраические операции реализованы как операции над потоками данных.
Операция, читает аргументы из отдельных потоков данных и записываетрезультат в выходной поток по мере его формирования. Такой подход позволяет отказаться от материализации данных, передаваемых между операциямивнутри одного запроса. Конечно, реализация операции, например, сортировки,может использовать внутреннюю материализацию промежуточных результатов.Мы будем различать первичные источники, представляющие собой потокиданных (streams), и потоки (pipelines), возникающие при выполнении запроса.В дальнейшем, если это не будет следовать из контекста, мы будем уточнять,что подразумевается под потоком данных.1.1.2. Оптимизация запросовОбсудим детально этап оптимизации, поскольку он является существенным для систем, предоставляющих возможность использования декларативных языков, когда в запросе не специфицирован процесс построения ответа, иоптимизация становится возможной и полезной.
В обзоре [29] рассматриваетсязадача оптимизации запросов, архитектура оптимизатора, основанного на моделях стоимости, а также основные алгоритмы поиска наилучшего плана. Обзорклассических методов оптимизации запросов также представлен в работе [30].Оптимизатор выбирает из множества эквивалентных планов выполнения20запроса в некотором смысле наилучший. Эффективность планов может оцениваться разными способами в зависимости от цели оптимизации. Более формально задача оптимизатора состоит в том, чтобы найти план, функция стоимости(например, время выполнения плана или получения первого кортежа ответа)которого минимальна.В зависимости от характера функции стоимости выделяют оптимизаторы:∙ применяющие правила преобразования плана выполнения запроса в эквивалентный ему, которые заведомо приводят к уменьшению значениянеявной функции стоимости;∙ использующие явную функцию оценки стоимости выполнения запроса.Оптимизаторы, явно использующие функцию стоимости плана, строятсяна основе моделей стоимости операций [29, 31].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
