Автореферат (1149730), страница 3

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

Текст из файла (страница 3)

Выражения1 , 2 ∈ Eэквивалентны,если существует конечная цепочка трансформаций (с заменой подвыраженийпеременными и обратно), переводящая1в2 .Для любого выражения в алгебре можно построить множество эквивалентных ему на основе алгебраических тождеств. Запросом называется множествоэквивалентных выражений в алгебре, которое может быть представлено однимиз них ∈ E. Для запроса ∈ E через () = { | ≡ } обозначим множествопланов выполнения запроса.На выполнение операции могут влиять параметры, такие как конфигурациявычислителей или специфические параметры вызова алгоритма, реализующегооперацию.

Для операции∈Oпространство конфигураций()представля-ет пространство значений параметров, влияющих на ее выполнение. Операцию∈Oс конфигурациейполнения запроса ∈ ()будем обозначать через().Для плана вы- ∈ E его конфигурация определяется множеством конфигу-раций операций его составляющих: конфигурацией плана называется функция⋃︀ : () → ∈() () такая, что ∀ ∈ () () ∈ (). План выполнениязапроса ∈ E с конфигурацией ∈ () будем обозначать через (). Пространство сконфигурированных планов выполнения запроса ¯ ∈ E обозначимкак P(¯) = {(, )| ∈ (¯), ∈ ()}.Для операции ∈ O с конфигурацией ∈ () критерием эффективности называется функция (()) : Q→ R. Оценки эффективности планов строятся на основе оценок эффективности отдельных операций, участвующих в алгебраическом выражении.

Для плана выполнения запросас конфигурацией ∈ ()его эффективность по критерию ∈ Eвычисляетсякак функция от стоимостей отдельных операций его составляющих, то есть(()) = ({(( ))| ∈ (), = ()}) ∈ R,где- функция агрегирова-ния оценок эффективности операций в плане.Для каждого критерия оценки эффективности определен частичный порядок, формализующий относительную эффективность операций по этому кри-(1 , 1 ), (2 , 2 ) ∈P() (1 (1 )) ≺ (2 (2 )), если 1 (1 ) не менее эффективен, чем 2 (2 ), по критерию .терию: для сконфигурированных планов выполнения запросаЭффективность операций (и, следовательно, планов) может измеряться одновременно на основе различных критериев, таких как время вычислений, объ- ∈ O с конфигурацией¯(()) : Q → R .емы ввода/вывода, процессорное время.

Для операции ∈ ()функцией стоимости называется функцияНа пространстве значений функций стоимости определено отношение, позволяющее сравнивать стоимость разных операций и выражений: для сконфи9(1 , 1 ), (2 , 2 ) ∈ P() ¯(1 (1 )) ≺только тогда, когда ∃ ∈ [1 : ] :гурированных планов выполнения запроса¯(2 (2 )) в пространстве R¯(1 (1 )) ≺ ¯(2 (2 )) ., тогда иТочное вычисление оценок эффективности планов и операций невозможно, поскольку требует исполнения плана, поэтому в качестве приближенияфункций стоимости операций рассматриваются их модели стоимости: для опе- ∈ O с конфигурацией ∈ () модель стоимости это функция¯(()) : S → R , где S - пространство свойств Q-множеств.

Таким образом,при оценке эффективности планов вычисление функции стоимости ¯ заменяется вычислением ¯. Для плана выполнения запроса ∈ E с конфигурацией ∈ () его приближенная стоимость, вычисленная на основе моделей стоимости, обозначается через ¯(()) ∈ R .рацииНа основе понятия модели стоимости в диссертации сформулированы задачи однокритериальной, многокритериальной и параметрической оптимизации.В этом исследовании мы рассматривали возможность приближенного выполнения запросов, в ситуациях, когда для вычисления неточного ответа тратится меньшее количество ресурсов.

Для поддержки эффективной реализации,используются приближенные контролируемые алгоритмы исполнения алгебраических операций, которые позволяют влиять на количество вычислительныхресурсов и качество результата.Для управления вычислениями применяются конфигурации алгоритмов: тоесть для операции∈Oконфигурация ∈ ()может содержать парамет-ры, определяющие контролируемое приближенное поведение. Мы фокусируемся на приближенном выполнении запросов и для упрощения обозначенийсчитаем, что конфигурация операции отвечает только за ее контролируемоеприближенное выполнение.Различные типы ресурсов могут быть использованы для оценки эффективности выполнения запросов и для ограничения их приближенного выполнения.Очевидно, что оптимальный план зависит от типа ресурсов, который мы минимизируем.

Однако, мы считаем, что функция стоимости оценивает скалярноезначение ресурсов, отражающее его количество, но не тип. Таким образом, ресурсы это выделенный агрегированный критерий оптимизации, принимающийзначения в пространствеR ⊂ R.Мы предполагаем, что ресурсы могут бытьраспределены между операциями в плане и стоимость плана равна сумме количеств ресурсов, выделенных отдельным операциям.Приближенное поведение операции зависит от выделенного на ее выполнение количества вычислительных ресурсов. Для операции∈Oсуществуетфункция отображения количества ресурсов, выделенных на выполнение операции, в параметры ее конфигурации:через() : R → ().Для ∈ Oи ∈ Rобозначим сконфигурированную операцию при данном количествересурсов, то есть() = ( ()).Несмотря на то, что понятие качества данных сложное и часто рассматривается в нескольких размерностях, мы предполагаем, что качество набора10данных и Q-множества, оценивается одним числом, то есть мы применяем агрегированный критерий.Для построения моделей стоимости/качества используются оценки относительного качества операций, принимающие значения в пространствеQ ⊂ R: тоесть отношения качества результирующего Q-множества к качеству аргументовоперации, поскольку даже операции с неограниченным количеством ресурсовмогут изменять качество данных.Когда мы ограничиваем количество вычислительных ресурсов на исполнение операции, ее относительное качество может оцениваться через отношениеабсолютного качества результата, полученного при ограничениях, к качествудостижимому при неограниченных ресурсах.Для операции∈Oстоимости это функция ∈ () бикритериальная модель¯(()) : S → R × Q.

Таким образом, в расширеннойс конфигурациеймодели стоимости связаны два ключевых критерия оценки приближенных планов выполнения запросов: качество и вычислительные ресурсы. Для операции∈Oмодель качества это пара функций :S×R→Qи−1 : S × Q → R.Задача распределения ресурсов, состоит в том, чтобы распределить ограниченное количество вычислительных ресурсов между операциями в плане выполнения запроса так, чтобы максимизировать качество ответа. Для заданного ∈ E и фиксированногоколичества ресурсов ∈ R∑︀¯ = { ≥ 0| ∈ (), ∈ R} : ∈() ≤ называется распремножество делением ресурсов, определяет количество ресурсов, выделяемое ∈ ().¯ обозначим множество всех возможных распределений вычислительЧерез ¯ = {¯ | ∈ R}. Различные стратегии распределенияных ресурсов , а через плана выполнения запросаресурсов между операциями в плане выполнения запроса определяют качествоответа.

Для плана выполнения запросавается функция¯ → Q.() : ∈Eотносительным качеством назы-Для заданного плана выполнения запроса ∈ E и фиксированногоколичества ресурсов ∈ R задача распределения ресурсов ставится следующим образом: arg max¯ ∈¯ ()(¯ ).Задача 1Предполагая решение задачи распределения ресурсов, можно определить∈E ( ) = max¯ ∈¯ ()(¯ ).функцию качества плана: для плана выполнения запросамодель качества : R → Qтак, чтоопределим егоВ контексте приближенного выполнения мы рассматриваем два критерияоптимизации запроса: количество вычислительных ресурсов и качество результата, поэтому мы можем рассматривать задачу бикритериальной оптимизации.Задача бикритериальной оптимизации запроса ∈ E, допускающего приближенное исполнение, ставится следующим образом: найти¯ ¯, ∀ˆ{(¯, ¯)|¯ ∈ (), ¯ ∈ ¯¯ ∈ ∈ (), ^ ∈ ¯^ (¯)(¯) ≥ (ˆ)(^)}.Задача 2Поскольку мы рассматриваем оптимизацию и контролируемое приближенное выполнение сценариев анализа данных, возникает специфическая постановка задачи параметрической оптимизации.11Задача параметрической оптимизации запроса ∈ E ставитсяследующим образом: найти функцию : R → () такую, что если ( ) = ¯,то ∀ˆ ∈ () ¯( ) ≥ ^( ), где ∈ R.Задача 3Поставленные задачи бикритериальной и параметрической оптимизации запросов, допускающих приближенное исполнение, эквивалентны.Конечная задача выбора оптимального плана для последующего исполнения может быть поставлена следующим образом: для заданного запросаи фиксированного количества ресурсов ∈ Rнайти¯ ∈ ()∈Eтакой, что∀ˆ ∈ () ¯( ) ≥ ^( ).В третьей главе описано решение задачи распределения ресурсов: дляплана выполнения запроса, допускающего приближенное исполнение, конструируется стратегия распределения заданного количества вычислительных ресурсов, обеспечивающая лучшее возможное качество результата.План выполнения запроса может быть представлен деревом, в котором вершины представляют операции, а ребра соединяют операции с их аргументамив выражении плана.

Деревом плана выполнения запроса ∈ Eназывается = ( ( ), ( )): любой ∈ () соответствует вершина ∈ ; если 1 , 2 ∈ () и 2 является аргументом 1 , то ребро ∈ ( ) связывает соответствующие вершины 1 и 2 . Для дерева плана и для вершины ∈ ( ) () ⊂ ( ) — множество вершин-детей; для не корневой операции () — родительская вершина; ¯ — поддерево с вершиной в .графДля вершины в дереве плана на основе модели качества соответствующей ∈ ( ),соответствующей операции ∈ () с моделью качества : S × R → Q,функцией качества называется () : R → Q такая, что () = (), где ∈ S операции построим функцию качества: для ∈ Eдля вершиныфиксированные статистики аргумента операции.

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

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