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

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

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

АгрегированиеОперация агрегирования строит объекты результирующего базового множества из нескольких объектов аргумента операции. Эту операцию можно рассматривать как нечеткую альтернативу и обобщение оператора GROUP BY вSQL запросах, который определяет набор входящих объектов, которые будутсгруппированы в один выходной объект. Помимо группировки объектов на основе точного совпадения значений атрибутов группировки, объекты могут быть55сгруппированы, например, на основе классификации или кластеризации входящих объектов.Формально определим операцию агрегирования:Операцией агрегирования называется операция ∈ O: = 1, параметры включают в себя функцию определения групп ,функцию вычисления оценки принадлежности группе , функцию вычисления оценки объектов в результирующем Q-множестве , функцию построения идентификатора , и функцию определения групп ∀ ∈ Q () ={((), (), ())| = (), = {(, , (, , ))| = (, , ) ∈ , ∈ }}.Определение 2.12.Операция агрегирования строит объекты нового Q-множества из группобъектов аргумента, на основе специфицированных функций-параметров, описывающих принципы группировки объектов.

В результате применения операции агрегирования объекты Q-множества содержат атрибут, также являющийся Q-множеством и представляющий построенную группу объектов исходногоQ-множества. Идентификаторы объектов в результате агрегирования строятсякак суррогаты.2.1.4.6. Группирующее соединениеНедостатком операций соединения и агрегирования является необходимость построения суррогатных идентификаторов. В этом случае, связь междуобъектами, извлеченными из первичных источников и полученными фактамитеряется.Поэтому в алгебре предусмотрена операция группирующего соединения,которая может быть определена как соединение с последующим агрегированием по идентификаторам объектов из первого аргумента.

Фактически это операция сочетает в себе выразительность операций соединения и агрегирования,и эти операции можно рассматривать как частный случай группирующего соединения.Определим формально бинарную операцию группирующего соединения:Определение 2.13. Группирующим соединением называется операция ∈ O:, параметры включают в себя функцию предиката на паре объектов ,функцию вычисления оценки объектов результата на основе оценок объектоваргументов и значения функции предиката , и функцию построения групп=256 ∀ 1 , 2 ∈ Q ( 1 , 2 ) = {(1 , 1 ∪ (), (1 , ))|1 = (1 , 1 , 1 ) ∈ 1 , ={(2 , 2 , (1 , 2 ))|2 = (2 , 2 , 2 ) ∈ 2 }.2.1.5.

АлгебрыОперации, определенные над множеством Q-множеств, могут составлятьалгебры различной выразительной силы. На самом простом уровне реализуетсяпоиск по ключевым словам: алгебра включает в себя фильтры и операции синтеза. Более мощные алгебры строятся с использованием операций соединенияи агрегирования.Предложенная алгебра будет использоваться в работе в качестве целевой,тем не менее методы и алгоритмы, описанные в следующих главах, не привязаны к конкретной алгебре.Основным требованием к алгебре является ее расширяемость, то есть возможность добавления новых операций. Помимо рассмотренных выше операцийполезно включение в алгебру, например, унарных операций сортировки объектов по атрибуту, поиска лучших по оценке или расщепления, которая извлекаетиз Q-множеств объекты вложенных Q-множеств.Также алгебра может быть обогащена с помощью реализации новых функций, которые используются для конфигурации родовых операций алгебры:∙ агрегирования;∙ предиката;∙ построения оценки.Отметим, что эти два вида расширения алгебры различны с точки зренияреализации, но не на концептуальном уровне.2.1.6.

Исполнение алгебраических операцийАлгебраическая операция может быть реализована разными алгоритмамис использованием различных структур данных. В реализации нашей алгебрымы не разделяем родовую операцию алгебры и алгоритмы, ее реализующие, иработаем с отдельными алгоритмами как с отдельными алгебраическими операциями.57Отметим также, что алгебраические операции реализуются как операциинад потоками данных, то есть читают данные из входных потоков аргументови по мере формирования результата (объектов результирующего Q-множества)передают его в выходной поток. Такая реализация позволяет отказаться отпромежуточной материализации результатов вычислений между операциями.2.2. Оптимизация запросовВ этом разделе мы введем понятия необходимые для дальнейшего обсуждения оптимизации запросов, сформулированных в терминах алгебры.2.2.1.

ВыраженияОпределим понятие выражения в алгебре:Множество выражений алгебры E( ) над переменнымиопределяется рекурсивно следующим образом:∙ ∈ E, где ∈ ;∙ ∈ E, где ∈ Q;∙ (), где ∈ O, ∈ E .Определение 2.14.Далее в работе мы также будем оперировать выражениями, в которыхзначения всех переменных определены:Определение 2.15. Выражение алгебры, в котором нет переменных, называ-ется определенным, и множество определенных выражений алгебры E строится рекурсивно следующими правилами:∙ ∈ E, где ∈ Q;∙ () ∈ E, где ∈ O, ∈ E .Для удобства работы с отдельными операциями в выражениях введем следующие обозначения:58Для выражения ∈ E через () обозначим множествовсех его подвыражений; тогда для упрощения выкладок будем использоватьобозначение ∈ (), имея ввиду ввиду корневую операцию выражения, содержащегося в том множестве.Определение 2.16.2.2.2.

Алгебраические тождестваВ алгебре может выполняться ряд алгебраических тождеств, аналогичныхалгебраическим тождествам реляционной алгебры.Выражения 1, 2 ∈ E( ) тождественны (1 ≡ 2), еслидля всех возможных подстановок переменных , Q-множества, получаемыев результате вычисления выражений, равны (по значению).Замена выражения тождественным называется трансформацией.Определение 2.17.Например, (1 , 2 ) ≡ (2 , 1 ) для коммутативной операции синтеза ∈ Oи выражений 1 , 2 ∈ . Примеры алгебраических тождеств в расширенныхалгебрах рассматривались в главе 1.Выражения 1, 2 ∈ E эквивалентны (1 ≡ 2), если Qмножества, получаемые в результате их вычислений, равны (по значению).Определение 2.18.Свяжем понятия эквивалентности определенных выражений и алгебраического тождества.Если для выражений 1, 2 ∈ E существует конечная цепочка трансформаций (с заменой подвыражений переменными и обратно), переводящая 1 в 2, то 1 ≡ 2.Утверждение 2.1.2.2.3.

Запрос и план его выполненияДля любого выражения в алгебре можно построить множество эквивалентных ему на основе алгебраических тождеств.Под запросом будем понимать множество эквивалентных выражений в алгебре, которое может быть представлено одним из них ∈ E.Определение 2.19.59Для запроса ∈ E через () = {| ≡ } обозначим множество плановвыполнения запроса, а отдельное выражение ∈ () будем называть планомвыполнения запроса.2.2.4. КонфигурацияНа выполнение операции может влиять множество параметров, таких какконфигурация вычислителей или специфические параметры вызова алгоритма,реализующего операцию. Например, алгоритм соединения на основе вложенныхциклов может считывать данные из входных потоков порциями, размер которых определяется соответствующим параметром вызова алгоритма. В классическом случае конфигурация включает такие параметры запроса, как напримерзначения констант для сравнения в фильтрах.Для операции ∈ O определим пространство конфигураций (), то есть пространство значений параметров, влияющих на еевыполнение.Операцию ∈ O с конфигурацией ∈ () будем обозначать через ().Определение 2.20.На основе конфигурации операций, составляющих выражение, определимконфигурацию плана выполнения запроса.Для плана выполнения запроса ∈ E его конфигурацияопределяется множеством конфигураций операций егосоставляющих: кон⋃︀фигурацией плана называется функция : () → ∈() () такая, что∀ ∈ () () ∈ ().План выполнения запроса ∈ E с конфигурацией ∈ () будем обозначать через ().Определение 2.22.

Пространство сконфигурированных планов выполнениязапроса ¯ ∈ E обозначим как P(¯) = {(, )| ∈ (¯), ∈ ()}.Определение 2.21.2.2.5. Функция стоимостиДля вычисления результата запроса необходим лишь один план из множества эквивалентных. Для выбора плана используются оценки эффективностиего исполнения, которые позволяют сравнивать планы между собой.60Эффективность плана выполнения запроса зависит от его структуры иэффективности его операций.Определение 2.23.

Для операции ∈ O с конфигурацией ∈ () критериемэффективности называется функция (()) : Q → R.Критерии эффективности оценивают апостериорную стоимость операциив терминах затраченных вычислительных ресурсов, таких как процессорноевремя или объемы ввода/вывода.Оценки эффективности планов строятся на основе оценок эффективностиотдельных операций, участвующих в алгебраическом выражении.Для плана выполнения запроса ∈ E с конфигурацией ∈ () его эффективность по критерию вычисляется как функцияот стоимостей отдельных операций его составляющих, то есть (()) = ({(( ))| ∈ (), = ()}) ∈ R, где - функция агрегирования оценокэффективности операций в плане.Определение 2.24.Для каждого критерия оценки эффективности определен частичный порядок, формализующий относительную эффективность операций по этому критерию. Для разных критериев эффективности отношение порядка может определяться по разному, например, если критерием является время вычислений,то план с меньшей стоимостью предпочтительнее.Для сконфигурированных планов выполнения запроса(1 , 1 ), (2 , 2 ) ∈ P() (1 (1 )) ≺ (2 (2 )), если 1 (1 ) не менее эффективен,чем 2(2), по критерию .Определение 2.25.Эффективность операций (и, следовательно, планов) может измерятьсяодновременно на основе различных критериев, таких как время вычислений,объемы ввода/вывода, процессорное время.Для операции ∈ O с конфигурацией ∈ () функциейстоимости называется функция ¯(()) : Q → R.Определение 2.26.В этой ситуации, рассматривается независимых критериев, каждый изкоторых принимает значения в R.61Если критерий оценки эффективности один, то = 1, и функция стоимости численно выражает значение единственного критерия, например, времявычислений или построения одного объекта из результата.Если критериев эффективности несколько, то на их основе часто можетбыть построен агрегированный критерий, например, как линейная комбинацияисходных.Если > 1, то функция стоимости учитывает сразу несколько независимых критериев оценки эффективности.Для плана выполнения запроса ∈ E с конфигурацией ∈ () его стоимость ¯(()) ∈ R строится как вектор его стоимостейпо каждому из критериев эффективности.Определение 2.27.На пространстве значений функций стоимости должно быть определеноотношение, позволяющее сравнивать стоимость разных операций и выражений.Для сконфигурированных планов выполнения запроса(1 , 1 ), (2 , 2 ) ∈ P() ¯(1 (1 )) ≺ ¯(2 (2 )) в пространстве R , тогда и только тогда, когда ∃ ∈ [1 : ] : ¯(1(1)) ≺ ¯(2(2)).Определение 2.28.Таким образом, если сконфигурированный план 1 (1 ) эффективнее сконфигурированного плана 2 (2 ) хотя бы по одному из критериев, то он эффективнее и по совокупности критериев.

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

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