Программирование, 2020, № 6, стр. 16-29

1. ВВЕДЕНИЕ

Среди исследователей, работающих в области семантических технологий, всем известно, что такое пустые узлы (ПУ), иначе называемые Blank nodes. Они используются для представления объектов, не имеющих постоянных идентификаторов, то есть IRI (Internationalized Resource Identifier – интернационализированный идентификатор ресурса). Примером использования может быть, например, представление класса, являющегося объединением нескольких классов, или представление коллекции. В случае представления объединений, например, конструкции owl:unionOf, получившийся класс будет пустым узлом, который ссылается на RDF list – структуру, в которой все промежуточные элементы, включая корневой, являются пустыми узлами, а перечисляемые элементы – обычными узлами с читаемыми идентификаторами (рис. 1). То же самое касается представления конструкции owl:Restriction (рис. 2). Подразумевается, что подобный узел не имеет значения без указания, на какое свойство вводится ограничение, а также без ограничения на значение.

Рис. 1.

Представление конструкции RDF list.

Рис. 2.

Представление конструкции owl:Restriction.

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

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

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

Визуализация в целом и предложенный подход в частности могут быть полезны в ряде задач по протоке логических выражений, рассмотренных в таких статьях как ”Визуализация знаний на основе семантической сети” [2] и ”Методы ускорения логического вывода в продукционной модели знаний” [3].

2. СУЩЕСТВУЮЩИЕ ПОДХОДЫ

Здесь и далее для примеров используются данные, представленные на листинге 1 на странице 4. Данные являются частью онтологии вин http: //www.w3.org/TR/owl-guide/wine.rdf. Для наглядности одна из связей продублирована, и ее идентификатор заменен на нестандартный: owl:intersectionOf $ \to $ <http://example.com/unknownTypeOfProperty>. Это сделано, чтобы показать, как средства визуализации обрабатывают нестандартные случаи.

Есть несколько подходов к обработке ПУ. Некоторые подходы включают непосредственно решение задачи ленивой визуализации онтологического графа, другие также решают задачу сравнения графов, содержащих ПУ, но преследуют другие цели. Так Ontop Protégé [4] для работы с ПУ вводит ограничение на свойства ПУ – каждый ПУ должен иметь литеральное свойство rdfs:label, которое, очевидно, выступает в качестве постоянного идентификатора ПУ. Другой плагин OntoGraph Protégé позволяет визуализировать ПУ, однако нестандартным образом. В OntoGraph ПУ визуализируются в виде аннотаций, как это представлено на рис. 3а. На рис. 3а видно, что аннотации представляются в виде всплывающих окон, при этом конструкция owl:Restriction представляется как свойство Superclasses, а owl:IntersectionOf отображается в виде Equivalent classes. Иначе OntoGraph Protégé разбирается с отображением нестандартных структур. На рис. 3b видно, что нестандартная связь к структуре RDF list выделяется в отдельный блок Annotations, после чего отображается только первый ПУ структуры.

Рис. 3.

Представление конструкций в инструменте OntoGraph Protégé.

В некоторых инструментах, таких как Graffoo [5], отсутствует поддержка визуализации ПУ, и при рендеринге ПУ исключаются из визуализации. WebVOWL [6] при визуализации онтологий, содержащих ПУ, осуществляет индивидуальный подход к визуализации известных структур, однако список поддерживаемых структур ограничен. Так, например, конструкция owl:intersectionOf представляется в виде топологии звезда, где центральный узел является пересечением других классов топологии (см. рис. 4), при этом WebVOWL практически игнорирует конструкции owl:Restriction, отображая только связи присоединенные к базовой сущность owl:Thing. Нестандартные случаи игнорируются. Стоит также отметить, что WebVOWL сосредотачивается в большей степени на визуализации классов, нежели экземпляров классов.

Рис. 4.

Конструкции owl:Restriction и owl:IntersectionOf в инструменте WebVOWL.

Подобным путем индивидуального подхода идет инструмент OWLGrEd [7]. Конструкция owl:intersectionOf визуализируется в виде дерева. Конструкция owl:Restriction отображается в теле целевого элемента в виде аннотации (рис. 5a). В отличие от WebVOWL, OWLGrEd способен рисовать экземпляры классов, выделяя их зеленым цветом, однако не справляется с отображением нестандартных случаев. Конструкции типа RDF list игнорируются, если не являются частью конструкции owl:IntersectionOf (рис. 5b).

Рис. 5.

Представление конструкций в инструменте OWLGrEd.

С другой стороны к данному вопросу подходит php-библиотека EasyRdf [8].

При визуализации EasyRdf максимально точно передает структуру онтологического графа, но не предпринимает попыток индивидуальной визуализации общеизвестных структур (см. рис. 6a). На рис. 6a представлена только часть результата. Это сделано вследствие того, что EasyRdf не предоставляет возможность изменять результат визуализации, и полный результат будет сложен для восприятия. Весь граф единомоментно помещается в память браузера, что дает возможность ссылаться на ПУ и производить визуализацию целевых структур. Плюсом данного подхода является то, что нестандартные случаи отображаются в точность так, как они определены (см. рис. 6b). Рассматривая примеры OWLGrEd, WebVOWL, следует сказать, что индивидуальный подход имеет свои преимущества при визуализации, если же его совмещать с глобальным подходом, как это делает EasyRdf, то мы получим комфортную визуализацию знакомых структур, совмещенную с возможностью универсальной визуализации.

Рис. 6.

Представление конструкций в инструменте EasyRdf.

Данный подход, например, осуществляет инструмент работы с онтологиями TopBraid Composer [9] (см. рис. 7a и 7b). Как можно видеть из результатов визуализации, TopBraid индивидуально подходит к отображению конструкций owl:IntersectionOf и owl:Restriction (см. рис. 7a), отображая ограничения и пересечения в теле элементов. Подобным образом TopBraid подходит к отображению конструкций RDF list, где элементы списка по порядку отображаются в теле головы списка, но в то же время инструмент способен показать всю структуры целиком, отображая пустые узлы в виде набора RDF list соединенных связями rdf:rest (см. рис. 7b). При этом весь объем данных загружается в память приложения и индексируется в соответствие с задачей, что позволяет порционно визуализировать граф. Вся модель хранится в памяти компьютера пользователя, поэтому визуализация ограничена ресурсами компьютера. Большие базы знаний, такие как Wikidata и DBpedia, не могут быть отображены подобным образом.

Рис. 7.

Представление конструкций в инструменте TopBraid Composer.

Что же касается инструмента Ontodia, здесь, как и в TopBraid, совершена попытка совместить два подхода, при этом индивидуальный подход в текущей реализации очень беден и включает только обработку конструкций типа RDF list, остальные конструкции визуализируются в рамках глобального подхода (см. рис. 8a). Как можно видеть из рисунка, для всех элементов RDF list проводятся дополнительные связи, указывающие на голову списка, а также указывается порядковый номер элемента в списке. То же самое делается и для хвоста списка, который, в свою очередь, является самостоятельным списком. Такой подход помогает легко справляться с визуализацией нестандартных случаев (см. рис. 8b). Стоит отметить, также, что загрузка данных в инструменте осуществляется лениво, загружается только визуализированная часть онтологического графа, что позволяет работать с большими данными.

Рис. 8.

Представление конструкций в инструменте Ontodia.

Исходя из вышеперечисленного, получаем следующую сводную табл. 1, которая описывает подходы рассмотренных инструментов к визуализации структур, содержащих ПУ.

3. ОПИСАНИЕ РЕШЕНИЯ

3.2. Общее описание решения

Решение, которое предлагает Ontodia для отображения ПУ, состоит в том, чтобы ввести стадию предобработки запросов и выдать контекстно зависимые идентификаторы пустым узлам. Стадия предобработки включает в себя несколько шагов: сбор контекста, формирование контекстно зависимых идентификаторов, сохранение результатов предобработки для последующей выдачи. Идентификаторы должны быть составлены так, чтобы было возможно восстановить контекст напрямую из каждого сгенерированного идентификатора и однозначно сравнить узлы.

Контекст определяется следующим образом: Контекст для целевого пустого узла – это подграф основного графа, который включает целевой ПУ, а также транзитивно все ПУ, заключенные между непустыми узлами, окружающими данный подграф и включающий их (см. рис. 9). То есть контекст для целевого ПУ – это граф, который содержит целевой ПУ и всех его соседей и соседей его соседей, вплоть до первого непустого узла (НПУ).

Рис. 9.

Представление контекста ПУ.

Далее, чтобы подробней описать метод, ответим на следующие вопросы:

1. В какой момент и где производится предобработка данных?

2. Как собирается контекст?

3. Как создаются контекстно зависимый идентификатор?

4. Где и когда происходит выдача результатов?

4. ЗАКЛЮЧЕНИЕ

Разработанный метод решает задачи визуализации и восстановления сохраненного графа. При сохранении графа сохраняются и идентификаторы узлов, а поскольку проблемная часть (контекст с ПУ) кодируется в идентификаторах, она также легко восстанавливается при загрузке сохраненного графа. Метод описан в общем виде и подходит для ленивой визуализации ПУ онтологических графов не только с использованием инструмента Ontodia, но и при работе с другими инструментами визуализации. Следующим шагом развития данного метода может быть формализация обработки специальных структур, использующих ПУ в качестве структурных компонентов:

• Список (RDF list);

• Аксиома (owl:Axiom);

• Ограничение (owl:Restriction);

• Взаимное различие (owl:AllDifferent);

• Объединение (owl:unionOf);

• Пересечение (owl:intersectionOf);

• Дополнение (owl:complementOf);

• Перечисление (owl:oneOf) [13].

Листинг 1: Представление конструкций owl:IntersectionOf и owl:Restriction в формате Turtle

Листинг 2: Часть канонизированного графа контекста в каноничной форме, включающая указатель на целевой элемент

Листинг 3: Компактное представление графа контекста в формате JSON, полученное из IRI элемента

Листинг 4: Пример сгенерированного IRI

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

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