Refereed Papers

Track: Semantic Web I

Paper Title:
Computing Minimum Cost Diagnoses to Repair Populated DL-based Ontologies

Authors:

• Jianfeng Du(Chinese Academy of Sciences)
• Yi-Dong Shen(Chinese Academy of Sciences)

Abstract:
Ontology population is prone to cause inconsistency because the populating process is imprecise or the populated data may conflict with the original data. By assuming that the intensional part of the populated DL-based ontology is fixed and each removable ABox assertion is given a removal cost, we repair the ontology by deleting a subset of removable ABox assertions in which the sum of removal costs is minimum. We call such subset a minimum cost diagnosis. We show that, unless P=NP, the problem of finding a minimum cost diagnosis for a DL-Lite ontology is insolvable in PTIME w.r.t. data complexity. In spite of that, we present a feasible computational method for more general (i.e. SHIQ) ontologies. It transforms a SHIQ ontology to a set of disjoint propositional programs, thus reducing the original problem into a set of independent subproblems. Each such subproblem computes an optimal model and is solvable in logarithmic calls to a SAT solver. Experimental results show that the method can handle moderately complex ontologies with over thousands of ABox assertions, where all ABox assertions can be assumed removable.

PDF version

Inquiries can be sent to: