Курдюков Н.С.

Рязанский Государственный Радиотехнический Университет, Россия

Анализ вычислительной сложности логического вывода для языков веб-онтологий

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

В данной статье описываются способы вычисления сложности логического вывода и основные методы ее снижения на примере языка web-онтологий OWL 2 QL, являющегося одним из инструментов формата Semantic web.

Определим онтологию O как двойку: O=<Tbox, Abox> где Tbox – множество аксиом, Abox – множество утверждений. Входными параметрами влияющими на вычислительную сложность задач логического вывода являются: размер TBox, размер ABox, размер запроса – число параметров запроса q.

Для задач логического вывода различают три способа вычислить сложность, перечисленные далее[1].

1. Сложность относительно данных: сложность оценивается как функция от размера Abox. Это используется для логик, специализирующихся на больших размерах Abox, к примеру, для задач онтологического доступа к базам данных.

2. Сложность относительно онтологии и данных: сложность оценивается как функция от размера Tbox и Abox. Это используется, когда Tbox может быть очень большим, и его размером нельзя пренебрегать.

3. Комбинированная сложность: сложность оценивается как функция от размера q, Tbox, и Abox. Это обычно применяется для очень выразительных логик.

Снижение вычислительной сложности алгоритмов обычно достигается за счет ограничения выразительности логики. Так же сложность можно снизить за счет изобретения оптимальных алгоритмов. Рассмотрим эти случаи на примере языка OWL 2 QL[4]. Данный профиль языка OWL 2 основан на одной из логик семейства DL-Lite, именуемой DL-Lite_R.

Сложность относительно онтологии и данных для стандартных задач вывода достигает PTime за счет отсутствия возможности привязки ролей к конкретным концептам и ограничения возможности выразить дизъюнкцию концептов[2].

Сложность относительно данных для алгоритмов ответа на запросы в Dl-lite_R достигает LogSpace за счет методов переписывания запросов к логике предикатов, являющейся фактически логикой реляционных баз данных[2]. Проблема оценки запросов первого порядка к базам данных входит в класс задач AC⁰[2].

AC⁰⊊ LogSpace

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

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

Важное различие между семейством DL-Lite и OWL 2 QL заключается в статусе предположения уникального имени (UNA): UNA принято в рамках логики DL-Lite, но не принято в OWL2. Вместо этого синтаксис OWL2 обеспечивает явные средства для того, чтобы сказать, что a и b это один и тот же индивид (sameAs) или же наоборот (differentFrom). В целях обеспечения постоянной сложности задач логического вывода на онтологиях по стандарту OWL 2 QL, было решено не включать возможности определения функциональных зависимостей и числовых ограничений между концептами, при которых вычислительная сложность зависит от принятия UNA[2,4].

Проведенные исследования этой области помогли выбрать язык веб-онтологий OWL 2 QL для создания системы основанного на онтологиях доступа к данным веб-сервисов. Алгоритмы ответа на запрос для языка OWL 2 QL были апробированы на более чем 1000 записях 3-х баз данных СУБД MySQL, взаимодействующих между собой, и решили свою задачу, не переходя за границу рассчитанной сложности.

Литература:

1. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The description logic handbook: Theory, implementation, and applications. Cambridge University Press, 2nd edition, 2010.

2. Alessandro Artale, Diego Calvanese, Roman Kontchakov,and Michael Zakharyaschev. The DL-Lite family and relations. J. of Artificial Intelligence Research, 36:1-69, 2009.

3. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528.

4. OWL 2 Web Ontology Language Document Overview. [Электронный ресурс]: Официальный сайт международного консорциума W3C — Режим доступа: http://www.w3.org/TR/owl2-overview/