Module-based classification of OWL ontologies

UoM administered thesis: Phd


Classification is a core reasoning service provided by most OWL reasoners. Classification in general is hard - up to 2NExptime for SROIQ(D), the Description Logic which is underpinning the Web Ontology Language (OWL). While it has been shown that classification is practical for a wide range of inputs, there are still ontologies for which classification takes an unreasonable amount of time for purposes such as ontology engineering (frequent classifications after updates). A natural optimisation strategy is divide and conquer, that is, to decompose the ontology into subsets which are hopefully easier to classify and whose classifications can be combined into a complete classification of the whole ontology. Unfortunately, an arbitrary subset may not be self-contained, i.e. it might be missing information that is needed to determine entailments over its signature. Moreover, such a subset can be potentially harder to classify than the whole ontology. In order to mitigate those problems, classification preserving decompositions (CPDs) must be designed with care that they support complete classification which is, in practice, more efficient than monolithic classification. Locality-based modules are subsets of an ontology that provide certain guarantees with respect to the entities (concepts, roles) in its signature - in particular, modules are self-contained. In this thesis we explore the use of syntactic locality-based modules for underpinning classification-preserving decompositions. In particular, we empirically explore their potential to avoid subsumption tests and reduce subsumption test hardness and weigh those benefits against detrimental effects such as overhead (for example the time it takes to compute the decomposition) and redundancy (a consequence of potentially overlapping chunks in the decomposition). The main contributions of this thesis are an in-depth empirical characterisation of these effects, an extensible framework for observing CPDs in action up until a granularity of individual subsumption tests, a large, public corpus of observations and its analysis and insights on experimental methodologies around OWL reasoning.


Original languageEnglish
Awarding Institution
Award date1 Aug 2016