Диссертация (1149731), страница 24

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

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

Это позволяет во многих случаях просто реализовывать новые трансформации путем конфигурациибазовых.5.4.2. Модели стоимостиПоскольку эффективная оптимизация запросов основана на качественныхмоделях стоимости операций (определения 2.29 и 2.30 в главе 2), архитектурадолжна поддерживать определенные пользователем модели стоимости операций, позволять настраивать модели стоимости базовых операций и определятьновые для расширений.Модель стоимости операции (интерфейс 4) реализует методы evaluateCostи evaluateStat, которые принимают на вход параметры вызова и статистикиаргументов операции и позволяют оценить, соответственно, стоимость выполнения операции и статистики результата.5.4.3.

Модели качестваПри оптимизации запросов, допускающих контролируемое приближенноеисполнение, система опирается на модели качества (определение 2.38 в главе 2),129Интерфейс 4 Интерфейс модели стоимостиi n t e r f a c e CostModel {d o u b l e e v a l u a t e C o s t (Map pars , Map [ ] s t a t s ) {// r e t u r n o p e r a t i o n c o s t e s t i m a t i o n// based on o p e r a t i o n c a l l p a r a m e t e r s p a r s// and arguments s t a t i s t i c s s t a t s ;}Map e v a l u a t e S t a t (Map pars , Map s t a t s ) {// r e t u r n e s t i m a t i o n o f r e s u l t s t a t i s t i c s ;}}описывающие связь между вычислительными ресурсами, выделенными на приближенное выполнение операции, и качеством результата.Модель качества (интерфейс 5) реализует метод evaluateCostQuality, который по неизменяемым параметрам вызова и статистикам аргументов операции вычисляет кусочно-линейное представление зависимости между выделенным количеством вычислительных ресурсов и качеством результата, и методmapCostQuality, который определяет параметры приближенного вызова операции на основе определенных условий на ее выполнение (количество вычислительных ресурсов, ожидаемое качество результата или их сочетание).Интерфейс 5 Интерфейс модели качестваi n t e r f a c e QualityModel {L i s t e v a l u a t e C o s t Q u a l i t y (Map pars , Map [ ] s t a t s ) {// r e t u r n p i e c e −w i s e l i n e a r r e p r e s e n t a t i o n// o f o p e r a t i o n q u a l i t y model// based on known p a r s and s t a t s ;}Map mapCostQuality(Map pars , Map [ ] s t a t s , d o u b l e r e s o u r c e s , d o u b l e q u a l i t y ) {// r e t u r n p a r a m e t e r s o f approximate o p e r a t i o n e v a l u a t i o n ;}}1305.4.4.

ОперацииРасширяемость алгебры реализуется в архитектуре системы с помощьюбиблиотеки операций. В этом разделе обсуждаются ее детали и основные классыопераций: первичной выборки, унарные, и бинарные.5.4.4.1. Библиотека операцийБиблиотека операций хранит множество алгебраических операций и всесвязанные с ними структуры. Для каждой операции библиотека операций хранит:∙ Отображение вызова операции внутри системы в вызов ее непосредственного исполнения на вычислителе;∙ Модель стоимости;∙ Модель качества;∙ Релевантные трансформации с участием операции.Каждый алгоритм, реализующий ту или иную алгебраическую операцию,например, соединение методом вложенных циклов или слиянием сортированных списков, регистрируется в библиотеке операций как отдельная операция.Для добавления новой операции в библиотеку необходимо также добавить соответствующие модели стоимости и качества и трансформации.Конкретные операции алгебры могут быть сконфигурированы различными параметрами, например, операция выбора лучших объектов использует параметр, определяющий число объектов, которое необходимо извлечь; операцияфильтра часто определяется соответствующими функциями вычисления значений оценки и построения набора атрибутов; а операция первичной выборкиполучает параметры, определяющие протокол доступа к данным.С точки зрения архитектуры множество алгебраических операций можноразделить на три основных класса: операции первичной выборки, унарные ибинарные.При расширении алгебры новые операции из любой из трех групп должныреализовывать предопределенный в архитектуре системы интерфейс соответствующей группы или являться конфигурацией базовой реализации.131Параметры обработчиков данных и функций, конфигурирующих базовуюреализацию, извлекаются из параметров вызова операции, передаваемых в виде отображения имен параметров на их значения.

В этом случае интерфейсбазовой реализации будет до некоторой степени универсальным, и обработчикиданных смогут работать с различными наборами специфических параметров.Все операции (интерфейс 6) реализуют метод call, который принимает параметры вызова и потоки, представляющие аргументы (число аргументов операции определяется ее арностью), и возвращает результат в виде потока.Интерфейс 6 Интерфейс операцииi n t e r f a c e Operation {I t e r a t o r c a l l (Map pars , I t e r a t o r [ ] a r g s ) {// r e t u r n i t e a r t o r t o stream o f o p e r a t i o n c a l l r e s u l t ;}}В следующих разделах обсуждаются детали реализации операций разныхклассов и приведен псевдокод процессов генерации потока, представляющегорезультат выполнения операции (псевдокод 7,8,9).5.4.4.2.

Операции первичной выборкиРабота с первичными источниками данных осуществляется через операции первичной выборки без аргументов. Например, если первичный источникданных это СУБД, то в системе может быть реализована операция первичнойвыборки, которая в качестве параметров получает информацию необходимуюдля установления соединения с СУБД и SQL запрос, описывающий извлекаемые данные.В архитектуре системы предусмотрена базовая реализация операции первичной выборки. Она может быть сконфигурирована различнымипроцессора-ми извлечения данных для построения специфических реализаций этого классаопераций.Процессор извлечения данных при каждом вызове возвращает объект данных до тех пор, пока все данные не будут извлечены из первичного источника.Базовая реализация операции первичной выборки вызывает процессор извлечения данных до тех пор, пока последний возвращает новые объекты и перена-132правляет собранные объекты в выходной поток.Псевдокод 7 описывает взаимодействие базовой реализации операции первичной выборки с процессором извлечения данных.Псевдокод 7 Операция первыичной выборкиInput: Параметры вызова операции pars.Output: Поток с результатом выполнения операции out.extr=InitilaizeExtractor(pars)out=InitilaizeOutput()loopobj = extr.get()if obj is not empty then out.put(obj)end ifend loopДля расширения алгебры новыми операциями первичной выборки можно реализовать новый процессор извлечения данных и зарегистрировать его всистеме.

После этого новая операция первичной выборки может быть созданакак конфигурация базовой реализации новым процессором извлечения данныхи зарегистрирована в библиотеке операций.5.4.4.3. Унарные операцииАрхитектура системы поддерживает базовую реализацию унарной операции, которая конфигурируетсяунарным обработчиком данных. Базовая реали-зация унарной операции читает объекты из входного потока по одному, асинхронно вызывает унарный обработчик данных, и по мере готовности результатов вычислений перенаправляет объекты в выходной поток.Унарный обработчик данных реализует 2 метода: put, get.

Метод put принимает объект и обрабатывает его определенным образом, например, добавляетновый атрибут или вставляет объект во внутренний список объектов, отсортированный по оценкам. Метод get возвращает результаты вычислений (объекты)по одному, если они доступны в момент вызова метода.Псевдокод 8 описывает взаимодействие базовой реализации унарной операции с унарным обработчиком данных:Структуру и поведение унарной операции можно проиллюстрировать напримере агрегирования. Процесс агрегирования моет быть разбит на 4 унарныеоперации:133Псевдокод 8 Унарная операцияInput: Параметры вызова операции pars, поток аргумента операции arg.Output: Поток с результатом выполнения операции out.up=InitilaizeUnaryProcessor(pars)out=InitilaizeOutput()loopobj = arg.get()if obj is not empty then up.put(obj)end ifend looploopobj = up.get()if obj is not empty then out.put(obj)end ifend loop∙ операция группировки определяет, как объекты должны быть сгруппированы, то есть добавляет метку группы каждому объекту;∙ операция агрегирования строит новые объекты, представляющие группы,на основе входящих объектов с метками группы;∙ операция вычисления оценки группы оперирует с объектами, представляющими группы, и вычисляет для них оценки по определенным правилам;∙ операция вычисления агрегата получает на вход объекты, представляющие группы, и обогащает их новым атрибутом (агрегатом) вычисленнымна основе объектов в этой группе, например, суммой значений некоторогоатрибута.Все эти унарные операции могут быть определены как специфические конфигурации базовой реализации различными унарными обработчиками данных.5.4.4.4.

Бинарные операцииБинарные операции получают объекты из двух входных потоков и возвращают по мере готовности объекты результата в выходной поток.Архитектура системы поддерживает базовую реализацию бинарной операции, основанной на вычислении декартова произведения аргументов операции.134Базовая реализация конфигурируетсяфункцией предиката, которая принима-ет пару объектов в качестве аргументов и возвращает объект построенный наоснове этой пары вместе с вычисленной для него оценкой.

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

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