Glass-Box Debugging Algorithm Based on Unsatisfiable Dependent Paths

Abstract

Calculating the minimal unsatisfiability-preserving sub-TBoxes (MUPS) for an unsatisfiable concept using the glass-box debugging method is a key reasoning service in ontology debugging. However, the glass-box method is limited as it can easily fall into an unnecessary expansion, especially in the process of non-deterministic expansion. An efficient method to solve this problem is to pre-select a set of relevant axioms involved in the unsatisfiability. For this purpose, we propose an optimization technique based on the unsatisfiable dependent path to avoid unnecessary expansion. The basic idea is to construct unsatisfiable dependent paths based on three basic conflict patterns and then obtain a conflict set from the unsatisfiable dependent paths. Accordingly, all the unsatisfiable concepts can be found and their MUPS can be calculated on the basis of the conflict set. Our experimental results show that the proposed method works well on real large-scale incoherent TBoxes.

Keywords

• Ontology debugging
• MUPS
• glass-box algorithm
• unsatisfiable dependent path
• conflict set