The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules

Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja, Sebastian RudolphSebastian Rudolph

ISBN: 978-1-956792-05-8
ISSN: 2334-1033
Download
Slides
DOI Link

Piotr Ostropolski-Nalewaja, Sebastian Rudolph
The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules
In Pierre Marquis, Magdalena Ortiz, Maurice Pagnucco, eds., Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, 574–584, 2024. IJCAI Organization

Details
Bibtex

KurzfassungAbstract
Extensive research in the field of ontology-based query answering has led to the identification of numerous fragments of existential rules (also known as tuple-generating dependencies) that exhibit decidable answering of atomic and conjunctive queries. Motivated by the increased theoretical and practical interest in navigational queries, this paper considers the question for which of these fragments decidability of querying extends to regular path queries (RPQs). In fact, decidability of RPQs has recently been shown to generally hold for the comprehensive family of all fragments that come with the guarantee of universal models being reasonably well-shaped (that is, being of finite cliquewidth). Yet, for the second major family of fragments, known as finite unification sets (short: fus), which are based on first-order-rewritability, corresponding results have been largely elusive so far. We complete the picture by showing that RPQ answering over arbitrary fus rulesets is undecidable. On the positive side, we establish that the problem is decidable for the prominent fus subclass of sticky rulesets, with the caveat that a very mild extension of the RPQ formalism turns the problem undecidable again.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT, ScaDS.AI
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{OR2024,
  author    = {Piotr Ostropolski-Nalewaja and Sebastian Rudolph},
  title     = {The Sticky Path to Expressive Querying: Decidability of
               Navigational Queries under Existential Rules},
  editor    = {Pierre Marquis and Magdalena Ortiz and Maurice Pagnucco},
  booktitle = {Proceedings of the 21st International Conference on Principles of
               Knowledge Representation and Reasoning},
  publisher = {IJCAI Organization},
  year      = {2024},
  pages     = {574{\textendash}584},
  doi       = {10.24963/kr.2024/54}
}