Computing Minimum Cost Diagnoses to Repair Populated DL-based Ontologies
Ontology population is prone to cause inconsistency because the populating process is imprecise or the populated data may con.ict with the original data. By assuming that the intensional part of the populated DL-based ontology is.xed 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.nding 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.
Ontologies Description Logics Disjunctive Datalog Diagnosis
Jianfeng Du Yi-Dong Shen
State Key Laboratory of Computer Science,Institute of Software, Chinese Academy of Sciences Graduate State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences Beijing
国际会议
第十七届国际万维网大会(the 17th International World Wide Web Conference)(WWW08)
北京
英文
2008-04-21（万方平台首次上网日期，不代表论文的发表时间）