Диссертация (1149731), страница 6
Текст из файла (страница 6)
Авторы предлагают несколько альтернативныхрасширений реляционной алгебры, позволяющих учитывать ранжирование иоценивание объектов. Обогащения набора операций последовательно усложняют модель и расширяют класс запросов, выразимых в терминах этой алгебры.Одно из предложенных в [7] расширений основано на базовой системе операций, работающих со списками: выборка, соединение, объединение, разностьи сортировка - и позволяющих учитывать упорядоченность кортежей относительно их рангов и оценок.Расширение следующего уровня основано на использовании операции поиска лучших объектов. Такая алгебра позволяет специфицировать в запросеколичество объектов в результате, что существенно в задачах информационного поиска, где пользователя, как правило, интересуют не все объекты, удовлетворяющие некоторым условиям, а лишь несколько лучших.26Еще одно расширение алгебры основано на поддержке рангов и оценоквнутри базовых операций.
Примером такой расширенной операции может служить операция объединения, которая строит оценку объекта результата на основе его оценок в исходных списках.Также в [7] рассматривается возможность применения пользовательскихопераций оценивания и ранжирования в качестве расширения базовой алгебры.
В представленной работе обсуждаются в первую очередь не конкретныерасширения реляционной алгебры и их применимость в контексте декларативных запросов на стыке традиционных баз данных и информационного поиска,а возможные пути развития алгебр данного класса и возникающие исследовательские проблемы.Алгебра на основе понятия подобия, формализующая язык запросов кмультимедиа данным, вводится в [8]. Как и в других подходах, предлагаемая алгебра может быть использована для выражения сложных запросов, сочетающихв себе различные интерпретации оценок подобия и алгоритмы их вычисления.В алгебре выделены следующие операции: соединение, слияние, разность, выборка и отображение. В основе алгебры лежит специфическая модель данных,а именно множество метрик подобия между объектами. Внутри алгебры применение операций к метрикам подобия позволяет формировать новые метрики.Авторы также рассматривают внешнюю оболочку над предложенной алгеброй,которая позволяет формулировать запросы в терминах расширенной реляционной алгебры.В отличие от большинства систем основанных на поиске по подобию, гдепонятие подобия между объектами жестко зафиксировано, предложенный в [8]подход позволяет комбинировать разные реализации функции подобия внутри одной алгебры.
Такое расширение позволяет формулировать и выполнятьзапросы к хранилищам данных разного типа, например, в ситуации, когда обрабатывается коллекция изображений с текстовыми аннотациями.Алгебра, являющаяся расширением реляционной алгебры на множествонечетких отношений, представлена в [9]. Предложенная формальная системаопераций позволяет формулировать запросы к нескольким хранилищам мультимедиа данных.
В качестве целевого класса сценариев анализа данных рассматриваются запросы к нескольким наборам Web-страниц с оценками, характеризующими их релевантность определенной теме. Алгебра поддерживает вы-27борку по подобию (поиск страниц на определенную тему), взвешенное соединение (поиск страницы на одну тему из двух источников при условии, что одинисточник имеет большую степень важности для пользователя), выбор лучшихобъектов (поиск лучших страниц на заданную тему) и их комбинации. Авторы определяют нечеткие реализации операций выборки, проекции, соединения,объединения, разности и операции выбора лучших объектов.В [10] предложена алгебраическая модель над нечеткими отношениями наоснове операций выборки, проекции, объединения, соединения, разности, переименования, булевой разности, пересечения, поиска лучших, выборки по порогу на значение оценки.
Модель поддерживает пользовательские предикаты ифункции оценки, различные подходы к интеграции оценок объектов. Некоторые операции работают с весами, позволяющими пользователю выражать желаемую степень влияния различных подзапросов на конечный результат. Авторыприводят несколько примеров запросов к хранилищу биометрических данных,демонстрирующих полезность и применимость разработанной алгебры.Расширение реляционной алгебры RankSQL [48] нацелено на эффективное выполнение запросов на поиск лучших объектов в реляционных системахуправления базами данных.
Кортежи в модели обладают рангами и обрабатываются в порядке согласованном с ними. Предложенная алгебра основана нановых операциях и расширениях стандартного набора операций реляционнойалгебры, поддерживающих ранжирование. В расширенную алгебру входят следующие операции: ранжирование, выборка, объединение, пересечение, разностьи соединение. Операции поддерживают ранжирование объектов, то есть формируют новые ранги на основе исходных, но не позволяют использовать нечеткиепредикаты.
При построении ранга кортежа по нескольким предикатам операцииопираются на фундаментальный принцип ранжирования и используют верхниеоценки на значение нового ранга.Алгебра, предложенная в [11], расширяет классическую реляционную модель, включая нечеткие операции и пользовательские веса. Авторы формальноопределяют декларативный язык запросов, который сочетает обработку неточных оценок объектов с традиционным реляционным исчислением на доменах.
Вязык также вводятся нечеткие кванторы. Авторы рассматривают задачу отображения реляционного исчисления с подобием на алгебру на основе подобия иразличают доменно зависимые и независимые запросы. В предложенной алгеб-28ре поддерживаются взвешенные конъюнкции и дизъюнкции на основе расширенной формулы введенной в [49,50]. Набор алгебраических операций представленный в [11] включает в себя проекцию, объединение, пересечение, разность,произведение, и соединение.Специфический набор алгебраических операций на основе подобия дляобработки изображений, представленных векторами признаков, в мультимедиахранилищах предложен в [12].
Алгебра очень тесно привязана к задачам анализа и поиска изображений, например, операция выборки семантически являетсяоперацией поиска изображений подобных заданному в некоторой окрестности.Предложенная алгебра позволяет использовать нечеткие предикаты на основеподобия векторов признаков изображений, но не поддерживает оценок объектов.
Важно также отметить, что новые операции рассматриваются независимоот стандартных операций реляционной алгебры, то есть не являются их расширением.В работе [13] предлагается язык запросов, являющийся расширением SQLи позволяющий формулировать сложные запросы на основе подобия. Авторывыделяют классы функций над типами данных: функции расстояния, функциисравнения и экстракторы, которые преобразуют объекты одного типа в объектыдругого. В статье не приводится полный список операций алгебры, но предполагается, что в дополнение к стандартным реляционным операциям выборки исоединения, система поддерживает различные виды поиска на основе подобия.Большинство предлагаемых алгебраических моделей [8, 9, 11, 48] являются расширениями реляционной алгебры. Этот факт позволяет естественнымобразом интегрировать их в традиционную реляционную модель и применятьнекоторые стандартные методы оптимизации точных запросов.В работе [51] представлена математическая модель спецификации в запросах предпочтений, определяемых как строгие отношения частичного порядка намножестве атрибутов.
Авторы формализовали процесс индуктивного построения составных предпочтений. Алгебра предпочтений, разработанная авторами [51, 52], делает возможным разбиение сложных предпочтений на простые иприменение алгоритмов на основе метода "разделяй и властвуй". Предложенная модель позволяет расширить такие традиционные языки запросов как SQLи XPath возможностью спецификации предпочтений [52].291.2.2. Приближенное выполнениеРасширенные модели данных, основанные на понятии подобия, и операции, учитывающие ранги и оценки объектов, позволяют не только производитьболее сложные виды обработки данных, но и расширяют сферу применимостиприближенного выполнения запросов.В современных задачах анализа и поиска данных точное выполнение запросов очень часто оказывается бессмысленным из-за неточностей в исходныхданных и в отображении пользовательской потребности в запрос.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
