Диссертация (1149731), страница 7
Текст из файла (страница 7)
Например,при поиске изображений по подобию, пользователь редко может уточнить в запросе, по какому набору критериев следует искать близкие изображения. Неточность данных может быть вызвана, например, ошибкой журналиста при анализе потока новостей или естественной погрешностью сенсора. С другой стороны,приближенное выполнение запросов позволяет найти баланс между временемвычислений и качеством ответа на запрос, что является существенным при массовой обработке больших объемов данных.Как правило, в исследованиях рассматриваются приближенные алгоритмы, реализующие те или иные операции, или разрабатываются подходы, основанные на использовании операций усечения объемов обрабатываемых данных,ведущие к неточному ответу на запрос.Предлагаемые методы приближенного выполнения запросов можно также классифицировать на конфигурируемые и прерываемые.
В первом случаевремя выполнения запроса фиксируется заранее, и система строит фиксированную стратегию приближенного построения ответа на запрос. Прерываемыеподходы позволяют пользователю отслеживать качество результата в процессевычислений и останавливать выполнение операции или запроса.1.2.2.1. Понятие качестваОбсуждение приближенного выполнения запросов невозможно без учетакачества данных и информации, полученной в результате приближенных вычислений. Работа [53], например, посвящена детальному исследованию этогопонятия.Задача построения единой модели оценки качества результата выполнениязапросов при интеграции нескольких информационных систем рассматривается30в [54].
Авторы выделяют критерии качества, зависящие от источника данных(понятность, репутация, надежность, своевременность), запроса (полнота, количество) и атрибутов качества (доступность, цена, согласованность, время ответа, точность, релевантность). В статье предложена единая система численнойоценки выбранных критериев качества и разработан подход к поиску лучшихисточников данных и планов выполнения запроса, состоящий из трех фаз. Напервом этапе сокращается вычислительная сложность второго этапа за счетисключения источников данных низкого качества на основе соответствующихкритериев. На второй фазе генерируются все корректные планы выполнениязапроса. На последнем этапе просматривается все пространство планов и наоснове критериев качества выбирается оптимальный.1.2.2.2.
Приближенное выполнение запросовВ литературе принято различать приближенное (основанное на случайныхвыборках) и частичное (основанное на операции поиска лучших объектов) выполнение запросов [55]. Эти подходы являются ортогональными и не исключают их совместное применение, хотя это влечет значительное усложнение задачиоценки ошибки привносимой приближенным выполнением запроса.Учет ограничений на время выполнения сложных SQL запросов рассматривается в [55].
В предложенной вычислительной модели пользователь вместес обычным SQL запросом определяет верхнюю границу времени выполнениязапроса и характер ожидаемого неточного ответа: приближенный или частичный.Методы приближенного выполнения запросов, основанные на случайныхвыборках, вейвлетах или прогнозах, рассматривались в контексте больших хранилищ данных и распределенных сетей в [56–59].Специфическая задача приближенного выполнения запросов в среде webрешается в [60].
Авторы предложили модель приближенного выполнения запросов к RDF данным, которая позволяет не только эффективно строить неточныйответ, но и затем итеративно его улучшать при необходимости.1.2.2.3. Приближенное выполнение операцийКласс операций агрегирования, рассмотренный в [61], можно рассматривать как класс операций расширенной алгебры, основанный на операции объ-31единения в классической модели. Эта операция строит объединение двух списков объектов с оценками, где для объектов, имеющихся в обоих списках, вычисляется агрегированная оценка. Авторы [62] предлагают приближенный алгоритм выполнения операции агрегирования и приводят вероятностные оценкикачества получаемого результата.
В [63] также рассматривается приближенноевыполнение этой операции в случае, когда вычисление результата может бытьпрервано пользователем. Авторы предлагают методы оценки качества результата, построенного на промежуточных этапах выполнения операции.В статье [64] предложено несколько алгоритмов приближенного выполнения соединения на основе подобия с последующим выбором лучших объектов.Важно отметить, что в данной работе анализируется применимость приближенных алгоритмов в различных окружениях, в зависимости от стоимости вычисления предиката и стоимости получения объекта из потока аргументов.Авторы [9] обсуждают применение операций поиска лучших объектов ивыборки по оценке с целью улучшения эффективности выполнения запросов.В работе [65] авторы предлагают методы оценки необходимого количествакортежей, получаемых на вход в порядке убывания оценок операцией соединения с поддержкой ранжирования.Оптимальные алгоритмы реализации соединения по точному предикату сранжированием и последующим поиском лучших объектов предложены в [66].Данные алгоритмы могут быть основой быстрого и неполного вычисления ответа на запрос.Баланс между качеством и временем вычислений при обработке потоковданных исследуется в [67, 68].1.2.3.
Оптимизация запросов в расширенных алгебрахМетоды оптимизации запросов, рассмотренные в разделе 1.1.2, являютсяосновой высокой производительности традиционных СУБД и должны быть пересмотрены в контексте новых систем аналитической обработки данных в средераспределенных неоднородных информационных ресурсов.321.2.3.1. Алгебраические тождестваПространство планов при оптимизации запросов в первую очередь формируется за счет эквивалентных преобразований выражений алгебры.Расширенные языки запросов часто накладывают ограничения на оптимизацию, так как специфические наборы операций по сравнению с реляционнойалгеброй обладают менее широким набором эквивалентных преобразований запросов, формирующих пространство планов выполнения запросов [7]. Например, расширенные операции, изменяющие оценки объектов, не коммутируют соперацией сортировки по оценке.Авторы [7] предлагают два альтернативных пути решения проблемы, тоесть расширения набора эквивалентных преобразований выражений расширенной алгебры.
Первое основано на разработке наборов операций или специальных ограниченных операций, которые сохраняют свою выразительнуюспособность языка, но обладают более богатым пространством эквивалентныхпреобразований планов. Второй подход является более интересным в контексте приближенного выполнения запросов, поскольку основан на использованииприближенных преобразований выражений алгебры.
В этом направлении важно иметь способ оценки ошибки вносимой преобразованиями такого рода, например, при использовании приближенного алгоритма реализующего операциюили отсечений промежуточных результатов.Тем не менее, расширенные языки запросов обладают рядом точных алгебраических тождеств, применимых при оптимизации запросов [8, 9]. В [9] обсуждается точное преобразование алгебраического выражения с соединением ипоследующей выборкой объектов на основе порога на значение оценки в эквивалентное ему с предварительной дополнительной выборкой.
Также рассматривается аналогичное преобразование с операцией поиска лучших объектов, котороев общем случае не является точным. Эквивалентные преобразования, основанные на совместном применении операций поиска лучших объектов, выборкиобъектов по порогу на значение оценки и операции объединения демонстрируют, что множество эквивалентных преобразований выражений расширеннойалгебры не только сократилось, как показано в [7], но и пополнилось.Аналогично с [9] в [10] выводятся алгебраические соотношения для выражений с операцией соединения и последующей выборкой по порогу или споследующим поиском лучших объектов.
Авторы также рассматривают экви-33валентные преобразования выражений с операцией соединения и последующейвыборкой, которые корректны на ограниченном подмножестве предложеннойрасширенной алгебры, например, при отказе от использования пользовательских весов и ограниченной семантике оценок. В статье также выведено алгебраическое тождество с операцией объединения и выборки, корректное при техже упрощениях модели.В [12] доказывается, что предложенная операция мультимедиа соединенияне коммутативна и не ассоциативна, что накладывает ограничения на оптимизацию запросов на основе рассмотренной алгебры.
Это связано со спецификойрасширенной операции соединения, которая для каждого объекта из первогоаргумента строит набор объектов из второго аргумента, находящихся в егоокрестности по подобию. Тем не менее, авторы предлагают использование коммутативной и ассоциативной операции симметричного соединения и последующей фильтрации и рассматривают примеры оптимизации запросов на основесоответствующих алгебраических равенств.1.2.3.2.
Модели стоимостиРазработка моделей стоимости лежит в основе создания оптимизатора запросов, специфицированных на новом расширенном высокоуровневом декларативном языке [8, 48]. Важно отметить, что разрабатываемые оценки должныучитывать распределенный характер среды выполнения запросов. Несмотря напроработанность этой тематики, модели стоимости для специфических операций, расширяющих реляционную алгебру, и алгоритмов их реализующих, например, в распределенной среде, требуют проектирования и анализа. В [48]рассматривается метод оценки размера результата выполнения операции, основанный на случайных выборках. Модели стоимости, основанные на оценкеселективности операций расширенной алгебры, предложены в [8].Авторы [69] предлагают систему, полностью интегрирующую операцию соединения с поддержкой ранжирования в реляционные базы данных. Системаоснована на расширении алгоритма динамического программирования новымметодом перечисления планов выполнения запросов и их исключения из рассмотрения.
В работе приведена вероятностная модель оценки размера входныхаргументов операции соединения с ранжированием и соответствующая модельстоимости.34В одной из наших работ [20] описана абстрактная расширенная модельстоимости, которая позволяет формализовать и реализовать для последующегоиспользования, связь между количеством вычислительных ресурсов, выделенным на приближенное исполнение операции, и качеством результата. На базерасширенной модели стоимости строилось дальнейшее диссертационное исследование.1.3. Адаптивное выполнение запросовНеобходимость иметь дело с неточностью оптимизации запросов в традиционных системах управления базами данных привела к развитию адаптивныхметодов выполнения запросов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
