Acyclicity notions for existential rules and their application to query answering in ontologies

DOI10.1613/JAIR.3949zbMATH Open1270.68295arXiv1406.4110OpenAlexW3102313542MaRDI QIDQ2846569FDOQ2846569

Authors: Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang 

Publication date: 6 September 2013

Published in: The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1406.4110

Recommendations

• Extending acyclicity notions for existential rules
• Characterizing boundedness in chase variants
• Restricted chase termination for existential rules: a hierarchical approach and experimentation
• Restricted Chase Termination: A Hierarchical Approach and Experimentation
• Taming the infinite chase: query answering under expressive relational constraints

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Knowledge representation (68T30)

Cited In (21)

• Preserving constraints with the stable chase
• Domain expansion for ASP-programs with external sources
• Query inseparability for \(\mathcal{ALC}\) ontologies
• A Single Approach to Decide Chase Termination on Linear Existential Rules
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted Chase Termination: A Hierarchical Approach and Experimentation
• Computing optimal repairs of quantified ABoxes w.r.t. static \(\mathcal{EL}\) TBoxes
• Reasoning with ontologies
• Semi-oblivious chase termination: the sticky case
• Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin
• Restricted chase termination for existential rules: a hierarchical approach and experimentation
• Characterizing boundedness in chase variants
• On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
• Extending acyclicity notions for existential rules
• Logical foundations of information disclosure in ontology-based data integration
• Craig interpolation with clausal first-order tableaux
• Uniform Restricted Chase Termination
• Query answering over inconsistent knowledge bases: a probabilistic approach
• Logic, languages, and rules for web data extraction and reasoning over data
• Generative Datalog with continuous distributions

This page was built for publication: Acyclicity notions for existential rules and their application to query answering in ontologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2846569)