Inproceedings,

On computing minimal conflicts for ontology debugging

, , and .
MBS 2008 - Workshop on Model Based Systems at ECAI 2008, Patras. Greece, page 7-12. University of Patras, (2008)

Abstract

Ontology debugging is an important stage of the ontology life-cycle and supports a knowledge engineer during the ontology development and maintenance processes. Model based diagnosis is the basis of many recently suggested ontology debugging methods. The main difference between the proposed approaches is the method of computing required conflict sets, i.e. a sets of axioms such that at least one axiom of each set should be changed (removed) to make ontology coherent. Conflict set computation is, however, the most time consuming part of the debugging process. Consequently, the choice of an efficient conflict set computation method is crucial for ensuring the practical applicability of an ontology debugging approach. In this paper we evaluate and compare two popular minimal conflict computation methods: QUICKXPLAIN and SINGLE JUST. First, we analyze best and worst cases of the required number of coherency checks of both methods on a theoretical basis assuming a black-box reasoner. Then, we empirically evaluate the run-time efficiency of the algorithms both in black-box and in glass-box settings. Although both algorithms were designed to view the reasoner as a black box, the exploitation of specific knowledge about the reasoning process (glass-box) can significantly speed up the run-time performance in practical applications. Therefore, we present modifications of the original algorithms that can also exploit specific data from the reasoning process. Both a theoretical analysis of best- and worst-case complexity as well as an empirical evaluation of run-time performance show that QUICKXPLAIN is preferable over SINGLE JUST.

Tags

Users

  • @mschuber

Comments and Reviews