Организация поиска в Semantic Web

Часть первая. Была написана ночью после долгого учебного и рабочего дня.

Поисковик уже существует

В общем-то есть уже поисковая система в SW — проект swoogle.

Посмотрите обязательно «Swoogle Web Services». (Естественно, на английском, но будет понятно всем, кто знает термины Semantic Web).

Оказывается, что за громким названием скрывается что-то не совсем понятное. Когда я узнал о swoogle, то сразу же захотел что нибудь с помощью него найти. Причем, непременно, что-нибудь токое, что не смог бы найти в Яндексе («Нужная мне информация наверняка теряется в куче мусора нерелевантаной информации» — подобные вещи пишут во многих SW агитках).

И вот я перехожу на страницу поиска Swoogle. Остаюсь один на один со строкой поиска и выбором среды поиска. Набираю «russia» и выбираю поиск «в документах».

Не понимая, что должен вернуть Swoogle, но по прежнему ожидая от него чуда, нажимаю на «Swoogle Search». Жду и получаю результат.

Результат появился а чудо не произошло :-)

Через несколько минут таканья по ссылкам я понял, что вообще не знаю что искать в swoogle и вообще что искать в Semantic Web.

А ответ будет интересный — в swoogle вы не найдете ничего больше, чем в обычном поисковике.

Swoogle осуществляет поиск по тексту SW документов. Да, он позволяет, например, найти все документы, которые используют онтологию X или найти документы, которые описывают ресурс Y. Верх возможностей swoogle — найти триплеты, которые описывают некий ресурс Z и класс, который является наследником класса W.

Т.е. по сути Swoogle просто индексирует SW документы.

Всё. Ничего больше от swoogla вы не получите. Вот такой Semantic Web поисковик. Хотя, и эти, на первый взгляд, скромные возможности нам могут пригодиться. Жалко только, что результат запроса возвращается в виде HTML. Ну детский сад какой-то. Вроде в 21 веке живем. Ну да ладно. Если прижмет и HTML будем обрабатывать. (Хотя, может я что-то в руководстве недочитал).

Идем дальше.

Что мы хотим?

Swoogle мне не подошел. Тогда что-же я хочу?

А я хочу ввести в поисковике «Какой e-mail у Д. Буша?» и получить результат:

1. bush@hotmail.com
   (www.usa.gov)
   
2. dbush@president.gov
   (www.president.gov)
   
   ...

Или ввести «Имя внука Ярослава Великого» и получить ответ

1. Святослав
   (www.history.ru)
   
2. Мстислав
   (www.russia.info, www.referat.ru)
   
   ...

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

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

Например, он запустит синтаксический анализатор и преобразует наши запросы в SPARQL запросы:

SELECT $result
WHERE
{
    $name   rdfs:label "имя" .
    $email  rdfs:label "e-mail" .

    $x $name  "Д. Буш" .
    $x $email $result .
}


SELECT $result
WHERE
{
    $name        rdfs:label "имя" .
    $isGrandSon  rdfs:label "являться внуком" .

    $x $name  "Ярослав Великий" .
    $result $isGrandSon $x .
}

Конечно же, запросы будут не такими простыми, но главное понять сам принцип — в любом случае мы перейдем на SPARQL или любой другой язык запросов к RDF.

Теперь наш поисковик должен эти запросы выполнить и передать нам результат.

Такой «наивный» подход к сценариям поиска характерен только для первой части статьи. Во второй части мы увидим, что помимо синтаксического анализатора возможны и даже намного более необходимы и менее искусственно-интелектуальные (а значит, — более надежные) прослойки между событиями на поведения пользователя и непосредственно SPARQL-запросами.

Описание принципа работы синтаксического анализатора не входит в мои задачи. В этой же статье мне хотелось объяснить принцип работы сервиса, который обрабатывает SPARQL запросы.

Что нам нужно?

Поставим такую цель: создать сервис, который будет выполнять данный SPARQL запрос ко всем документам, которые известны нашей поисковой системе.

Смешной вариант: Берем Arq и создаем список url. Теперь по очереди вызываем Arq для каждого ресурса (а в хорошей поисковой системе будет зарегистрирована не менее 500 тысяч ресурсов). Т.к. большинство ресурсов по нашему SPARQL запросу ничего не будет возвращать, то для формирования первых 10 результатов запроса пользователю придется ждать месяца три :-)

Вариант №2: Теперь серьезно. Единственное решение, — это индексация. Она необходима для того, чтобы выполнять SPARQL запросы только к тем ресурсам, которые могут вернуть результат.

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

Приведу пример. (Как я представляю себе индексацию в Semantic Web):

Таблица, которая индексирует субъекты:

...
http://www.misha.ru/blog	описан в	http://www.misha.ru, http://www.blogs.ru, http://www.fi.ru/~verenko
http://www.misha.ru/articles	описан в	http://www.misha.ru, http://www.history.ru/sw, http://www.semanticweb.ru/
...

Что означает, например, что где-то в документе http://www.fi.ru/~verenko есть триплет

<http://www.misha.ru/blog> somePredicat someObject.

Для тех, кто еще не понял: допустим, в нашем SPARQL запросе есть такая строка:

<http://www.misha.ru/blog> $y $z .
<http://www.misha.ru/blog> $x "20" .

Тогда запрос этот мы можем отправлять только на те ресурсы, которые указаны в таблице «Предикаты» справа от ячейки <http://www.misha.ru/blog>.

Т.е., в нашем случае, только на 3 ресурса (!). Все остальные все равно вернут пустой результат.

А 3 — это уже не 500000.

Получили задачу, которую необходимо решить для достижения цели:

Индексация Semantic Web документов

Идеальная система

У нас существует таблица A (n x 4)

n = summ(L(D_i)); i=1..m

L(D) — количество уникальных триплетов в документе d
D_i — i-й документ, зарегистрированный в нашей системе
m — количество документов, зарегистрированных в системе

Таблица выглядит так:

документ     субъект     предикат     объект
   d₁           s₁           p₁          o₁
   d₂           s₂           p₂          o₂
   ...
   d_n           s_n           p_n          o_n

где
d_j — некоторый url (чаcтный случай uri)
s_j, p_j — некоторые uri
o_j — uri или литерал
j = 1..n

И существует возможность подачи запросов к этой таблице:

Пример (на несуществующем языке, очень похожем на SPARQL):

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT $x
WHERE
{
    $doc $y foaf:name "Д. Буш" .
    $doc $y foaf:email $x .
}

Этот запрос позволяет искать по двум шаблонам триплетов в одном документе.

Также существует возможность поиска в разных документах:

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT $x
WHERE
{
    $doc1 $y foaf:name "Д. Буш" .
    $doc2 $y foaf:email $x .
}

По сути мы переходим от триплетов к тетрадам (наборам из четырех компонент).

T_j = (d_j, s_j, p_j, o_j) — j-я тетрада нашей системы.
j = 1..n

Соответственно и компонентой запроса теперь становится шаблон тетрады.

Причем идеальная система находит все решения любых шаблонов тетрад с нулевой скоростью.

Реализация идеальной системы

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

И тут на сцене появляются «RDF-репозитории», но о них в следующей части статьи (через несколько дней).

Вторая часть. Спасибо всем, кто ждал.
Когда-нибудь здесь не будет орфографических ошибок, появится возможность комментировать статьи, etc. Но пока это не так.

Репозитории

Что такое репозиторий RDF?

В общем, репозиторий как ч. ящик можно определить так: Аппарат (в широком смысле слова), выполняющий SPARQL-запросы и расширенные SPARQL-запросы с определённым качеством.

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

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

За счет чего же осуществляется высокая скорость выполнения SPARQL-запросов?

За счет того, что используемые структуры хранения rdf-данных оптимизированны под обслуживание SPARQL-запросов.

В самом распространённом на сегодняшний день репозитории Sesame используются B-деревья (читается как Б деревья, т.е. не минус, а просто дефис).

А вот в экспериментальном репозитории YARS (Yet Another RDF Store) для этого используются B+ деревья через BerkeleyDB (читается как Б плюс деревья). Причем в своей известной статье «Optimized Index Structures for Querying RDF from the Web» авторы YARS утверждают, что их репозиторий в среднем быстрее обрабатывает SPARQL-запросы. Это действительно так, но, при этом, сама база данных может физически занимать в несколько раз больше места, чем БД с аналогичными данными в том же Sesame.

Я с командой товарищей сейчас пытаюсь обуздать репозиторий от IBM — BOCA.

В определении ещё упоминаются расширенные SPARQL-запросы. На самом деле, иногда используется не чистый SPARQL. Большинство создателей репозитория поддерживают его, но рекомендуют пользоваться их собственным языком запросов. Например, в Sesame, это — SeRQL, основанный на SPARQL.

Идем дальше: понятие контекста.

Контекст — это и есть та четвертая компонента, о которой говорилось в первой части статьи. Т.е. во всех репозиториях хранятся четверки
c (context), s (subject), p (predicate), o (object)
Потом к ним осуществляют запрос и всё хорошо.

Если кто ещё не понял, объяснюна пальцах:

Есть 1000 документов в сети. Мы хотим осуществить к ним запрос. Если быдем осуществлять соединение и передачу данных по сети во время обслуживания запроса, то велика вероятность того, что время отклика на запрос не будет нас удовлетворять (ну просто ответ будет формироваться несколько десятков минут, что, естественно, неприемлимо).

А мы возьмем и заранее скачаем эту тысячу документов к себе в локальную базу данных.

Хозяйке на заметку: Естественно, надо будет следить, чтобы локальный документ был точной копией документа в сети. Для этого можно придумать множество способов. Вот например, самый простой из них, — это смотреть на HTTP-заголовок документа. По идее, там должен быть указан его срок жизни. Незадолго до того, как этот срок истечет документ опять надо скачать в свою локальную БД репозитория; посмотреть срок жизни, etc.

Воооот. Скачали мы значит много-много документов, которые содержат много-много триплетов. Ну насчет (s, p, o) всё понятно. Это триплеты, это мы знаем. А чем заполнять context.

Те, кто читал первую часть статьи уже всё поняли. Объясним всем остальным:

Всё очень просто. Context — это контекст. А что у нас является контекстом? Правильно, — документ. А что является уникальным именем документа в сети, правильно — URL. Т.е. четвертую компоненту заполняем url-кой документа из сети.

Ладно, после примера всем станет понятно.

Рассмотрим для двух гипотетических документов:
http://1.su/p и
http://2.ru/rdf

Пусть оба отдают rdf.

Допустим, 1.su/p отдает по http-запросу следующее:

@prefix : <http://1.su/p#> .
@prefix ont: <http://1.su/ont/> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#"> .
:preved ont:contents :medved;
        rdfs:label "Превед".

а 2.ru/rdf это:

@prefix : <http://2.ru/rdf/>.
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#">
:pesok rdfs:label "песок" .

Мы оба этих документа скачиваем, и кидаем в репозиторий. После этого в нём хранится следующее (http:// я опустил, чтобы нагляднее было):

с	s	p	o
1.su/p	1.su/p#preved	1.su/ont/contents	1.su/p#medved
1.su/p	1.su/p#preved	www.w3.org/2000/01/rdf-schema#label	"Превед"
2.ru/rdf	2.ru/rdf/pesok	www.w3.org/2000/01/rdf-schema#label	"песок"

На самом деле подобные таблицы обычно содержат сотни тысяч строк.

Ну всё, теперь запросы будут выполняться очень быстро, потому что все триплеты лежат в локальном пространстве по отношению к процессу, обслуживающим запрос. Реально менее чем за секунду просмотреть тысячи строк подобной таблицы БД, тем более, что ещё может использоваться и разнообразное кеширование.

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

Допустим, есть такие данные:

_:a foaf:name "Михаил Зимин" .
:vasya foaf:name "Василий Предольский".
:mihaSuslov foaf:name "Михаил Суслов" .
_:b0 foaf:name "Екатерина Пенькова" .

И мы хотим осуществить выборку только тех людей, у которых в имени есть подстрока "Михаил". В общем, хотим найти всех Михаилов независимо от их фамилии и отчества.

Конечно, для этого можно выбрать абсолютно все ресурсы, которые вообще имеют свойство foaf:name; а потом уже самому выбирать из них Михаилов. Можно воспользоваться конструкцией FILTER с regex, которая будет делать тоже самое за вас. Но существует принципиально другой способ осуществить поиск по подстроке.

Просто необходимо настроить репозиторий так, чтобы индексировал литералы. При этом будет создана ещё одна таблица, по которой можно будет сказать, — какая подстрорка находится в каком триплете. Причем этатаблица будет заполнятся заранее, по мере поступления триплетов в репозиторий, а не во время выполнения SPARQL-запроса.

Потом можно будет осуществлять подобные запросы (пример для BOCA):

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
prefix boca: <http://boca.adtech.internet.ibm.com/predicates/>

select ?person ?name
where
{
  ?person foaf:name ?name .
  ?name boca:textmatch "Михаил" .
}

Причем, boca:textmatch — не настоящее свойство субъекта, просто видя его встроенный в BOCA SPARQL-процессор понимает, что необходимо как-раз таки здесь использовать данные из таблицы индексации подстрок литералов. Это, кстати, тоже можно назвать расширенным SPARQL.

Ну всё, вроде с репозиториями разобрались.

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

все о Semantic Web

Статьи: