Output details
11 - Computer Science and Informatics
University of Oxford
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
<22>
Answering conjunctive queries over facts extended with existential rules is a prominent problem in KR and databases, and is closely related to query answering in Horn fragments of the OWL 2 ontology language. This paper introduces new acyclicity conditions that guarantee termination of the widely used chase materialisation procedure, and that generalise existing conditions. It is shown that query answering for acyclic ontologies is of lower complexity than for general ontologies, and that many commonly used OWL 2 ontologies satisfy one of our new conditions. These results suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.