General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase

The disjunctive skolem chase is a sound, complete, and potentially non-terminating procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. We develop novel acyclicity and cyclicity notions for this procedure; that is, we develop sufficient conditions to determine chase termination and non-termination. Our empirical evaluation shows that our novel notions are significantly more general than existing criteria.

Authors

• Lukas Gerlach Knowledge-Based Systems Group, TU Dresden, Dresden, Germany
• David Carral LIRMM, Inria, University of Montpellier, CNRS, Montpellier, France

Keywords

• KRR: Automated Reasoning and Theorem Proving
• KRR: Computational Complexity of Reasoning
• KRR: Description Logics
• KRR: Knowledge Representation Languages
• KRR: Logic Programming
• KRR: Ontologies and Semantic Web
• KRR: Other Foundations of Knowledge Representation & Reasoning