Диссертация (1149731), страница 10
Текст из файла (страница 10)
Процессисполнения сценария непрерывно отслеживается, собираются актуальные статистики времени исполнения, на основе которых адаптивно перестраиваютсяпланы параллельного выполнения запроса.Расширение оптимизатора системы SCOPE на случай работы с планамипараллельного исполнения запросов предложено в [93].Системы оптимизации и исполнения сложных сценариев анализа данныхтакже обсуждались в [44, 94]. В статье [94] строится современная система оптимизации и исполнения ETL процессов. Слоистая архитектура системы делаетвозможной оптимизацию на каждом из уровней спецификации.
Авторы выделяют такие критерии качества и эффективности ETL сценария, как надежность(reliability), свежесть (freshness), масштабируемость, доступность (availability)и другие. На основе этих неформальных критериев основывается процесс оптимизации. Авторы выделяют три основных метода оптимизации сценариевинтеграции данных: алгебраические трансформации, перестроения сценария иадаптация к текущему окружению. Оптимизация сценариев на основе алгебраических трансформаций аналогична оптимизации традиционных запросов вреляционной базе данных с учетом специфики набора доступных операций итрансформаций. К сценариям интеграции данных также могут быть применены классические методы оптимизации процессов, такие как распараллеливаниеи исключение узлов условного перехода. Детальное описание и анализ предложенного оптимизатора представлен в работе [44].451.4.2.
Приближенные вычисленияСистемы анализа данных, описанные в [14, 15] позволяют исполнять определенные классы запросов с учетом ограниченных вычислительных ресурсов,фокусируясь на приближенных вычислениях на основе случайных выборок.Система приближенного исполнения SQL запросов с агрегированием,предложена в [14]. Приближенные запросы могут быть аннотированы ограничениями на значение ошибки или на время вычислений, на основе которых система выбирает подходящий размер случайной выборки для приближенного исполнения запроса. В работе [15] авторы описали систему исследования данных,основанную на приближенном исполнении SQL запросов с контролем временивычисления и точности результата.
Предложенная система основана случайныхвыборках, называемых впечатлениями, размеры которых определяются статистически низкой ошибкой результата вычислений и жесткими ограничениямина время.1.5. Основные результатыВ главе проведен обзор существующих методов оптимизации и приближенного выполнения декларативных сценариев нечеткой аналитической обработкиданных.В обзоре рассмотрен класс нечетких запросов, ставший широко распространенным в контексте новых типов обработки и поиска данных.
Построенаклассификация подходов к оптимизации и приближенному выполнению нечетких запросов на основе сопоставления с методами, разработанными для точных декларативных запросов. Проведенный анализ подходов позволил выделить основные направления развития методов оптимизации и приближенноговыполнения сложных запросов к разнородным и распределенным источникаминформации.Основные результаты главы опубликованы в статьях [22, 23, 25].46Глава 2. Основные понятияВ этой главе введены основные понятия, а именно теоретическая модельоптимизации и контролируемого приближенного выполнения нечетких запросов, в том числе понятия качества и вычислительных ресурсов, модель стоимости и качества операций.
Здесь также уточнены задачи оптимизации запросов вконтексте их приближенного выполнения, и поставлена математическая задачараспределения ресурсов.Мы предложим системный подход к работе с понятием подобия, одновременному использованию различных метрик близости и парадигмам анализаданных, сложного поиска и исполнения запросов, комбинированию структурированных и неструктурированных данных в одном аналитическом сценарии.2.1. Декларативные языки и расширенная алгебраСистема эффективного выполнения сценариев обработки данных строитсяна исполнении декларативных запросов, описывающих аналитическую задачу.Декларативные языки запросов позволяют специфицировать обработку данных на уровне коллекций и предоставляют простор для оптимизации, котораяобеспечивает эффективное исполнение. В исследовании мы не опираемся наконкретные высокоуровневые декларативные языки запросов, а предполагаем,что запросы в системе сформулированы на некотором из них, и прорабатываемсредства их выполнения на более низком уровне.В работе мы рассматриваем алгебраический слой, который функционируетмежду пользовательским интерфейсом (чаще всего, графическим) и вычислителями в послойной архитектуре системы анализа данных.
Запрос, сформулированный в пользовательском интерфейсе на декларативном языке передаетсяв алгебраический слой, транслируется и исполняется.47Отметим, что поскольку мы рассматриваем алгебраический слой, вне рамок обсуждения остаются многие аспекты связанные с построением системыанализа данных, например, задача отображения моделей данных.Мы введем алгебру на основе понятия нечетких множеств, которая позволит единообразно соединять в одном аналитическом сценарии разные видыобработки разнородных данных.
Построенная алгебра позволит специфицировать различные аналитические сценарии и предоставит простор для их оптимизации и последующего приближенного исполнения. Предложенная алгебраявляется расширением реляционной, также как и алгебры, рассмотренные вразделе 1.2.1.Помимо фиксированной расширенной алгебры важно предусмотреть возможность ее дальнейшего расширения, что позволит учитывать развитие области и естественно включать новые типы обработки и анализа данных.2.1.1.
Функция оценкиПостроение алгебры начнем с формального определения базовых понятий.При построении системы исполнения сложных аналитических сценариевнеобходимо определить, как будут сопоставляться объекты с запросами и другс другом. Начнем с определения расстояния между парой объектов некоторогомножества и воспользуемся базовым определением метрического пространства.Метрическое пространство есть пара (, ), где —множество, а : × → R - функция расстояния (метрика) со следующим набором свойств:∙ (, ) ≥ 0, (, ) = 0 ⇔ = (тождество);∙ (, ) = (, ) (симметричность);∙ (, ) ≤ (, ) + (, ) (неравенство треугольника).Определение 2.1.Таким образом над множеством объектов можно определить функцию расстояния, которая будет отражать соотношение между объектами этого множества.Представленная далее модель использует понятие подобия в качестве основного инструмента, подходящего для сопоставления объектов с запросами идруг с другом.48Функцией подобия над метрическим пространством(, ) называется : × → (0, 1] такая, что (, ) ≤ (, ) ⇔ (, ) ≤(, ).Определение 2.2.Из определения функции подобия следует, что она обратная по смыслуфункции расстояния, и принимает большие значения для более близких объектов.Функции подобия и расстояния тесно связаны, то есть объекты считаются подобными, если расстояние между ними невелико в определенной метрике.Понятия подобия и расстояния являются проверенным инструментом и основойдля многочисленных методов анализа данных.
Например, близкие объекты втерминах некоторой функции расстояния кластеризуются вместе. В задачах информационного поиска ранжирование объектов происходит на основе значенийфункции подобия в пространстве документов между объектом представляющим запрос и объектами-документами (поисковыми образами документов). Таким образом, методы анализа данных на основе подобия зависят от определенияфункции расстояния или функции подобия, которые являются приближениемк семантике конкретной предметной области и задачи.В случае поиска по образцу запрос представлен объектом в анализируемом пространстве, но понятие подобия переносится и на более широкий классзапросов.
В этом случае функция подобия определяется следующим образом:Определение 2.3. Абстрактной функцией подобия для множества запросови множества объектов называется : × → R такую, что если- метрическое пространство, на нем определена функция подобия ,то ≡ .(, ) ≡ ,В этом определении релевантность объекта запросу выражается оценкой,вычисленной как значение функции подобия между объектом и запросом. Теперь, когда функция подобия определена между запросами и объектами, онатакже может представлять, например, точные запросы в традиционных базахданных. Отметим, что представленном выше определении множество запросов не специфицировано и может нести различную семантику, например, черезабстрактную функцию подобия может быть выражено определение нечеткогомножества, где значения функции подобия определяют степень принадлежности объекта множеству.49В нашей модели мы требуем, чтобы все значения функции подобия лежалив интервале [0, 1], в частности, подразумевая, что они могут быть рассмотреныкак вероятности релевантности объекта запросу.Определение 2.4.
Для множества запросов и множества объектов абстрактная функция подобия : × → [0, 1] называется функцией оценки.Из определения видно, что функция оценки, с которой мы будем работать,по своей семантике совпадает с функцией подобия и отличается от нее лишьобластью значений.2.1.2. Множество объектовФункции подобия позволяют работать с некоторыми объектами, поэтомуформализуем и уточним понятие анализируемого объекта:Любой объект из множества определяется парой(, ), в которой - идентификатор объекта, - множество атрибутовобъекта.Определение 2.5.Иными словами анализируемый объект определяется своим идентификатором и множеством атрибутов, на основе которых происходит его обработка.Отметим, что не происходит строгой типизации объектов по набору и типуатрибутов. Несмотря на тот факт, что требования к структуре объектов минимальны, некоторые свойства и атрибуты объекта, в конечном счете необходимыдля исполнения любого запроса.Мы требуем от всех объектов идентифицируемости ( [95–97]).
Предполагается, что объект, полученный из первичного источника, может быть извлеченна основе его идентификатора. Природа идентификатора может варьироватьсяот простого URL до суррогатных значений и зависеть от объекта, что делаетего неизменным. Ожидается, что идентификаторы объектов согласованы между источниками данных, то есть, если объект может быть получен из различных первичных источников, ожидается, что он имеет тот же идентификатор, иобъекты с разными идентификаторами различны.Исполнение запроса и даже его спецификация требуют определенного знания мета-информации, связанной с анализируемыми или запрашиваемыми объектами. Как правило, эта информация доступна в некоторой схеме, которой50принадлежат объекты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
