Efficient classification of complex ontologies

Abstract

Description logics (DLs) are knowledge representation languages that provide the theoretical underpinning for modern ontology languages such as OWL and serve as the basis for the development of ontology reasoners. The task of ontology classification is to compute the subsumption relationships between all pairs of atomic concepts in an ontology, which is the foundation for other ontology reasoning problems. There are two types of mainstream reasoners to perform ontology classification: 1) tableau-based reasoners usually support very expressive DLs, but they may not be efficient for large and highly cyclic ontologies. 2) consequence-based reasones are typically significantly faster than tableau-based reasoners, but they support less expressive DLs. It is difficult to extend the consequence-based reasoners directly to support more expressive DLs. In the present thesis, we propose a weakening and strengthening based approach for ontology classification, which aims to extend the capability of an efficient reasoner for a less expressive base language Lb (Lb-reasoner) to support a more expressive language. The approach approximates the target ontology by a weakened version and a strengthened version in Lb. Their subsumptions are a subset and a superset of the subsumptions of the target ontology. There are two cases: (1) the subsumptions of the strengthened ontology are the same as that of the target ontology; (2) there may be more subsumptions in the strengthened ontology, which is therefore unsound. In case (1) which we call soundness-preserved strengthening, we classify only the strengthened ontology with the Lb-reasoner to get the final classification results. In case (2) which we call soundness-relaxed strengthening, a hybrid approach is employed – we first classify both the weakened and strengthened ontologies with the Lb-reasoner, and then use a full-fledged (hyper)tableau-based assistant reasoner to check whether the subsumptions implied by the strengthened ontology are also implied by the target ontology. We first study the general principles to apply weakening and strengthening to extend an Lb-reasoner for a DL language that has one more constructor than Lb, i.e., single extension. Then we study the combination of several single extensions for multiple extended constructors for the reasoner, i.e., multiple extension. Based on the general principles, we investigate two single extensions from the ALCH description language to ALCH(D)¯ and ALCHI with soundness-preserved strengthening, as well as a single extension from ALCH to ALCHO with soundness-relaxed strengthening. Then, we show how to combine them into multiple extensions from ALCH to ALCHI(D)¯, ALCHOI, ALCHO(D)¯, and ALCHOI(D)¯. The soundness and completeness of all the single and multiple extensions are proved. We also develop a prototype ALCHOI(D)¯-reasoner, WSClassifier, based on the proposed approach. We experiment with and evaluate WSClassifier on large and highly cyclic real-world ontologies such as FMA and Galen ontologies, the required languages of which are beyond the capability of the current efficient consequence-based reasoners. The experiments show that on most of these ontologies, WSClassifier outperforms or significantly outperforms conventional (hyper)tableau-based reasoners.