Диссертация (1149731), страница 15
Текст из файла (страница 15)
Основные результатыВ главе предложена теоретическая модель оптимизации и контролируемого приближенного выполнения нечетких запросов. На основе введенных ключевых понятий сформулирована задача распределения ресурсов, а также поставлена задача бикритериальной оптимизации запросов, допускающих приближенное выполнение. Система понятий и задач, изложенная в главе, опубликованав [17–20, 23, 24].74Глава 3. Распределение ресурсов в планевыполнения запросаВ этой главе описано решение поставленной в главе 2 задачи 2.4 распределения ресурсов: для плана выполнения запроса, допускающего приближенноеисполнение, конструируется стратегия распределения ограниченного количества вычислительных ресурсов, обеспечивающая лучшее возможное качестворезультата.3.1. Мотивирующий примерПроиллюстрируем задачу распределения ресурсов на примере плана исполнения запроса, который выявляет продукты компании с наименьшим рейтингом, на основе оценок нескольких розничных магазинов.Идея запроса состоит в том, чтобы найти продукты с низким рейтингом,с тем, чтобы в дальнейшем их анализировать.
На первый взгляд, ответ на этотзапрос может быть получен на основе информации от одного магазина. Однако, чтобы сделать результаты более надежными, мы могли бы объединитьинформацию от нескольких магазинов.План выполнения запроса включает в себя операции первичной выборкиданных из различных источников, последующее соединение по названию продукта с тем, чтобы построить агрегированный рейтинг, и сортировку:12sortjoin on product name3get ratings for company products from reatiler14get ratings for company products from reatiler2Точное выполнение этого плана потребовало бы полного извлечения дан-75абРис.
3.1. Распределение ресурсов в плане выполнения запроса-примераных из обоих источников и заняло много времени. Скорее всего, это не имеетсмысла, поскольку аналитик заинтересован в выборе лишь нескольких продуктов, которые требуют дальнейшего детального анализа. Следовательно, выборка данных из источников должна быть ограничена. В этом случае запрос будетвыполнен приближенно, поскольку оценки некоторых объектов не будут учтены, что повлияет на качество конечного ответа на запрос.
Отметим, что в этомпримере, качество приближенного ответа может быть оценено как доля правильно возвращенных объектов в результате выполнения запроса.Предположим, что источники данных возвращают в операцию выборкиобъекты со средней скоростью 300 и 500 объектов в секунду, соответственно.Предположим также, что пользователь ожидает ответа через 200 миллисекунди лучший возможный (неизвестный) ответ на запрос содержит 50 объектов.Доступное ограниченное количество вычислительных ресурсов (200 миллисекунд в этом примере) может быть распределено между операциями в планеразличными способами, влияя на качество результата. Две возможные стратегии распределения ресурсов между операциями в нашем плане проиллюстрированы на рисунке 3.1.Рассмотрим стратегию распределения ресурсов, в которой выборка из первого источника данных использует 150 мс и возвращает 45 объектов, выборка из76второго источника занимает 30 мс и извлекает 15 объектов, а остальные 20 мснеобходимы для исполнения операций соединения и сортировки (рисунок 3.1а).Конечный результат вычислений будет содержать не более 15 объектов и, следовательно, оценка качества не может превышать 30%.Гораздо лучшие результаты могут быть получены, если выборка из первого источника данных будет использовать 100 мс, из второго - 60 мс, в результатечего 40 мс будут выделены последующим операциям (рисунок 3.1б).
Оба источника данных вернут за выделенное время 30 объектов и качество результатаможет достигнуть 60%.Приведенный пример показывает, что не имеет смысла ограничивать некоторые операции (используя приближенные алгоритмы), оставляя точными другие, так как качество результата будет сильно зависеть от операций с наименьшим качеством. Другими словами, распределение ограниченного количестваресурсов между операциями должно быть сбалансировано.3.2. Вычислительная модельМы работаем с планами выполнения запросов (определение 2.19), и решаемзадачу 2.4 распределения ресурсов, сформулированную в главе 2.3.2.1.
Дерево планаПлан выполнения запроса может быть представлен деревом, в которомвершины представляют операции, а ребра соединяют операции с их аргументами в выражении плана.Определение 3.1. Деревом плана выполнения запроса ∈ E называется граф: любой ∈ () соответствует вершина ∈ ; еслии является аргументом 1, то ребро ∈ ( ) связываетсоответствующие вершины и . = ( ( ), ( ))1 , 2 ∈ () 212Отметим, что листьями дерева являются операции первичной выборки,информация о источниках данных, из которых они извлекают Q-множества,далее учитывается внутри листьев дерева-плана. В этой главе в дальнейшеммы будем оперировать только с представлением плана выполнения запроса в77Рис. 3.2.
Пример дерева плана выполнения запросавиде дерева и использовать понятия плана и дерева, вершины и операции взаимозаменяемо.Введем несколько обозначений, связанных с определением дерева плана.Для дерева плана и для вершины ∈ ( ) () ⊂ ( ) — множество вершин-детей; для не корневой операции () — родительская вершина; ¯ — поддерево с вершиной в .Определение 3.2.Отметим, что (под)деревья однозначно соответствуют (под)планам выполнения запроса.Пример дерева плана выполнения запроса показан на рисунке 3.2.
Деревоплана содержит все вершины-операции: ( ) = {0 , 1 , 2 , 3 , 4 , 5 }; поддеревос корнем в 2 определяется как ¯2 = {2 , 4 , 5 }; (5 ) = 2 и (0 ) ={1 , 2 , 3 }.3.2.2. КачествоВ главе 2 по определению 2.38 модель качества операции ∈ O показывала, как зависит относительное качество выполнения операции при определенных ограничениях на количество вычислительных ресурсов и знании статистикаргументов операции.В дальнейшем в этой главе мы предполагаем, что незначительные изменения количества вычислительных ресурсов при приближенном выполненииопераций не могут существенно изменить статистики Q-множеств обрабатываемых в плане выполнения запроса.
Разработанный нами и описанный далее78итеративный алгоритм распределения ресурсов будет на каждом шаге пересчитывать статистики, обеспечивая допустимость этого предположения.Для вершины в дереве плана на основе модели качества соответствующейоперации построим функцию качества., тогда для вершины ∈ ( ), соответствующей операции ∈ () с моделью качества : S × R → Q, функциякачества () : R → Q определяется следующим образом: () = (), где ∈ S- фиксированные статистики аргумента операции.Определение 3.3.Пусть ∈ EТаким образом, если операция ∈ ( ) получает количество ресурсов ∈ R она достигает качества ()().Качество, достигаемое при приближенном выполнении плана, зависит отконфигурации операций, его составляющих, в том числе распределения ограниченного количества доступных вычислительных ресурсов.
Определим распределение ресурсов в новых терминах дерева и его вершин.Для заданного дерева плана выполнения запроса и фиксированного количества вычислительныхресурсов ∈ R множество ¯ =∑︀{ ≥ 0| ∈ ( ), ∈ R} : ∈ ( ) ≤ называется распределением ресурсов, определяет количество ресурсов, выделяемое ∈ ( ).Количество ресурсов, выделенное (под)дереву с корнем в обозначим черезОпределение 3.4.¯ ∈ R.Через ¯ обозначим множество всех возможных распределений ограниченного количества вычислительных ресурсов .В главе 2 относительное качество плана выполнения запроса определялоськачеством его операций, что позволяет перейти к понятию функции качествадерева плана.Для дерева плана выполнения запроса и распределенияресурсов ¯ ∈ ¯ его качество определяется следующим образом: (¯ ) = ({()( )| ∈ ( ), ∈ ¯ }), где -функция агрегирования качества вплане (по определению 2.24).Определение 3.5.Формализуем один из возможных подходов к оценке качества плана, втерминах его представления в виде дерева и функций качества его вершин, тоесть определим конкретную реализацию функции .79Качество плана зависит от качества подпланов и свойств корневой операции.
Например, качество (под)плана с бинарной корневой операцией зависитот трех параметров: качества левого и правого подпланов, ¯ и ¯ соответственно, и качества корневой операции (), где , ∈ ().Для операций с несколькими аргументами мы предполагаем, что вкладаргумента с меньшим качеством доминирует при оценке качества поддерева.Более формально, качество поддерева оценивается как произведение относительного качества корневой операции и общего (минимального) качества ееаргументов: для любого распределения ресурсов ¯¯ ∈ ¯¯ ¯ (¯¯ ) = ()( ) ·min∈() ¯ (¯¯ ), где ∈ ¯¯ , ¯¯ = { | ∈ (),¯ ∈ ¯¯ }.Отметим, что описанная функция агрегирования качества в плане не единственная и можно рассматривать другие ее реализации, например, ¯ (¯¯ ) =∏︀()( ) · ∈() ¯ (¯¯ ), где ¯¯ ∈ ¯¯ , ¯¯ = { | ∈ (),¯ ∈ ¯¯ }, ∈ ¯¯ , что может повлиять на решение задачи распределения ресурсов. Тем не менее в этойглаве мы далее будем использовать функция агрегирования качества в планена основе минимального качества аргументов операций.3.2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
