Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
Abstract. Answering conjunctive queries (CQs) over a set of facts extended with existential rules
is a prominent problem in knowledge representation and databases. This problem can be
solved using the chase algorithm, which extends the given set of facts with fresh facts in
order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in
the resulting set of facts. The chase, however, does not terminate necessarily, and checking
whether the chase terminates on a given set of rules and facts is undecidable. Numerous
acyclicity notions were proposed as sufficient conditions for chase termination. In this
paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and
model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the
known acyclicity notions and establish a complete taxonomy of all notions known to us.
Finally, we show that MFA and MSA generalise most of these notions.
Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.
Published at Journal of Artificial Intelligence Research (Journal paper)
Download PDF (last update: July 30 2013)
Citation details
- Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang. Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies. In Journal of Artificial Intelligence Research, volume 47, pp. 741–808. AI Access FoundationProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2013.
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 Notions for Existential Rules
and Their Application to Query Answering in
Ontologies},
journal = {J Art. Int. Research},
volume = {47},
year = {2013},
pages = {741--808},
publisher = {AI Access Foundation}
}
Remarks
This work completely subsumes, extends, and improves earlier results on Acyclicity Conditions and their Application to Query Answering in Description Logics.
