Atomic Decomposition-based Ontology Classification

Abstract

For Web Ontology Language (OWL) 2 ontologies, classification is the central reasoning task. Classification is computationally expensive, 2$\textsc{NExpTime}$-complete for a worst-case complexity. Several highly-optimised reasoners have been designed for different fragments of OWL 2. Some of these exploits different notions of modularity, including the atomic decomposition (AD), to further optimise their performance. However, these called modular reasoning approaches are all black box approaches that allow reasoning over each module independently and combining the results to achieve sound and complete results for the original ontologies. These delegate reasoners only share results with each other. In this thesis, we further investigate a range of ways to use the AD to further optimize the classification. We first explore the property of AD to avoid some subsumption tests (STs), called avoidance, during classification. Ontology modules overlapping causes duplication of subsumption tests. We build our approach to avoid this duplication then. We also design an AD-aware order to further avoid STs in classification. We then design and implement our approach, called $\mathsf{ReAD}$ which works with these good features we explored, e.g. avoidance, duplication avoidance, delegate reasoners, order. We investigate how $\mathsf{ReAD}$ classifies the whole ontology or modules with or without parallelization. We empirically evaluate our approaches with a set of complex BioPortal ontologies and $\mathsf{SNOMED \: CT}$ ontologies. Besides, we design a label, called Positive Boolean Formulae (PBFs), for atoms in AD for efficiently extracting modules. This approach has the potential for optimizing the computation of AD. Finally, we show our approach still has good potential for further exploration. Our empirical evaluation results show that using a coarsening AD in our approach is a potential way to further optimise the classification.

Date of Award	31 Dec 2022
Original language	English
Awarding Institution	The University of Manchester
Supervisor	Uli Sattler (Supervisor) & Bijan Parsia (Supervisor)