Acyclicity Conditions and their Application to Query Answering in Description Logics

Bernardo Cuenca GrauBernardo Cuenca Grau, Ian HorrocksIan Horrocks, Markus KrötzschMarkus Krötzsch, Clemens KupkeClemens Kupke, Despoina MagkaDespoina Magka, Boris MotikBoris Motik, Zhe WangZhe Wang

Download

Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang
Acyclicity Conditions and their Application to Query Answering in Description Logics
Proc. 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12), 243–253, June 2012. AAAI Press

Details
Bibtex

KurzfassungAbstract
Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a fundamental reasoning problem although undecidable due to non-termination of the main reasoning algorithm used—the chase. Several acyclicity conditions have been formulated that ensure chase termination. In this paper, we show that acyclicity can also be practically relevant for description logic (DL) reasoning. Due to the high complexity of answering CQs over DL ontologies, applications often solve this problem using materialisation, in which ontology consequences are precomputed using variants of the chase. Due to the non-termination problem, the execution of the algorithm is restricted only to rules that fall within the OWL 2 RL proﬁle, which results in incomplete reasoning. After presenting two novel acyclicity conditions (model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA)), we investigate the practical applicability of these and other acyclicity conditions for DL query answering. Our experiments reveal that many existing ontologies are MSA and that materialisation is typically not too large. Thus, our results suggest that principled, materialisation-based reasoning for ontologies beyond the OWL 2 RL proﬁle may be practically feasible.
Bemerkung: Note: This work is completely subsumed by the journal article Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{GHKKMMW2012,
  author    = {Bernardo Cuenca Grau and Ian Horrocks and Markus Kr{\"{o}}tzsch
               and Clemens Kupke and Despoina Magka and Boris Motik and Zhe Wang},
  title     = {Acyclicity Conditions and their Application to Query Answering in
               Description Logics},
  booktitle = {Proc. 13th International Conference on Principles of Knowledge
               Representation and Reasoning (KR'12)},
  publisher = {AAAI Press},
  year      = {2012},
  month     = {June},
  pages     = {243{\textendash}253}
}