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


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.


Description logics, Rule languages