Метод диаграмматической верификации онтологий на основе дескрипционной логики ALC тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Нгуен Нгок Тхан

• Нгуен Нгок Тхан
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Нгуен Нгок Тхан

Содержание

Реферат

Synopsis

Введение

1. Анализ предметной области

1.1 Методы диаграмматического представления знаний

1.1.1 Диаграммы Венна

1.1.2 Экзистенциальные графы Пирса

1.1.3 Теория графов

1.1.4 Концептуальные графы

1.2 Визуальные языки для онтологий

1.3 Диаграмматический вывод для онтологий

1.4 Методы оценки визуальных языков

1.4.1 Принципы проектирования визуальных языков

1.4.2 Методы оценки визуальных языков для онтологий

1.5 Требования к разрабатываемым методам визуального представления онтологий

1.5.1 Семейство языков OWL

1.5.2 Семейство DL

1.5.3 Верификация онтологий

1.6 Выводы по Главе

2. Разработка семантико-ориентированных методов визуального представления онтологий

2.1 Семантико-ориентированный визуальный язык для

онтологий Logic Graphs

2.1.1 Logic Graphs для ALC

2.1.2 Logic Graphs для SHIFT

2.1.3 Logic Graphs для SHOIN

2.2 Алгоритм диаграмматической верификации для LG

2.2.1 Диаграмматический вывод для LG

2.2.2 Непротиворечивость системы диаграмматического вывода LG

2.3 Формальные методы оценки визуальных представлений онтологий

2.3.1 Полнота

2.3.2 Оценка информативности

2.4 Выводы по Главе

3. Апробация разработанных методов

3.1 Апробация языка Logic Graphs

3.2 Апробация диаграмматического алгоритма верификации

для LG

3.3 Апробация формальных методов оценки визуальных представлений онтологий

3.4 Выводы по Главе

Заключение

Список иллюстраций

Список таблиц

Литература

Приложение 1 - Акты о внедрении

Приложение 2 - Тексты публикаций

Реферат

Общая характеристика работы

Введение диссертации (часть автореферата) на тему «Метод диаграмматической верификации онтологий на основе дескрипционной логики ALC»

Актуальность

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

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

— Обзор и анализ существующих методов диаграмматического представления знаний.

— Обзор и анализ существующих методов визуализации онтологий.

— Обзор и анализ существующих методов оценки визуальных представлений онтологий.

— Разработка семантико-ориентированного визуального языка представления онтологий.

— Разработка алгоритма диаграмматической верификации онтологий.

— Разработка формальных методов оценки визуальных представлений онтологий.

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

Объектом исследования в данной диссертационной работе являются методы диаграмматического представления знаний.

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

Методы исследования. В диссертации применялись методы представления знаний, математической логики, теории информации, теории графов.

Основные положения, выносимые на защиту:

— Визуальный язык представления онтологий Logic Graphs, позволяющий формировать логически корректные и полные визуальные представления онтологий, описанных на языке OWL DL.

— Метод диаграмматической верификации онтологий, заданный на языке Logic Graphs, включающий систему диаграмматического вывода для Logic Graphs, корректность которой доказывается посредством табличного алгоритма дескрипционной логики ALC.

— Формальные метрики, позволяющие сформировать оценки качества визуальных представлений онтологий: полнота и информативность, основанная на формализме гиперграфов.

Научная новизна диссертации:

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

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

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

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

Теоретическая и практическая значимость. Теоретическая значимость результатов диссертационной работы состоит в создании новых

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

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

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

Внедрение результатов работы. Результаты диссертационного исследования были использованы в учебном процессе Университета ИТМО при выполнении лабораторных работ и проведении лекционных курсов на факультете программной инженерии и компьютерной техники по дисциплинам «Онтологии и представление знаний» и «Графовые базы знаний». Также полученные результаты нашли практическое применение в проекте «Разработка способов визуального представления сложных конструкций языка OWL», выполненном международный научной лабораторией «Интеллектуальные методы обработки информации и семантические технологии».

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

— 5th International Scientific and Practical Conference "TECHNOLOGICAL PERSPECTIVE: NEW MARKETS AND POINTS ECONOMIC GROWTH"(St.Petersburg, 2019)

— 27th Conference of Open Innovations Association FRUCT (Trento, 2020)

— 12th The Majorov International Conference on Software Engineering and Computer Systems 2020 (St.Petersburg, 2020)

— the 30th anniversary international conference on computer graphics and machine vision (St.Petersburg, 2020)

— VII конгресс молодых ученых университета ИТМО (Санкт- Петербург, 2018)

— VIII Конгресс молодых ученых университета ИТМО (Санкт- Петербург, 2019).

Личный вклад. Соискателем лично получены основные результаты: язык представления онтологий Logic Graphs, метод диаграмматической верификации онтологий и формальные метрики качества представления онтологий. Язык представления онтологий Logic Graphs разработан совместно с Баймуратовым И.Р. и Муромцевым Д.И. Метод диаграм-матической верификации онтологий и формальные метрики качества представления онтологий разработаны совместно с Баймуратовым И.Р. Программная реализация метрик оценки качества визуальных представлений онтологий выполнялась совместно с Голчиным Р.А.

Публикации. Основные результаты диссертации изложены в 6 публикациях. 5 из которых изданы в журналах и сборниках докладов конференций, рецензируемых Scopus.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации составляет 224 страниц, включает в себя 84 рисунка, 36 таблицы. Библиографический список включает 95 наименование.

Основное содержание работы

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

Первая глава содержит анализ предметной области. В этой главе рассмотрены и проанализированы существующие методы визуализации

онтологий. Установлено, что существующие методы визуализации онто-логий имеют общие недостатки, которые необходимо преодолеть, чтобы иметь возможность осуществлять диаграмматический вывод: полнота используемого визуального языка и отражение семантики логических отношений. Обзор инструментов визуализации онтологий приведен в таблице 0.1. Для каждого метода визуализации был произведен анализ полноты по отношению к языку описания онтологий OWL DL и отражается ли семантика логических отношений.

Для детального анализа были выбраны три наиболее полные системы визуализации онтологий: VOWL, SOVA и Graphol. В результате их анализа установлено, что, хотя инструменты, упомянутые выше, поддерживают почти все языковые конструкции OWL DL, они визуализируют онтологические структуры, только обозначая их произвольными графическими примитивами, не отражая семантику отношений. Поэтому вместо того, чтобы облегчать восприятие онтологий, пользователю приходится изучать новый визуальный язык. Например, сравним визуализацию пересечения в Graphol, рис. 0.1, с соответствующей диаграммой Венна, рис. 0.2.

Из диаграммы Венна пользователь может понять семантику отношения, т.е. что два множества обладают общими элементами, а в случае СгарЬо1 пользователь должен запомнить, что шестиугольник обозначает конъюнкцию.

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

Рисунок 0.1 — Пересечение в Graphol

Рисунок 0.2 — Диаграмма Венна для пересечения

Таблица 0.1 — Анализ полноты существующих инструментов визуализации онтологий

Cardinality (

OWL Classes property unionOf Intersection Of Compelment Of Some ValueFrom AllValue From Тгалэ^гуе Property Inverse of Cardinality subPropertyOf maxCardinality minCardinality cardinality) Oneof FunctionalProperty Subclass of Equivalent Class

DL Концепт Роль Пересечение Объединение Дополнение Экзистенциальное ограничение Универсальное ограничение Тралзитиьная роль Обратная роль Кардинальность роли Иерархия ролей Ограничение кардинальности роли Норминал Функциональная роль Включение Экьиьалентность

FlexViz + + +

GlOW + + +

Graifoo + + + + + + + + + + + +

GrOWL + + + + + + + + + + + + + + + +

Jambaiaya + + + + + +

КС-Viz + + + +

Navig-OWL + + + + + + + + + + + + + + +

OLSvis + + +

Ontodia + + + + + +

OntoGraf + + + + + + + + + +

OntoRama + +

OntoViz + + + + + + + + + + + +

OWLGrEd + + + + + + + + + + + + + + + +

Topbraid + + + + + + + + + + + + + + + +

OWLViz + +

SOVA + + + + + + + + + + + + + + + +

TGViz + + +

WebVOWl + + + + + + + + + + + + +

Graphol + + + + + + + + + + + + + + + +

установлено, что эти методы неприменимы для представления языка OWL DL.

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

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

Наконец, был произведен обзор языка описания онтологий OWL и его подъязыков: OWL Lite, OWL DL, OWL Full. Также были рассмотрены соответствующие им дескрипционные логики: ALC, SHIF, SHOIN. SHOIN включает в себя все конструкторы, соответствующие языку OWL DL. Синтаксис и семантика ALC представлены в таблице 0.2:

Таблица 0.2 — Дескрипционная логика ALC

Наименование Синтаксис Сементика

концепт С С1 с А1

роль R R1 с А1 х А1

дополнение -С А1 \ С1

пересечение С П D С1 П D1

объединение С U D С1U D1

экзистенциальное ограничение 3R.T (3R.T)1 = {а е А1: ЗЬ (a,b) G R1}

универсальное ограничение VR.T (УД.Т)1 = {а е А1: УЬ (a,b) G R1} ^ b е С1

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

Во второй главе представлены разработанные методы визуального представления онтологий. Во-первых, это семантико-ориентирован-ный визуальный язык представления онтологий, получивший название «Logic graphs», который является полным по отношению к языку OWL DL и отражает семантику логических отношений, используя минимум графических примитивов.

LG для ALC. Визуальный язык Logic Graphs разрабатывался на основе экзистенциальных графов. Его фрагмент, соответствующий де-скрипционной логике ALC, представлен в Таблице 0.3, где С, С1 и С2 - концепты, R - роль, а и b - индивиды.

Таблица 0.3 — Logic graphs для ALC_

C

2.

лС

В

С1П С 2

4.

С1LI С 2

5. 7.

С 1С С 2

<71 SubClassOf (72

6.

С1 = С 2

3R.C

\fR.C

9.

а : С

10.

(а,Ъ) : R

R

. а .Ь

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

Для примера рассмотрим обозначение пересечения. Внешний прямоугольник также обозначает множество объектов. Прямоугольники

внутри обозначают, что эти объекты в полной мере обладают как свойством С\, так и свойством С2, что соответствует семантике пересечения. Аналогичным образом выводятся обозначения и других отношений.

LG для SHIFT. Фрагмент OWL DL, соответствующий дескрипцион-ной логике SHIFT, расширяет язык следующими отношениями:

— обратная роль;

— транзитивная роль;

— функциональная роль;

— иерархия ролей.

Чтобы изобразить роли, являющиеся обратными или транзитивными, предлагается применять подход теории графов, поскольку это широко распространенный метод визуализации, отражающий семантику этих свойств ролей. Следовательно, обратной роли R- соответствует обратно направленное ребро. Далее, если роль R+ является транзитивной, одно ребро соединяет узел С с узлом D, а другое - узел D с узлом Е, то должно быть ребро между узлами С и Е. См. рис. 0.3 и рис. 0.4.

С1 R- С2

Рисунок 0.3 — Обратная роль

С R+ С

-►

1 R+ г

С

Рисунок 0.4 — Транзитивная роль

К сожалению, нет более простого способа представления функциональных ролей, чем пометить соответствующую стрелку обозначением "^ 1" . См. рис. 0.5.

С1 < 1Р ь, С2

Рисунок 0.5 — функциональная роль

Для включения ролей предлагается не вводить новый графический примитив, а вывести представление на основе семантики. Семантика включения ролей следующая

Я ц в & Я1 с 51 (1)

По определению роли,

Я1 с 51 & (а,Ь) е Я1 ^ (а,Ь) е 51 (2)

Определим множество X такое, что

X = {а : (а,Ь) е Я1} (3)

и множество У такое, что

У = {а : (а,Ъ) е 57} (4)

Тогда можно доказать следующую лемму. Лемма 1: Я1 с в1 ^ X Ц У

Доказательство. Согласно определению X, для каждого а, если а е X ^ (а,Ь) е Я1, тогда, согласно (2), верно (а,Ь) е в1 и, наконец, согласно определению У, верно а е У. Следовательно, а е X ^ а е У для каждого а, и X Ц У. □

В результате предлагается изображать включение ролей Я Ц 5 включением соответствующих концептов X Ц У, как показано на рис. 0.6.

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

Таким образом, Logic Graphs расширены до дескрипционной логики SHIF.

Рисунок 0.6 — Иерархия ролей

LG для SHOIN. Наконец, фрагмент, соответствующий SHOIN, расширяет OWL DL следующими конструкциями:

— номиналы (О);

— Ограничения кардинальности ролей (N).

Номиналы позволяют определять концепты как наборы индивидов: если а - имя индивида, то {а} - это номинал. Ожидаемо, такая конструкция интерпретируется как {а}1 = {а1}.

В Logic Graphs каждый индивид номинала изображается в виде точки в прямоугольнике, пример на рисунке 0.7.

. ai . а2

. аз

. а4 . as

Рисунок 0.7 — Номинал

Далее, ограничения кардинальности (N) позволяют ограничивать количество индивидов, которых можно достичь с помощью роли. В Logic Graphs ограничения кардинальности ролей указываются в виде чисел над стрелкой, соответствующей роли, и символов "^"и Фиксиро-

ванные значения обозначаются символом " = ". Пример на рисунке 0.8 .

С1 <(>,=)ПР С2

W

Рисунок 0.8 — Ограничения кардинальности ролей

Таким образом, Logic Graphs расширены до дескрипционной логики SHOIN, следовательно, метод является полным по отношению к языку OWL DL.

Диаграмматический алгоритм верификации онтологий. Для Logics Graphs был разработан алгоритм диаграмматической верификации. Он основан на табличном алгоритме для ALC. Алгоритм заключается в построении дерева, узлы которого являются пространствами утверждений. Определения:

— Дерево пространств утверждений. Дерево пространств утверждений - это тройка Т = (V,E,L), где V - множество узлов, Е -множество ребер и L(x) - функция, которая присваивает каждому узлу х G V пространство утверждений.

— Противоречивое пространство утверждений. Для некоторого узла х G V и концепта С, пространство утверждений L(x) противоречиво, если оно содержит концепт С и его отрицание —С.

— Непротиворечивость. Онтология непротиворечива, если в соответствующем дереве имеется хотя бы одно непротиворечивое пространство утверждений.

При построении этого дерева все сложные узлы сводятся к элементарным по следующим правилам:

— —-правило. Обратить затемнение узла;

— П+-правило. Удалить узел пересечения и поместить все его элементы на пространство утверждений;

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

— 3+-правило. Удалить ребро роли и его целевой концепт и присвоить узлу исходного концепта новое имя.

— 3--правило. Удалить ребро роли и его целевой концепт и присвоить узлу исходного концепта имя, которое уже использовалось для тех же роли и целевого концепта.

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

Таким образом, алгоритм следующий:

1. Вход: ЬС, построенный по онтологии.

2. Построение дерева пространств утверждений Т: пока возможно, к ЬС применяются правила преобразования.

3. Выход: если Т содержит непротиворечивое пространство утверждений, онтология непротиворечива, иначе - противоречива.

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

Для визуального языка V полнота СатрШепевв^) определяется как количество синтаксических элементов языка описания онтологий Ь, которые представимы в V, к количеству всех элементов языка описания онтологий Ь:

Полнота представления онтологии СотрУЛепезво (V) определяется как количество аксиом А(0)у онтологии О, которые представимы посредством V, к общему количеству аксиом А(О) онтологии О:

Вторая метрика информационная. Она выводится как функция Хартли

С отрШепе8з(у) = —.

Ьь

СотрШепевво (У) =

1одь1А1,

(5)

Хз ) ( Х3 ) ( Х3

Рисунок 0.9 — Примеры гиперграфов Таблица 0.4 — Информационная оценка гиперграфов

н X Е \ М I (Н)

1 3 2 3 0.21

2 3 3 3 0.33

3 3 3 4 0.17

где А - произвольное множество and b - произвольное число, примененная к представлению онтологии в виде гиперграфа, а именно в виде матрицы инцидентности.

Пусть дан гиперграф Н с заданным набором узлов X, заданным набором ребер Е и набором соответствующих значений матрицы инцидентности {а}. Подставляем в (5) количество ребер IE| как \А| и количество всех возможных ребер \Е\ как Ь, тогда информация гиперграфа I(Н) определена формулой:

I (Н) = log\s\\E | = щ log\М||Е |. (6)

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

В третьей главе представлены эксперименты с разработанными методами представления онтологий. Во-первых, применение языка Logic Graphs было продемонстрировано на онтологии Document Component Ontology (DoCO). Выбор этой онтологии обусловлен тем, что она используется в различных прикладных решения и содержит нетривиальные аксиомы. Визуальное представление выборки аксиом из онтологии DoCO приведено в Таблице 0.5.

Также предоставлены примеры применения разработанного диаграм-матического алгоритма верификации онтологий, представленных на

Таблица 0.5 — Logic graphs для онтологии DoCO

abstract Q (chapter U section) n(3i s p a rt о f.b о dym at t e r Uf rontm att e r)

afterword Q sectionH 3i s p a rt о f.b a с km at t e r)

appendix Q (sectionH

h e a d e d с о nt ai n e г)П (3i s p a rt о f.b a с km at t e r)

ba с km att e г Q discourseelement Hcont ai n e r

b a с kmatt e г Q Vi s cont ai n e dby (.—b a с km at t er U b о dym at t e r U n m a )

Blockquotation Q container

chapter Q 3contains.paragraph Us e cti on

chapt er Q 3contain s.—( chapt er)

ch apt e r la be I Q — s e cti on la be I

ch apt e r s u btit le Q 3i spart о f.ch apt e r

u Q m a a U m n

h e a d e r = f ront m att e r

glossary Q section\l (3i s p art о f.b a с km at t e r U n m a )

list Q Vcontains.blocк U fieIdU (с о nt ai n e г П (—(h e a d e d с о nt ai n e d Ut abl e)))

a n n Q

3h a sp a rt.li s t о fr e f e r e n с e sn (V с о nt ai n s. 3r e lat i о n. s e ct i о n)

a a

языке LGs. В первом примере рассматривается концепт «Веган и не Вегетарианец». Под веганом подразумевается человек, который питается только растениями:

Vegan = Person П Veats.Plant.

Под вегетарианцем подразумевается человек, который питается только растениями и молочной пищей:

Vegetarian = Person П У eats. (Plant LI Diary). Произведем подстановку:

Person П Veats.Plan П — (Person П У eats. (Plant L Diary)).

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

1. вход: S = {PersonП—Beats.—PlantП — (PersonП—Зeats.(—PlantП —Dairy))};

2. П+-правило: S = {Person, —Beats.—Plant, —(Person П —Beats.(—Plant П —Dairy))};

3. П--правило для —(Person П —Beats.(—Plant П —Dairy)): Si = {Person, —Beats.—Plant, —Person},

S2 = {Person, —Beats.—Plant, Beats.(—Plant П—Dairy)}, мы видим, что Si уже содержит противоречие;

4. П+-правило для S2: S2 = {Person, —Beats.—Plant, Beats.—Plant, Beats.—Dairy};

5. B+шравило для Beats.—Plant: S2 = {Person, —Beats.—Plant, EatsNotPlant, Beais.—Dairy};

6. B'-правило для —Beats.—Plant: S2 = {Person, —EatsNotPlant, EatsNotPlant, Beats.—Dairy}. Теперь S2 также содержит противоречие.

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

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

Person П Veats.Plan Ц Person П У eats. (Plant L Diary).

Рисунок 0.10 — Дерево пространств утверждений для концепта "Веган

и не вегетарианец"

Соответствующее дерево пространств утверждений:

1. Вход: S = [Person П —Beats.—Plant С Person П —Beats. (—Plant П -Dairy))};

2. Применим С-правило: S\ = [—(Person П —Beats.—Plant)}, S2 = [Person П —Beats.(—Plant П —Dairy))};

3. Применим П--правило к S\: Su = [—Person}, S\2 = [Beats.—Plant)}, К Su больше невозможно применить ни одно правило и при этом оно непротиворечиво, следовательно, существует хотя бы одно непротиворечивое пространство утверждений и база знаний K непротиворечива, однако мы завершим анализ других пространств утверждений, чтобы продемонстрировать алгоритм;

4. Применим B+-правило к S\2: S\2 = [а : EatsNotPlant}, анализ S\2 завершен;

5. Применим П+-правило к S2: S2 = {Person, —Beats.(—Plant П -Dairy))};

6. Применим П--правило: S2\ = {Person, Beats.Plant}, S22 = {Person, Beats.Dairy};

7. Применим B+-правило к 52i : 52i = {Person, EatsPlant}, анализ 52i завершен;

8. Применим B+-правило: S22 = {Person, EatsDairy}, анализ S22 завершен;

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

Рисунок 0.11 — Дерево пространств утверждений для аксиомы "Веган

- это вегетарианец"

Далее, было произведено сравнение существующих систем визуализации онтологий VOWL и Graphol с Logic Graphs на основе разработанных формальных метрик. Оценка полноты визуальных языков представлена в таблицах 0.6, 0.7 и 0.8. Согласно таблице, в VOWL выразимы только

12 из 15 элементов языка OWL DL, следовательно, полнота составляет 0,8. В отличие от VOWL, языки Graphol и LGs являются полными.

Таблица 0.6 — Оценка полноты VOWL_

N Сущность Полнота

1 концепт о

2 роль

3 дополнение е>—

4 пересечение ^ClassA^---'С©3'--^ClassB^

5 объединение

6 экзистенциальное ограничение

7 универсальное ограничение

8 транзитивная роль ^Chas^A^-(transitive)-^.^ClassB^

9 обратная роль ^ciassA^-(transitive)-^^Oass^B^

10 иерархия ролей ^Ctess A J Subproperty Class^

11 кардинальное ограничение ©

12 номинал

13 функциональная роль ^lass^-(functional)-^^Oass^

14 включение

15 эквивалентность ©

0.8

Хотя язык Graphol является полным, сформированные с его помощью визуальные представления онтологий являются менее информативными. Для оценки информативности была составлена выборка аксиом из онтологии DoCO. Для каждого графа была построена матрица инцидентности и рассчитана информативность. Результат представлен в Таблице 0.9. Как можно видеть, средняя информативность Logic Graphs выше, чем у Graphol.

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

Список литературы диссертационного исследования кандидат наук Нгуен Нгок Тхан, 2021 год

нормативности графов

н X Е М I (Н)

1 3 2 3 0.21

2 3 3 3 0.33

3 3 3 4 0.17

2.4 Выводы по Главе 2

В данной главе был представлен разработанный семантико-ориенти-рованный визуальный язык для онтологий, названный Logic Graphs. Он является полным по отношению к языку OWL DL и в большинстве случаев (кроме функциональных ролей и кардинальных ограничений) отражает семантику логических отношений, что обеспечивает возможность диаграмматического вывода.

Далее, для Logics Graphs был разработан алгоритм диаграммати-ческой верификации. Этот алгоритм основан на табличном алгоритме для дескрипционной логики ALC и позволяет определять непротиворечивость онтологий. Как и в случае с ALC, алгоритм заключается в построении дерева, узлы которого являются пространствами утверждений. База знаний К является непротиворечивой, если соответствующее дерево имеет хотя бы одно непротиворечивое пространство утверждений.

Также были предложены формальные метрики для оценки визуальных представлений онтологий. Первая метрика - полнота. Она определена для визуального языка в целом и для визуального представления отдельной онтологии. Вторая метрика - информационная. Она выводится из функции Хартли и позволяет оценивать сложность визуальных представлений онтологий, рассматриваемых как матрицы инцидентности.

3. Апробация разработанных методов

3.1 Апробация языка Logic Graphs

В данном разделе применение языка Logic Graphs демонстрируется на онтологии Document Component Ontology (DoCO). Выбор этой онтологии обусловлен тем, что она используется в различных прикладных решения и содержит нетривиальные аксиомы. Визуальное представление выборки аксиом из онтологии DoCO приведено в Таблице 3.1.

3.2 Апробация диаграмматического алгоритма верификации для LG

В данном разделе представлены примеры применения разработанного диаграмматического алгоритма верификации онтологий, представленных на языке LG. В первом примере рассматривается концепт «Веган и не Вегетарианец». Под веганом подразумевается человек, который питается только растениями:

Vegan = Person П Veats.Plant.

Под вегетарианцем подразумевается человек, который питается только растениями и молочной пищей:

Vegetarian = Person П У eats. (Plant U Dairy).

Произведем подстановку:

Person П Veats.Plan П - (Person П У eats. (Plant U Dairy)).

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

Таблица 3.1 — Логические графы для онтологии DoCO

abstract Q (chapter U section) n(3ispartof .body matter Ufrontmatter)

afterword Q sectionH 3ispartof .backmatter)

appendix Q (sectionH

headedcontainer) П (^ispartof .backmatter)

backmatter Q discourseelement Hcontainer

backmatter Q \liscontainedby (.—backmatter U bodymatter Ufrontmatter)

Blockquotation Q container

chapter Q 3contains.paragraph Usection

chapter Q ^contains.—(chapter)

chapterlabel Q —sectionlabel

chapter subtitle □ Bispartof .chapter

figure Q mata U milestone

header = frontmatter

glossary Q sectionn (bispartof .backmatter Ufrontmatter)

list Q \contains.block U fieldU (container П (—(headedcontained Utable)))

tableof contents Q 3haspart.listof refer encesn (\contains. 3relation.section)

tabled table

1. вход: 5 = {PersonП—Beats.—PlantП — (PersonП—Beats.(—PlantП -Dairy))};

2. П+-правило: S = {Person, —Beats.—Plant, —(Person П —Beats.(—Plant П —Dairy))};

3. П--правило для —(Person П —Beats.(—Plant П —Dairy)): S\ = {Person, —Beats.—Plant, —Person},

S2 = {Person, —Beats.—Plant, Beats.(—Plant П -Dairy)}, как можно видеть, S\ уже содержит противоречие;

4. П+-правило для S2: S2 = {Person, —Beats.—Plant, Beats.—Plant, Beats.—Dairy};

5. B+-правило для Beats.—Plant: S2 = {Person, —Beats.—Plant, EatsNotPlant, Beats.—Dairy };

6. B--правило для —Beats.—Plant: S2 = {Person, —EatsNotPlant, EatsNotPlant, Beats.—Dairy}. Теперь S2 также содержит противоречие.

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

Рис. 3.1 — Дерево пространств утверждений для концепта "Веган и не

вегетарианец"

Также проверим на примере, что разработанный диаграмматический алгоритм не выявляет противоречий, если исходная база знаний не противоречива. Для этого рассмотрим аксиому «Веган - это вегетарианец». Соответствующее дерево пространств утверждений:

1. Вход: S = {Person П —Beats.—Plant Ц Person П —Beats.(—Plant П —Dairy))};

2. Ц-правило: S\ = {—(Person П —Beats.—Plant)}, S2 = {Person П —Beats.(—Plant П —Dairy))};

3. П--правило для S\: Sn = {—Person}, S\2 = {Beats.—Plant)}, к Sn больше невозможно применить ни одно правило и при этом оно непротиворечиво, следовательно, существует хотя бы одно непротиворечивое пространство утверждений и база знаний непротиворечива, однако мы завершим анализ других пространств утверждений, чтобы продемонстрировать алгоритм;

4. B+^равило для S\2: Sy2 = {а : EatsNotPlant}, анализ S12 завершен;

5. П+-правило для S2: S2 = {Person, —Beats.(—Plant П —Dairy))};

6. П--правило: S2\ = {Person, Beats.Plant}, S22 = {Person, Beats.Dairy};

7. B+^равило для S2\: S2\ = {Person, EatsPlant}, анализ S21 завершен;

8. B+^равило: S22 = {Person, EatsDairy}, анализ S22 завершен.

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

Рис. 3.2 — Дерево пространств утверждений для аксиомы "Веган - это

вегетарианец"

3.3 Апробация формальных методов оценки визуальных представлений онтологий

Пример оценки полноты

В качестве примера оценим полноту графических языков VOWL [37], Graphol [36] и LG [92] по отношению к языку OWL DL. См. Таблицу 3.2, 3.3 и 3.4 соответственно.

Как можно видеть, VOWL может представлять только 12 из 15 сущностей OWL DL, следовательно, его полнота составляет 0,8, тогда как Graphol и Logic Graphs являются полными визуальными языками.

N Сущность Полнота

1 концепт о

2 роль ^Оаэ^А^-[Ргорвпу в]-

3 дополнение (3-------чей

4 пересечение ^Оазз^---'С©3'--^аэзВ^

5 объединение

6 экзистенциальное ограничение

7 универсальное ограничение

8 транзитивная роль ^Оаэ^А^-(1гап8|11уе)-^^ОаББ^

9 обратная роль ^С^вА^-ргапзщув)-^^азз^

10 иерархия ролей ^ОаззА) виьргорепу ^ С1азз^

11 кардинальное ограничение ©

12 номинал

13 функциональная роль -(МпсИопа!)-^^аазэ^

14 включение

15 эквивалентность ©

0.8

Пример оценки информативности

Для демонстрации применения разработанной меры информативности гиперграфов была сформирована выборка аксиом из онтологии ЭоСО, затем они были представлены на визуальных языках ОгарЬо1 и ЬО. Список аксиом и их визуальные представления приведены в таблице 3.5.

Затем для каждого представления аксиомы была построена матрица инцидентности. Пример матрицы инцидентности для ОгарЬо1 уже рассматривался ранее, теперь рассмотрим пример матрицы инцидентности для ЬО. Матрица инцидентности для первой аксиомы, представленной

N Сущность Полнота

1 концепт

2 роль

3 дополнение (not)

4 пересечение ( and )

5 объединение < - >

6 экзистенциальное ограничение - • С

7 универсальное ограничение Г7. • ~ ■

8 тразнитивная роль ________________________

9 обратная роль

10 иерархия ролей о-<>

11 кардинальное ограничение - ".....

12 номинал ^oneOf^

13 функциональная роль <8>

14 включение Concept2

15 эквивалентность _ ^—^ _

1

на языке Logic Graphs, приведен в таблице 3.6. Для простоты в данном примере не учитывается направление ребер.

Расчет информативности для полученных матриц инцидентности представлен в Таблице 3.7. Как можно видеть, средняя информативность представлений LG по этой выборке выше, чем у Graphol.

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

Приложение реализовано на JavaFX, для представления графов используется библиотека Graphstream [93], а онтологии импортируются с помощью OWL API [94]. В процессе разработки было принято несколь-

N

Сущность

Полнота

концепт

роль

3

дополнение

4

пересечение

объединение

6

экзистенциальное ограничение

7

универсальное ограничение

8

транзитивная роль

9

обратная роль

10

иерархия ролей

11

кардинальное ограничение

12

номинал

13

функциональная роль

14

включение

15

эквивалентность

1

2

5

1

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

Рабочий процесс приложения состоит из трех шагов: 1) преобразование онтологии в граф, 2) размещение графа и 3) расчет выбранной

Таблица 3.5 — Аксиомы DoCO в LGs и Graphol

chapter С Bcontains.paragraph U section

2 abstract С (chapter U section) П (Bispartof .body matter U frontmatter)

3

afterword С section П Bispartof .backmatter)

4 appendix С (section П headedcontainer) П (Bispartof .backmatter)

backmatter С discourseelement П container

chapterlabel С —sectionlabel

7

chapter subtitle С 3ispartof .chapter

figure С mata U milestone

9 glossary С section П (Bispartof.backmatter U frontmatter)

5

6

8

Таблица 3.6 — Матрица инцидентности для аксиомы 1 в LG

subClassOf contains negation 1 negation 2 negation 3

conjunction 0 1 0 0 1

chapter 1 0 0 0 0

paragraph 0 0 1 0 0

domain 1 1 0 0 0

section 0 0 0 1 0

Таблица 3.7 — Сравнение информативности LG и Graphol

N LG Graphol

X Е I (Н) X Е I (Н)

1 5 6 0.52 6 3 0.26

2 9 11 0.38 10 5 0.23

3 5 3 0.32 6 3 0.26

4 7 4 0.29 8 4 0.25

5 4 2 0.25 4 2 0.25

6 2 2 0.5 3 2 0.33

7 3 2 0.33 4 2 0.25

8 4 5 0.58 4 2 0.25

9 7 7 0.4 8 4 0.25

0.4 0.26

Рис. 3.3 — Меню приложения

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

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

Рис. 3.4 — Архитектура приложения

предложенной метрики информативности (2.7) с |{&}| = 2. Наряду с этим реализована метрика энтропии графа (1.1), где X - множество узлов. Два узла считаются эквивалентными, если они имеют одинаковую степень. На этапе размещения используются различные эстетические метрики, такие как количество пересечений ребер и сходство с графом формы, а именно графом к-ближайших соседей [75].

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

Приложение предоставляет два способа оценки и сравнения визуализаций, созданных другими инструментами визуализации онтологий. Первый способ - смоделировать результаты с помощью соответствующих алгоритмов в приложении. На данный момент поддерживаются алгоритмы конвертации из систем ОП^гаГ [27] и OWLViz [23]. Второй способ

- импортировать результат. Некоторые инструменты визуализации, например WebVOWL поддерживает экспорт в DOT, поэтому приложение поддерживает импорт из этого формата.

В качестве примера на рис. 3.5 представлена визуализация онтологии FOAF [95] в приложении.

Рис. 3.5 — Визуализация онтологии FOAF в приложении

3.4 Выводы по Главе 3

В данной главе, было продемонстрировано применение разработанного семантико-ориентированного визуального языка Logic Graphs на примере выборки аксиом из онтологии DoCO.

Далее, были предоставлены примеры применения разработанного диа-грамматического алгоритма верификации онтологий, представленных на языке LG. Было продемонстрировано, что алгоритм позволяет выявлять противоречия, если исходная база знаний противоречива, и не выявляет противоречий, если она непротиворечива.

Наконец, было произведено сравнение существующих систем визуализации онтологий VOWL, Graphol и Logic Graphs на основе разработанных формальных метрик: полноты и информативности. Визуальный язык VOWL оказался менее полным, чем языки Graphol и Logic Graphs, тогда как Graphol на сформированной ранее выборке аксиом из онтологии DoCO оказался менее информативным. Также было разработано приложение для расчета формальных метрик визуальных представлений онтологий.

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

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

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

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

Во второй главе был представлен разработанный семантико-ориенти-рованный визуальный язык для онтологий, названный Logic Graphs. Он является полным по отношению к языку OWL DL и в большинстве случаев (кроме функциональных ролей и кардинальных ограничений) отражает семантику логических отношений, что обеспечивает возможность диаграмматического вывода.

Далее для Logic Graphs была разработана система диаграмматическо-го вывода и алгоритм диаграмматической верификации, основанный на табличном алгоритме дескрипционной логики ALC. Как и в случае с дескрипционной логикой, алгоритм заключается в построении дерева, узлы которого являются пространствами утверждений, переход между которыми осуществляется по определенным правилам вывода. Если соответствующее дерево имеет хотя бы одно непротиворечивое пространство утверждений, то исходная онтология непротиворечива.

Также были предложены формальные метрики для оценки визуальных представлений онтологий. Первая метрика - полнота. Она определена для визуального языка в целом и для визуального представления отдельной онтологии. Вторая метрика - информационная. Для векторного представления визуальных представлений онтологий был использован формализм гиперграфов, а именно матрицы инцидентности. Информационная метрика выводится из функции Хартли и позволяет оценивать сложность визуальных представлений онтологий.

В третьей главе было продемонстрировано применение разработанного семантико-ориентированного языка Logic Graphs для визуального представления онтологий на примере выборки аксиом из онтологии DoCO.

Далее были предоставлены примеры применения разработанного диа-грамматического алгоритма верификации онтологий, представленных на языке Logic Graphs. Было продемонстрировано, что алгоритм позволяет выявлять противоречия, если исходная база знаний противоречива, и не выявляет противоречий, если она непротиворечива.

Наконец, было произведено сравнение некоторых существующих визуальных языков для онтологий с Logic Graphs на основе разработанных формальных метрик, полноты и информативности. Сравнение показало, что визуальные представления с использованием языка Logic Graphs более полны и информативны.

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

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

2. Разработан семантико-ориентированный визуальный язык представления онтологий Logic graphs.

3. Разработан метод диаграмматической верификации онтологий на основе табличного алгоритма для ALC.

4. Разработан набор формальных метрик для оценки визуальных представлений онтологий.

5. Произведены экспериментальные исследования разработанных методов.

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

0.1 Пересечение в СгарЬо1..............................................12

0.2 Диаграмма Венна для пересечения ..............................12

0.3 Обратная роль......................................................16

0.4 Транзитивная роль ................................................16

0.5 функциональная роль..............................................17

0.6 Иерархия ролей ....................................................18

0.7 Номинал ............................................................18

0.8 Ограничения кардинальности ролей..............................19

0.9 Примеры гиперграфов..............................................21

0.10 Дерево

пространств утверждений для концепта "Веган и не вегетарианец

24

0.11 Дерево

пространств утверждений для аксиомы "Веган - это вегетарианец

25

0.12 Архитектура приложения..........................................29

0.13 Меню приложения..................................................30

0.14 conjunction in Graphol..............................................39

0.15 Venn diagram for conjunction......................................39

0.16 Inverse role ..........................................................43

0.17 Transitive role ......................................................43

0.18 Functional role ......................................................44

0.19 Role hierarchy........................................................45

0.20 Nominal..............................................................45

0.21 Number restriction..................................................45

0.22 Examples of hypergraphs............................................48

0.23 Tree of statement spaces for the concept " Vegan and

non-vegetarian"......................................................50

0.24 A tree of statement spaces for the axiom " A vegan is a vegetarian" 52

0.25 Application Architecture............................................56

0.26 Application menu....................................................57

1.1 Диаграмма Венна для пересечение множеств А и В............66

1.2 Диаграмма Венна 1. Принадлежность............................66

1.3 Диаграмма Венна 2. Эквивалентность............................66

1.4 Диаграмма Венна 3. Включение..................................66

1.5 «Если у человека есть машина, значит, человек богат» .... 68

1.6 «Все мужчины, у которых есть машина, богаты» ..............68

1.7 «Возможно, Алекс богат»..........................................69

1.8 Рефлексивность ....................................................71

1.9 Симметричность ....................................................71

1.10 Транзитивность ....................................................71

1.11 форма концептуального графа ....................................72

1.12 кот на циновке ......................................................72

1.13 кот Джо-Джо на циновке ..........................................72

1.14 EG....................................................................73

1.15 «Джон едет в Бостон на автобусе»................................74

1.16 EG ....................................................................74

1.17 CG ....................................................................74

1.18 Концептуальные графы с вырезами..............................75

1.19 полный CG Совы ....................................................75

1.20 CG с вырезом Дау..................................................75

1.21 Пересечение в Graphol ..............................................80

1.22 Пересечение в Venn diagrams......................................80

1.23 Паучья диаграмма ..................................................82

1.24 Паучья диаграмма с конъюнкцией................................82

1.25 Диаграмма с ограничениями ......................................83

1.26 языка OWL 2 ........................................................92

1.27 Табличный алгоритм для ALC....................................98

2.1 Концепт в Logic Graphs......................100

2.2 Дополнение в Logic Graphs....................101

2.3 Пересечение в Logic Graphs ........................................101

2.4 Включение в Logic Graphs ........................................101

2.5 Экзистенциальное ограничение в Logic Graphs.........102

2.6 Объединение в Logic Graphs...................104

2.7 Эквивалентность в Logic Graphs.................104

2.8 Универсальное ограничение в Logic Graphs...........105

2.9 Принадлежность концепту в Logic Graphs ...........105

2.10 Принадлежность роли в Logic Graphs..............105

2.11 Обратная роль...........................107

2.12 Транзитивная роль ........................107

2.13 Функциональная роль.......................108

2.14 Включение ролей..........................109

2.15 Номинал ..............................110

2.16 Кардинальное ограничение....................110

2.17 ——-правило.............................111

2.18 П+-правило.............................112

2.19 П--правило.............................112

2.20 3+-правило.............................112

2.21 3--правило.............................113

2.22 С-правило .............................113

2.23 Противоречивое пространство утверждений ..........114

2.24 Алгоритм диаграмматической верификации для Logic Graphs 115

2.25 Аксиома (2.5) в Graphol ............................................121

2.26 Примеры графов..........................124

3.1 Дерево

пространств утверждений для концепта "Веган и не вегетарианец

128

3.2 Дерево

пространств утверждений для аксиомы "Веган - это вегетарианец

130

3.3 Меню приложения.........................135

3.4 Архитектура приложения.....................136

3.5 Визуализация онтологии FOAF в приложении.........137

0.1 Анализ полноты существующих инструментов визуализации

онтологий............................................................13

0.2 Дескрипционная логика ALC......................................14

0.3 Logic graphs для ALC..............................................15

0.4 Информационная оценка гиперграфов............................21

0.5 Logic graphs для онтологии DoCO................................22

0.6 Оценка полноты VOWL............................................26

0.7 Полнота Graphol....................................................27

0.8 Полнота LG..........................................................28

0.9 Сравнение информативности LG и Graphol......................29

0.10 Analysis of the completeness of existing ontology visualization

tools..................................................................40

0.11 Description Logic ALC..............................................41

0.12 Logic graphs for ALC................................................42

0.13 Information evaluation of hypergraphs..............................48

0.14 Logic graphs for ontologies DoCO..................................49

0.15 Completeness evaluation of VOWL ................................53

0.16 Completeness Graphol..............................................54

0.17 Completeness LG....................................................55

0.18 Comparison of the informativeness of LG and Graphol............56

1.1 Экзистенциальные графы..........................................70

1.2 Конструкторы DL визуализируются в рассмотренных инструментах ........................................................78

1.3 Визуальные языки VOWL, Graphol и Sova........................79

1.4 Синтаксис и семантика SHOIN....................................96

2.1 Функция интерпретации для Logic Graphs...........103

2.2 Дескрипционная логика ALC...................103

2.3 Логические графы для ALC ...................106

2.4 Расширение ALC до SHIFT....................106

2.5 Расширение SHIF до SHOIN...................109

2.6 Матрица инцидентности для аксиомы (2.5) в Graphol.....121

2.7 Оценка информативности графов................125

3.1 Логические графы для онтологии DoCO............127

3.2 Полнота VOWL ..........................131

3.3 Полнота Graphol..........................132

3.4 Полнота LG.............................133

3.5 Аксиомы DoCO в LGs и Graphol.................134

3.6 Матрица инцидентности для аксиомы 1 в LG..........134

3.7 Сравнение информативности LG и Graphol...........135

1. Ruskey Frank, Weston Mark. A survey of Venn diagrams // Electronic Journal of Combinatorics. — 1997. — Vol. 4, no. 3.

2. Peirce Charles Sanders. Collected papers of charles sanders peirce. — Harvard University Press, 1960. — Vol. 2.

3. Robin Richard S. Annotated catalogue of the papers of Charles S. Peirce. — 1967.

4. Sowa John F. Peirce's tutorial on existential graphs // Semiotica. — 2011. — Vol. 2011, no. 186. — Pp. 347-394.

5. Barwise Jon. An introduction to first-order logic // Studies in Logic and the Foundations of Mathematics. — Elsevier, 1977. — Vol. 90. — Pp. 5-46.

6. Smullyan Raymond, Logic First-Order. Springer, 1968. — 1995.

7. Borgida Alex. On the relative expressiveness of description logics and predicate logics // Artificial intelligence. — 1996. — Vol. 82, no. 1-2. — Pp. 353-367.

8. West Douglas Brent et al. Introduction to graph theory. — Prentice hall Upper Saddle River, 2001. — Vol. 2.

9. Gross Jonathan L, Yellen Jay. Handbook of graph theory. — CRC press, 2003.

10. Hitzler Pascal, Krotzsch Markus, Rudolph Sebastian. Foundations of semantic web technologies. — CRC press, 2009.

11. Sowa John F. Conceptual graphs for a data base interface // IBM Journal of Research and Development. — 1976. — Vol. 20, no. 4. — Pp. 336-357.

12. Sowa John F. Conceptual structures: information processing in mind and machine. — 1983.

13. Conceptual structures: Current research and practice / Timothy E Nagle, Janice A Nagle, Laurie L Gerholz, Peter W Eklund. — Ellis Horwood, 1992.

14. Roberts Don D. The Existential Graphs // Semantics Networks in Artificial Intelligence. — 1992. — Pp. 639-663.

15. Dau Frithjof. The logic system of concept graphs with negation: And its relationship to predicate logic. — Springer Science & Business Media, 2003. — Vol. 2892.

16. Chein Michel, Mugnier Marie-Laure. Graph-based knowledge representation: computational foundations of conceptual graphs. — Springer Science & Business Media, 2008.

17. Noy Natalya F, McGuinness Deborah L et al. Ontology development 101: A guide to creating your first ontology. — 2001.

18. Staab Steffen, Studer Rudi. Handbook on ontologies. — Springer Science & Business Media, 2010.

19. W3C Semantic Web FAQ. — URL: https://www.w3.org/RDF/FAQ (online; accessed: 2020-06-4).

20. Ontology visualization methods and tools: a survey of the state of the art / Marek Dudas, Steffen Lohmann, Vojtech Svatek, Dmitry Pavlov // The Knowledge Engineering Review. — 2018. — Vol. 33.

21. Lohmann S, Negru S, Haag F, Ertl T. Visualizing ontologies with VOWL. Semant. Web 7 (4), 399-419 (2016).

22. Antoniazzi Francesco, Viola Fabio. RDF graph visualization tools: A survey // 2018 23rd Conference of Open Innovations Association (FRUCT) / IEEE. — 2018. — Pp. 25-36.

23. OwlViz. — URL: http://www.co-ode.org/downloads/owlviz/ (online; accessed: 2020-09-4).

24. Liebig Thorsten, Noppens Olaf. OntoTrack: A semantic approach for ontology authoring // Journal of Web Semantics. — 2005. — Vol. 3, no. 2-3. — Pp. 116-131.

25. A novel approach to visualizing and navigating ontologies / Enrico Mot-ta, Paul Mulholland, Silvio Peroni et al. // International Semantic Web Conference / Springer. — 2011. — Pp. 470-486.

26. Eklund Peter, Roberts Nataliya, Green Steve. Ontorama: Browsing rdf ontologies using a hyperbolic-style browser // First International Symposium on Cyber Worlds, 2002. Proceedings. / IEEE. — 2002. — Pp. 405-411.

27. Falconer S. OntoGraf Protege plugin.

28. Falconer Sean M, Callendar Chris, Storey Margaret-anne. FLEXVIZ: visualizing biomedical ontologies on the web // International Conference on Biomedical Ontology, Software Demonstration / Citeseer. — 2009.

29. Alani Harith. TGVizTab: An ontology visualisation extension for Protege. — 2003.

30. Olsviz. — URL: http://ols.wordvis.com (online; accessed: 2020-09-4).

31. Scalable visualization of semantic nets using power-law graphs / Ajaz Hussain, Khalid Latif, Aimal Tariq Rextin et al. // Applied Mathematics & Information Sciences. — 2014. — Vol. 8, no. 1. — P. 355.

32. SOVA. — URL: http://protegewiki.stanford.edu/wiki/SOVA (online; accessed: 2020-09-4).

33. Krivov Sergey, Williams Richard, Villa Ferdinando. GrOWL: A tool for visualization and editing of OWL ontologies // Journal of Web Semantics. — 2007. — Vol. 5, no. 2. — Pp. 54-57.

34. The Simple Web-based Tool for Visualization and Sharing of Semantic Data and Ontologies. / Dmitry Mouromtsev, Dmitry Pavlov, Yury Emelyanov et al. // International Semantic Web Conference (Posters & Demos). — 2015.

35. Grapffoo. — URL: https://essepuntato.it/graffoo/specification/ (online; accessed: 2020-09-4).

36. Graphol. — URL: Http://www.obdasystems.com/graphol (online; accessed: 2020-09-4).

37. Vowl. — URL: Http://vowl.visualdataweb.org/ (online; accessed: 2020-09-4).

38. Bosca Alessio, Bonino Dario, Pellegrino Paolo. OntoSphere: more than a 3D ontology visualization tool. // Swap / Citeseer. — 2005.

39. Somasundaram Ramanathan. OntoSELF: A 3D ontology visualization tool: Ph.D. thesis / Miami University. — 2007.

40. Guo Simon Suigen, Chan Christine W. A tool for ontology visualizaiton in 3D graphics: Onto3DViz // CCECE 2010 / IEEE. — 2010. — Pp. 1-4.

41. Interactive 3d exploration of rdf graphs through semantic planes / Fabio Viola, Luca Roffia, Francesco Antoniazzi et al. // Future Internet. — 2018. — Vol. 10, no. 8. — P. 81.

42. Gil Joseph, Howse John, Kent Stuart. Formalizing spider diagrams // Proceedings 1999 IEEE Symposium on Visual Languages / IEEE. — 1999. — Pp. 130-137.

43. Stapleton Gem. Tech. Rep.: : School of Computing, Mathematical and Information Sciences, 2004.

44. Howse John, Stapleton Gem, Taylor John. Spider diagrams // LMS Journal of Computation and Mathematics. — 2005. — Vol. 8. — Pp. 145-194.

45. Stapleton Gem. Reasoning with Constraint Diagrams. — 2004.

46. Shin Sun-Joo. The logical status of diagrams. — Cambridge University Press, 1994.

47. Flower Jean, Masthoff Judith, Stapleton Gem. Generating proofs with spider diagrams using heuristics // Proceedings of Distributed Multimedia Systems, International Workshop on Visual Languages and Computing / Knowledge Systems Institute. — 2004. — Pp. 279-285.

48. Patrascoiu Octavian, Thompson Simon, Rodgers Peter. Tableaux for diagrammatic reasoning // Proceedings of the 2005 International Workshop on Visual Languages and Computing / Knowledge Systems Institute. — 2005. — Pp. 279-286.

49. Kent Stuart. Constraint diagrams: visualising assertions in object-oriented models // online] Proc. of. — 1997. — Pp. 5-9.

50. Fish Andrew, Flower Jean, Howse John. The semantics of augmented constraint diagrams // Journal of Visual Languages & Computing. — 2005. — Vol. 16, no. 6. — Pp. 541-573.

51. Harel David. On visual formalisms // Communications of the ACM. — 1988. — Vol. 31, no. 5. — Pp. 514-530.

52. Larkin Jill H, Simon Herbert A. Why a diagram is (sometimes) worth ten thousand words // Cognitive science. — 1987. — Vol. 11, no. 1. — Pp. 65-100.

53. Moody Daniel. The "physics" of notations: toward a scientific basis for constructing visual notations in software engineering // IEEE Transactions on software engineering. — 2009. — Vol. 35, no. 6. — Pp. 756-779.

54. Goodman Nelson. Languages of art: An approach to a theory of symbols.

— Hackett publishing, 1976.

55. Winn William. Encoding and retrieval of information in maps and diagrams // IEEE Transactions on Professional Communication. — 1990.

— Vol. 33, no. 3. — Pp. 103-107.

56. Petre Marian. Why looking isn't always seeing: readership skills and graphical programming // Communications of the ACM. — 1995. — Vol. 38, no. 6. — Pp. 33-44.