태블로 알고리즘 기반 온톨로지 추론 엔진의 속도 향상을 위한 방법 = Methods to Reduce Execution Time of Ontology Reasoners based on Tableaux Algorithm

국문 초록 (Abstract)

온톨로지의 크기가 대형화됨에 따라, 온톨로지 내부 구조는 점점 복잡해지고 있다. 따라서 온톨로지 구축과정에서 발생하는 여러 가지 논리적 오류를 찾아내어 수정하는 것은 매우 어려운 작업이 되고 있다. Minerva[1]는 OWL로 작성한 온톨로지 중 논리적 오류를 갖는 개념들을 자동으로 탐지하고, 개념간의 계층 관계를 추론하기 위해 개발된 온톨로지 추론 엔진이다. Minerva를 포함한 대부분의 서술 논리 기반의 온톨로지 추론 엔진은 태블로 알고리즘(Tableau Algorithm)을 기반으로 동작한다. 태블로 알고리즘을 그대로 적용할 경우 시간 및 공간 복잡도가 상당히 높아지기 때문에 다양한 최적화 기법이 필요하다. 본 논문에서는 태블로 알고리즘을 사용하는 온톨로지 추론 엔진의 속도를 향상시키는 최적화 기법들을 제안한다. 제안한 기법들은 선행 연구로서 이미 개발된 온톨로지 추론엔진 Minerva에 적용되어 성능향상을 이끌어 내었다.

다국어 초록 (Multilingual Abstract)

As size of ontology has been increased more and more, the descriptions in the ontologies become more complicated. Therefore finding and modifying unsatisfiable concepts is hard work in ontology construction process. Minerva is an ontology reasoner which detects unsatisfiable concepts automatically and infers subsumption relation between concepts in ontology. Most description logic based ontology reasoners (including Minerva) work using tableaux algorithm. Because tableaux algorithm is very costly, ontology reasoners need various optimization methods. In this paper, we propose optimizing methods to reduce execution time of tableaux algorithm based ontology reasoner. Proposed methods were applied to Minerva which was developed as preceding study result. In consequence the new version Minerva shows high performance.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 기본 개념
• 3. 선행 연구
• 4. 태블로 알고리즘 기반 온톨로지 추론 엔진의 속도 향상을 위한 최적화 기법
• 5. 실험 및 평가
• 6. 결론 및 향후 연구
• 참고문헌

참고문헌 (Reference)

• 1 김제민, "태블로 알고리즘 기반 온톨로지 추론 엔진의 속도 향상을 위한 방법" 한국정보과학회 36 (36): 153-160, 2009
• 2 권순현, "온톨로지 포함관계 추론을 위한 최적화된 검색방법" 2008
• 3 U. Hustadt, "Reasoning in Description Logics with a Concrete Domain in the Framework of Resolution" 353-357, 2004
• 4 V. Haarslev, "Racer: A Core Inference Engine for the Semantic Web. In Proceedings of the 2nd International Workshop on Evaluation of Ontology-based Tools(EON2003)" 27-36, 2003
• 5 Evren Sirin, "Pellet: A practical OWL-DL reasoner" 5 (5): 2007
• 6 Dmitry Tsarkov, "FaCT++ description logic reasoner: System description" IJCAR 2006
• 7 Min-su Jang, "Bossam: an extended rule engine for OWL Inferencing" 2004
• 8 F. Baader, "Basic description logics. IN : The Description Logic Handbook: Theory, Implementation, and Applications" Cambridge University Press 43-95, 2003
• 9 Franz Baader, "An Empirical Analysis of Optimization Techniques for Terminological Representation System, Principles of Knowledge Representation and reasoning -" 1992