A Tractable Approach to ABox Abduction over Description Logic Ontologies


  • Jianfeng Du Guangdong University of Foreign Studies
  • Kewen Wang Griffith University
  • Yi-Dong Shen Chinese Academy of Sciences




ABox abduction, abductive reasoning, query abduction problem, description logics, first-order rewritable


ABox abduction is an important reasoning mechanism for description logic ontologies. It computes all minimal explanations (sets of ABox assertions) whose appending to a consistent ontology enforces the entailment of an observation while keeps the ontology consistent. We focus on practical computation for a general problem of ABox abduction, called the query abduction problem, where an observation is a Boolean conjunctive query and the explanations may contain fresh individuals neither in the ontology nor in the observation. However, in this problem there can be infinitely many minimal explanations. Hence we first identify a class of TBoxes called first-order rewritable TBoxes. It guarantees the existence of finitely many minimal explanations and is sufficient for many ontology applications. To reduce the number of explanations that need to be computed, we introduce a special kind of minimal explanations called representative explanations from which all minimal explanations can be retrieved. We develop a tractable method (in data complexity) for computing all representative explanations in a consistent ontology. xperimental results demonstrate that the method is efficient and scalable for ontologies with large ABoxes.




How to Cite

Du, J., Wang, K., & Shen, Y.-D. (2014). A Tractable Approach to ABox Abduction over Description Logic Ontologies. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8852



AAAI Technical Track: Knowledge Representation and Reasoning