Диссертация (1149731), страница 11
Текст из файла (страница 11)
Тем не менее, было бы нереальным предполагать существование глобального определения данных для всех возможных запросов,задач и предметных областей.Вопросы, связанные с представлением или отображением локальных схемв глобальную или наоборот ( [98–100]), остаются вне рамок этой работы. Вместоэтого, мы предполагаем, что внешний источник может предоставить информацию о свойствах данных, и объекты анализируемые в сценарии, обладают всеминеобходимыми для исполнения запроса атрибутами.2.1.3.
Q-множестваЦентральным понятием нашей модели является Q-множество.Q-множество это тройка (q,X,S), в которой∙ ∈ - запрос,∙ - базовое множество объектов,∙ : → [0, 1] - функция оценки объектов из множества по запросу, то есть () = (, ).Q-множество (, , ) можно описать множеством объектов с оценками (без привязки к запросу) {(, ) : ∈ , = ()} ≡ {(, , ) : =Определение 2.6.(, ) ∈ , = ()}.Q = {(, , )}Черезбудем обозначать множество всех Q-множеств.Понятие Q-множества инкапсулирует запрос и результат его исполнения,представленный в виде функции оценки. Понятие Q-множества можно рассматривать как обобщение наборов результатов, используемых во многих интерфейсах доступа к данным, таких как JDBC или ODBC. Q-множество также можнорассматривать как нечеткое множество, интерпретируя функцию оценки какфункцию принадлежности объекта множеству.Подчеркнем, что в нашей модели нет никаких предположений о представлении запроса.
В частности, мы не предполагаем, что запрос сформулированна конкретном языке запросов и даже имеет какую-либо явную спецификацию.Таким образом, запросы разных Q-множеств могут быть специфицированы на51разных языках, таких как исходный декларативный язык, SQL или язык поисковых запросов, что позволяет выполнять алгебраические операции, комбинируя разные типы анализа данных в одном сценарии.Заметим, что множество может содержать объекты, атрибутами которых являются Q-множества.Существует два способа получить Q-множество: Q-множество извлекается из первичного источника данных или получается в результате исполнениянекоторой операции (или выражения из нескольких операций) алгебры, определенной над множеством Q ниже в подразделе 2.1.4. Q-множества, извлекаемыеиз первичных источников, могут быть рассмотрены как обобщение хранимыхтаблиц в традиционных СУБД.2.1.4.
Алгебраические операцииНад множеством Q можно определить алгебраические операции, наборыкоторых будут порождать алгебры различной выразительной силы.Операция алгебры определяется следующим образом: : × Q → Q, где множество параметров операции, арность операции.Через O будем обозначать множество всех операций.Определение 2.7.Отметим, что многие операции алгебры частичные, то есть могут бытьприменены только на подмножествах Q , определяемых семантикой конкретной операции. Также операции будут опираться на наличие специфических атрибутов объектов, внутри анализируемых Q-множеств.Параметры вызова операции описывают конфигурацию операции, например, они позволяют специфицировать предикат в операции соединения илифункцию подобия при поиске по образцу.
Набор параметров специфичен длякаждой отдельной операции. В дальнейшем мы будем опускать в выраженияхпараметры вызова операции, считая их ее неотъемлемой частью.2.1.4.1. Первичная выборкаКак уже говорилось Q-множества могут быть получены из некоторого первичного источника данных, например, из файла, результата выполнения SQLзапроса к базе данных или других информационных ресурсов.52Определим родовую операцию первичной выборки, которая инкапсулируетпроцесс построения Q-множества из источника данных.Первичной выборкой называется операция ∈ O: = 0,параметры специфицируют первичный источник данных и процесс построения Q-множества из него.Определение 2.8.2.1.4.2.
ФильтрыОпределение 2.9. Фильтром называется операция ∈ O: = 1, параметрывключают в себя функции вычисления значений оценки и построениянабора атрибутов , ∀ ∈ Q () = {(, (), (, ))|(, , ) ∈ }.Фильтры представляют собой унарные операции, в которых анализ объектов Q-множества не зависит от остальных объектов в нем, и сохраняетсяидентификация объектов.Простые фильтры возвращают Q-множество, построенное над базовыммножеством аргумента операции. Отметим, что простые фильтры сохраняютидентификаторы объектов. Простые фильтры пересчитывают оценки отдельных объектов, и новая оценка объекта может зависеть только от значений атрибутов этого объекта и ограниченного числа дополнительных параметров операции.
Следовательно, фильтры могут быть выполнены на потоке объектов безматериализации или временного хранения (любой части) Q-множества. Примером простого фильтра может быть операция дискретизации, которая преобразует нечеткое Q-множество в точное заменой высоких оценок значением 1 инизких — 0. Иными словами операция отбрасывает предположительно неважные объекты с низкими оценками в Q-множестве.Несколько иной вид фильтров можно использовать для создания дополнительных атрибутов объектов. Как правило, значения новых атрибутов вычисляются на основе внешних библиотечных функций.
Несмотря на тот факт, чтотакие фильтры могут быть вычислительно дорогими, они также не требуютматериализации и могут быть реализованы как потоковые.2.1.4.3. Теоретико-множественные операцииОпределим родовую операцию синтеза, которая будет являться расширением теоретико-множественных операций, позволяя реализовать, например,53теоретико-множественные операции на нечетких множествах и их аналоги.Традиционные теоретико-множественные операции, например, в реляционной алгебре требуют, чтобы аргументы имели один тип.
В нашей модели нетстрогой типизации, поэтому предполагается, что аргументы операции синтезапостроены на базовых множествах с общей системой идентификации объектов.Также все атрибуты элементов базовых множеств аргументов операции будутвключаться в состав атрибутов объектов базового множества результата. Отметим также, что операция синтеза сохраняет идентификацию объектов.Формально определим бинарную операцию синтеза:Операцией синтеза называется операция ∈ O: =2, параметры включают в себя функцию вычисления оценки объектов врезультате применения теоретико-множественной операции , ∀1, 2 ∈ Q( 1 , 2 ) = {(, 1 ∪ 2 , (1 , 2 ))|(, 1 , 1 ) ∈ 1 , (, 2 , 2 ) ∈ 2 }.Определение 2.10.Специфические операции синтеза на основе родовой определяются функцией вычисления оценки, которая задает метод вычисления новой оценки объекта на основе его оценок в аргументах операции.
Функция вычисления оценки (и другие аналогичные функции) не возвращает ненулевую оценку, исходя из нулевых исходных оценок, что позволяет в реализации не материализовать объекты Q-множеств с нулевыми оценками. Специализацию операциисинтеза определяет функция вычисления оценки, так функция произведения((1 , 2 ) = 1 * 2 ), например, позволяет реализовать произведение нечеткихмножеств.Многие алгебраические свойства операции синтеза, например, коммутативность, следуют из соответствующих свойств функции вычисления оценки, аименно симметричности.Большинство специализаций операции синтеза коммутативны, и могутбыть как бинарными, так и принимать большее число аргументов. Многие изважных специализаций операции синтеза не ассоциативные, и многоместнаяоперация не может быть выражена через бинарные операции синтеза.
Например, операция синтеза с функцией вычисления оценки (1 , 2 ) = 1 не коммутативна, поскольку перестановка аргументов операции приводит к другим оценкам объектов в результирующем Q-множестве. Многомерную операцию синтезас функцией оценки (1 , ..., ) = (1 , ..., ) нельзя представить в виде выражения, составленного из − 1 бинарной операции с той же функцией оценки.542.1.4.4. СоединениеРодовая операция соединения строится как обобщение тета-соединения реляционной модели.Формально определим бинарную операцию соединения:Операцией соединения называется операция ∈ O: = 2, параметры включают в себя функцию предиката на паре объектов , функцию вычисления оценки объектов результата на основе оценок объектов-аргументов и значения функции предиката , функцию построения идентификатора , ∀1, 2 ∈ Q (1, 2) = {((1, 2), 1 ∪2 , (1 , 2 , (1 , 2 )))|(1 , 1 , 1 ) ∈ 1 , (2 , 2 , 2 ) ∈ 2 }.Определение 2.11.Определение соединения предполагает использование (нечеткой) функциипредиката над атрибутами объектов в аргументах операции.
Значение этойфункции используется в качестве дополнительного компонента при вычислении оценки нового объекта. Таким образом, оценка объектов в результате операции соединения зависит от 3 факторов: входящих оценок объектов и значенияфункции предиката. В зависимости от предиката, на основе родовой операциисоединения можно выразить традиционное точное соединение, пространственное соединение, соединение по подобию, или нечеткое соединение.Идентификаторы объектов в результате соединения строятся как суррогаты на основе исходных идентификаторов или генерируются функцией построения идентификаторов независимо.Как и в реляционной алгебре, родовое соединение является избыточным иможет быть выражено как прямое произведение с последующей фильтрацией.Тем не менее, знание предиката позволяет использовать более эффективныеалгоритмы реализации операции, чем вычисление произведения.2.1.4.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
