Restricted Chase (Non)Termination for Existential Rules with Disjunctions
Restricted Chase (Non)Termination for Existential Rules with Disjunctions
David Carral, Irina Dragoste, Markus Krötzsch
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 922-928.
https://doi.org/10.24963/ijcai.2017/128
The restricted chase is a sound and complete algorithm for conjunctive query answering over ontologies of disjunctive existential rules. We develop acyclicity conditions to ensure its termination. Our criteria cannot always detect termination (the problem is undecidable), and we develop the first cyclicity criteria to show non-termination of the restricted chase. Experiments on real-world ontologies show that our acyclicity notions improve significantly over known criteria.
Keywords:
Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning
Knowledge Representation, Reasoning, and Logic: Description Logics and Ontologies
Knowledge Representation, Reasoning, and Logic: Knowledge Representation Languages
Knowledge Representation, Reasoning, and Logic: Logics for Knowledge Representation