Inproceedings,
On computing minimal conflicts for ontology debugging
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.
