Acyclicity Conditions and their Application to Query Answering in Description Logics
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
Abstract. 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 profile, 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 profile may be practically feasible.
Published at KR2012 (Conference paper)
Download PDF (last update: July 13 2012)
Citation details
- 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. In Gerhard Brewka, Thomas Eiter, Sheila A. McIlraith, eds.: Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), pp. 243–253. AAAI PressProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2012.
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 = {Proceedings of the 13th International Conference
on Principles of Knowledge Representation and
Reasoning (KR'12)},
editor = {Gerhard Brewka and Thomas Eiter and
Sheila A. McIlraith},
year = {2012},
publisher = {AAAI Press},
pages = {243--253}
}
Remarks
This work is completely subsumed by the journal article Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies.
The above link points to the extended technical report that includes all proofs. The AAAI website has the conference version of this paper.
