Сокращение пространства поиска интерпретаций за счет обнаружения изоморфных концептов

Abstract

The article considers an algorithm for logic inference on knowledge bases described in OWL language which is based on description logic formalism. The considered algorithm has an NEXPTIME complexity which makes it inapplicable in practice. By now certain optimizations, reducing worktime of the algorithm, have been developed, but nevertheless some real knowledge bases can’t be classified in satisfactory time. The main part of the article is devoted to developing of a new method on reducing the number of interpretations under consideration by tableau algorithm. The article demonstrates the proof of correctness for the given method and offers estimation of the number of nonconsidered interpretations. The authors briefly describe the structures, used for concepts representation, and determine the modification of Edmonds’ method for the search of identical substructures in concept descriptions. The developed method is implemented in TReasoner system. At the end of the article testing results are presented. Testing was performed with the help of data of the Description Logic International Workshop DL’98 in comparison with such popular systems as JFact and HermiT.

В статье рассматривается алгоритм осуществления логического вывода в базах знаний, описанных на языке OWL, который основан на формализме дескрипционных логик. Рассматриваемый алгоритм имеет экспоненциальную вычислительную сложность, что делает его не применимым на практике. К настоящему моменту были разработаны оптимизации, существенно сокращающие время работы алгоритма, но некоторые реальные базы знаний не могут быть классифицированы за приемлемое время. Основная часть статьи посвящена разработке метода сокращения количества рассматриваемых интерпретаций табличным алгоритмом за счет исключения из поиска изоморфных интерпретаций. Для данного метода представлено доказательство корректности работы и дана оценка количеству не рассматриваемых интерпретаций. В статье приводится краткое описание структур, используемых для представления концептов, и приведена модификация метода Эдмондсона для поиска идентичных подструктур в описании концептов. Разработанный метод был реализован в системе TReasoner. В заключение представлены результаты тестирования на данных международного симпозиума по дескрипционным логикам DL'98 в сравнении с наиболее популярными системами логического анализа онтологий JFact и HermiT.