Задачи OWL-based поисковой системы и пути их решения

Павлов Дмитрий

Цель работы заключается в устранении критичности процесса поиска в распределенной онтологии. Поставленная цель, ввиду тенденций роста применения технологии Semantic Web, является актуальной и требующей практической реализации.

Введение

За последние несколько лет IT индустрия сильно шагнула в развитии автоматического поиска, сбора и обработки информации. Одним из ведущих направлений этой отрасли является технология Semantic Web[1], продвигаемая W3 консорциумом. Среди последних значительных достижений данной технологии спецификация языка описания онтологий OWL[2]. Вместе с появлением такого мощного инструмента возник ряд практических задач его непосредственного внедрения и применения. Решенными задачами на сегодняшний день являются: визуальные среды разработки онтологии[3,4]; спецификация агентного взаимодействия по средством метаописания механизмов передачи и обработки данных[5]; проверка формальной целостности онтологии[6] и пр. В данной работе предполагается использование этих решений.

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

Цель работы заключается в устранении критичности процесса поиска в распределенной онтологии. Поставленная цель, ввиду тенденций роста применения технологии Semantic Web, является актуальной и требующей практической реализации.

1 Постановка задачи

Изначально онтология предполагается как нечто, что можно разделить на элементы, путем указания ссылок друг на друга. Ввиду практической постановки задачи, условимся, что онтология представлена на языке OWL.

Разделяемая структура рождает задачу поиска элементов при использовании предоставляемых ссылок:

SELECT a FROM uri WHERE resource=»uri#a», (1.1)

где а — элемент онтологии, uri[7] — ссылка на элемент, resource — специфицированный элемент RDF[8].

Помимо простого нахождения элемента онтологии, сразу заложим требования на более глубокий поиск, а именно — поиск элементов эквивалентных данному:

SELECT a FROM * WHERE a=b, (1.2)

где а и b — элементы онтологии.

Также в углубленный поиск должна входить возможность дополнения тройки субъект-предикат-объект, при отсутствии одного из элементов, что тоже является поиском:

SELECT a FROM * WHERE [a, R, b], (1.3)

где [a, R, b] — тройка субъект-предикат-объект, а — один из недостающих элементов тройки.

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

Таким образом, необходимо предложить алгоритм либо ряд алгоритмов онтологического поиска, выполняющие 1.1, 1.2, 1.3, а также их взаимные вариации в условиях распределения данных в сети. Представленные алгоритмы должны базироваться на общих принципах языка OWL и быть обоснованными с точки зрения оптимальности.

2 Онтологический поиск в контексте OWL

Определимся с основными понятиями, которыми мы будем оперировать.

2.1 Сеть

Ont = Σ Stori, i=1,n, (2.1)

где Ont — распределенная онтология, Stori — часть онтологии, находящаяся в i хранилище данных, n — число хранилищ.

Пример топологии сети

Рисунок 2-1 Пример топологии сети

Сеть (Рис. 2-1), в которой функционирует онтология, будем рассматривать как направленный граф, обладающий не всеми дугами. Узлами графа являются хранилища данных, таким образом число узлов — n. Дуги графа — ссылки, которыми обладают хранилища.

Допущение 1. Пусть в графе нет обособленных вершин.

Этим допущением мы исключаем случаи, когда не возможно вернуть наиболее полный ответ, что противоречит условиям поставленной задачи.

Допущение 2. В топологии сети не присутствуют циклы. В случае, если каким-либо путем запрос будет адресоваться узлу, сформировавшему его, он будет игнорироваться.

Дуги между узлами возникают в момент указания внешних ссылок в элементе онтологии. Помимо определения узла-соседа непосредственно из имени документа вводится форсированное объединение, когда известно, что разные документы хранит один и тот же узел. В этом случае в данном узле помещается объект, в котором указан набор пространств имен, обрабатываемых другим узлом.

Таблица 2.1 — Формирование дуг сети.

URI Узел-сосед Элемент
http://www.w3.org/2002/07/owl#Class http://www.w3.org/2002/07/owl class
http://www.w3.org/2001/XMLSchema#float

http://www.w3.org/2001/XMLSchema#string

http://www.w3.org/2001/XMLSchema float

string

rmi://127.0.0.1/1.owl#a

rmi://127.0.0.1/2.owl#b

Форсировано объедине\\нный — localhost a

b

2.2 Поиск

Теперь определимся с непосредственным результатом выполнения глобального поиска, то есть фактическим результатом работы системы, функцией search(Ont, query0).

Определение 1. Search(Ont, query0) возвращает наиболее полно описанную элементарную сущность языка OWL, отвечающую базовому запросу query0.

Под элементарной сущностью OWL мы понимаем класс, свойство либо объект, а под запросом query0 мы подразумеваем один из запросов указанных в 1.1 — 1.3.

Наиболее полное описание достигается только в результате работы с онтологией целиком. Чтобы не решать задачу поиска силами одного сервера обозначим порядок дифференциации нагрузки в рамках отдельных серверов, введем понятие локального поиска local_search(Stori, queryk).

Определение 2. Под локальным поиском мы будем понимать поиск, ограничивающийся ресурсами i хранилища данных.

Введем операцию-обработчик результатов process(Stori, result), где result — результат выполнения функции глобального либо локального поиска. Данная операция отвечает за преобразование результатов локального поиска в каскад запросов к серверам-соседям, узлам к которым ведут дуги от данного узла. По возврату данных от серверов-соседей может вновь инициироваться локальный поиск, но уже с учетом полученной информации.

Ввиду допущений 1 и 2, а также топологии сети, введем возможность перемещения поиска из узла, в котором происходит обработка информации, в узлы-соседи:

Stori ->{Stori1, … Storij}, (2.2)

где j число серверов-соседей активного узла.

Вновь имеем возможность применить глобальный механизм поиска, с центром в каждом из серверов-соседей. Получаем рекурсию, глубина которой для конкретного запроса равна максимальному пути, который можно построить из заданного узла (с учетом допущения 2). Из постановки задачи очевидно, что понятие поиска сразу распадается на три направления:

  • поиск элемента онтологии по ссылке URI (1.1);
  • поиск элемента эквивалентного данному (1.2);
  • поиск недостающего элемента тройки N-Triple[8] (1.3).

Рассмотрим каждое направление в отдельности.

Поиск по ссылке (1.1) — тривиальная техническая задача, в которой, имея имя узла и имя искомого на нем объекта, требуется получить развернутое описание объекта.

Поиск эквивалентного элемента (1.2) осуществляется путем использования стандартных рекомендаций для языка OWL[2].

Заполнение недостающего элемента в N-Triple (1.3) будем решать с помощью механизмов RDQL[9].

Не смотря на разобщенность направлений поиска, они тесно связаны. Рассмотрим взаимодействие механизмов поиска (Рис. 2-2).

search(Ont, [a,R,?] ) = Σ search(Ont, [am,Rn,?] ), m=1,M; n=1,N, (2.3)

где [a, R, ?] некоторый базовый запроса, am эквивалентно a, Rn эквивалентно R, M и N — количество найденных эквивалентностей соответствующему элементу N-Triple.

В 2.3 показано взаимодействие между поиском элементов эквивалентных данному (1.2), когда базовый запрос преобразуется в серию эквивалентных ему, и поиском недостающего элемента тройки (1.3). При формировании, как расширения запроса, так и при поиске недостающих элементов возможно возникает задача поиска по ссылке (1.1). Из сказанного следует, что в данном примере показана логическая связь всех трех элементарных типов поиска.

Взаимодействие механизмов поиска

Рисунок 2-2 Взаимодействие механизмов поиска

3 Межсерверное взаимодействие

В основе межсерверного взаимодействия лежит технология агентного взаимодействия OWL-S[10]. Во-первых, ее использование формализует процесс передачи данных внутри сети, во-вторых, позволяет оставить возможность интеграции системы с внешними пользователями, еще не специфицированными на данном этапе разработки.

Для организации межсерверного взаимодействия специфицируется следующий интерфейс:

  1. функция broad(query) преобразующая запрос в список эквивалентных запросов;
  2. функция local_search(query) создающая описание элемента OWL по заданному запросу;
  3. функция search(query), которая, по сути, является объединением двух предыдущих функций. Ее непосредственно вызывают клиенты.

Используя данный интерфейс, были созданы следующие алгоритмы работы сервера, получившего запрос:

  1. Алгоритм 1, простой: сервер расширяет запрос силами своей (локальной) информации и силами всех серверов-соседей, не отличая собственную информацию от чужой, получая, таким образом, наиболее полное расширение для данной сети. Далее для каждого малого запроса выполняет функцию local_search(query) на всех доступных ресурсах. Все полученные ответы соединяются воедино и возвращаются клиенту;
  2. Алгоритм 2, с повышенным доверием: сервер расширяет запрос, опираясь исключительно на собственную модель, а затем выполняет функцию search(query) для своей модели и моделей серверов-соседей. Все полученные ответы соединяются воедино и возвращаются клиенту.
  3. Алгоритм 3, с транслятором: такой вариант можно назвать гибридным алгоритмом. При локальном расширении запроса используется ряд серверов-соседей исключительно в целях нахождения эквивалентных классов, свойств и объектов. Затем на основании полученной трансляции выполняется функция search(query) для своей модели и моделей серверов-соседей, которые не являются трансляторами.

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

Алгоритм 2 предназначен для случаев, когда каждый из серверов представляет в какой-то степени завершенный ресурс. Таким образом, его область имен, классы и свойства наиболее эффективно применять исключительно к его модели. Скорость выполнения запросов в таком алгоритме выше за счет сокращения числа межсерверных пересылок данных, но качество поиска падает, вследствие того, что часть данных, которые были бы выбраны более широким запросом, утеривается. Таким образом вводим Ограничение 1: ни один сервер такой сети не может не содержать ссылок на сервер, хранящий некоторый объект, эквивалентный данному, иначе данные объекты не будут распознаны как эквивалентные. Такой алгоритм в большей степени подходит Internet поисковикам, которые имеют ссылки на сервера различной принадлежности.

Область применения Алгоритма 3 шире двух первых, так как в условиях разделения информации на описательную и несущую можно использовать алгоритмы, строго предназначенные для каждого конкретного случая. Но создание непосредственно транслятора требует разного рода формализаций, определяющих грань различия структуры от содержания, что достаточно легко решается в каждом конкретном случае.

Важным аспектом оптимизации межсерверного взаимодействия является кеширование результатов в рамках конкретного поиска. Оно заключается в сохранении результатов выполнения каждого конкретного запроса. Благодаря такой организации мы предотвращаем ситуацию зацикливания, облегчаем скорость работы при ветвлении сети (как в узлах 1, 2 и 3 на рис. 2-1), а также значительно ускоряем процесс повторного запроса, который может быть инициирован функцией process.

4 Практическая реализация

Рассмотрим пример используя топологию рисунка 2-1.

Информация узла 1.

[3:Мать ID=»Маша»]

[2:породил rdf:resource=»#Вася»/]

[/3:Мать]

[2:Ребенок ID=»Вася»/]

Информация узла 2.

[owl:class rdf:id=»Родитель»/]

[owl:class rdf:id=»Ребенок»/]

[owl:objectproperty rdf:id=»породил«]

[rdfs:domain rdf:resource=»#Родитель» /]

[rdfs:range rdf:resource=»#Ребенок» /]

[/owl:ObjectProperty]

Информация узла 3.

[owl:class rdf:id=»Мать«]

[rdfs:subclassof rdf:resource=»2#Родитель» /]

[/owl:Class]

[owl:class rdf:about=»2#Родитель«]

[owl:equivalentclass rdf:resource=»4#Parent»/]

[/owl:Class]

Информация узла 4.

[owl:class rdf:id=»Parent»/]

Пусть поступил запрос «Кто Parent Васи?», приведя этот запрос к форме языка запросов получим [?, instanceOf, Parent] и [?, породил, Вася]. Имеем два запроса, обладая информацией по каждому из них мы легко можем сделать пересечение ответов.

Построим модель поиска для первого запроса:

Сервер 1:

Расширение:

Поиск в локальных данных:

Трансляция серверу 2 и 3:

[?, instanceOf, Parent]

0

0

Сервер 2:

Расширение:

Поиск в локальных данных:

[?, instanceOf, Parent]

0

0

Сервер 3:

Расширение:

Поиск в локальных данных:

Трансляция серверу 2 и 4:

[?, instanceOf, Parent]

[?, instanceOf, Родитель] [?, instanceOf, Мать]

0

Сервер 2:

Расширение:

Поиск в локальных данных:

[?, instanceOf, Parent] — отказ в результате кеширования [?, instanceOf, Родитель] [?, instanceOf, Мать]

0

0

Сервер 4:

Расширение:

Поиск в локальных данных:

[?, instanceOf, Parent] [?, instanceOf, Родитель] [?, instanceOf, Мать]

0

0

Результат:

Общее расширение:

Общий поиск:

Решение на повторный поиск:

изменилось расширение

[?, instanceOf, Parent] [?, instanceOf, Родитель] [?, instanceOf, Мать]

0

Сервер 1:

Расширение:

Поиск в локальных данных:

Результат:

Общее расширение:

Общий поиск

[?, instanceOf, Parent] [?, instanceOf, Родитель] [?, instanceOf, Мать]

0

[Маша, instanceOf, Мать]

изменился результат самого поиска

0

[Маша, instanceOf, Мать]

Для остальных серверов работу рассматривать не будем, так как очевидно, что большая часть запросов будут отказом, а остальные ни к чему не приведут.

Построим модель поиска для второго запроса:

Сервер 1:

Расширение:

Поиск в локальных данных:

Результат:

Общее расширение:

Общий поиск

[?, породил, Вася]

0

[Маша, породил, Вася]

изменился результат самого поиска

0

[Маша, породил, Вася]

Дальнейший поиск результатов не изменит, поэтому не будем рассматривать дальнейший ход событий.

Итак «Кто Parent Васи?» — «Маша».

Предлагаемый пример показывает работу только Алгоритма 1, но базовые элементы этого алгоритма присущи всем остальным предложенным алгоритмам и их детальный анализ не дополнит общей картины.

Выводы

  1. В данной статье впервые проводится анализ проблемы организации поиска среди разнесенного в пространстве множества документов OWL. Предложена грань, позволяющая отделить фазу локального и межсерверного поиска, благодаря чему представляется возможным вести оптимизацию использования ресурсов на стратегически разных уровнях работы системы.
  2. В работе тесно интегрированы, как различные новые разработки Semantic Web, так и собственные решения.
  3. Четко сформулирована цель онтологического поиска. Представлен и логически обоснован процесс формирования ответа на простой запрос.
  4. Предложены рекомендации к практическому использованию полученных теоретических результатов в практических приложениях, что определяет практическую значимость выполненной работы.

Литература:

[1] T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. Scientific American, 284(5):34-43, 2001.

[2] D. L. McGuinness and F. van Harmelen. OWL Web Ontology Language Overview. http://www.w3.org/TR/owl-features/ . August 2003. World Wide Web Consortium (W3C) Candidate Recommendation.

[3] Jeremy J. Carroll, Ian Dickinson, Chris Dollin. Jena: implementing the semantic web recommendations. International World Wide Web Conference. pp. 74 — 83, 2004.

[4] W. E. Grosso et al. Knowledge Modeling at the Millennium (The Design and Evolution of Protege-2000). In Proc. of KAW99, 1999.

[5] D. Martin, M. Burstein, O. Lassila, M. Paolucci, T. Payne, and S. McIlraith. Describing Web Services using OWL-S and WSDL. http://www.daml.org/services/owl-s/1.0/owl-s-wsdl.html, October 2003.

[6] Bijan Parsia, Evren Sirin, Aditya Kalyanpur «Debugging OWL Ontologies», In The 14th International World Wide Web Conference (WWW2005), Chiba, Japan, May 2005.

[7] T. Berners-Lee, R. Fielding, and L. Masinter. Uniform Resource Identifiers (URI): Generic Syntax. 1998.

[8] Graham Klyne, Jeremy J. Carroll Resource Description Framework (RDF): Concepts and Abstract Syntax, http://www.w3.org/TR/rdf-concepts/ 2004

[9] Andy Seaborne, RDQL — A Query Language for RDF HP Labs Bristol http://www.w3.org/Submission/2004/SUBM-RDQL-20040109/ 2004

[10] OWL-S Home Page. http://www.daml.org/services/. 2003.

2 Responses to Задачи OWL-based поисковой системы и пути их решения

  1. Павел:

    А что есть ХРАНИЛИЩЕ там содержиться часть концептов(классов) и их экземпляров или это просто набор троек?

  2. тройки — это наборы экземпляров объектов (классов)
    но в хранилищах хранится информация и о концептах(классах) —
    все как в OWL — OWL — экземпляры с соответсвующими классами

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *


Ответить с помощью ВКонтакте: