Browse wiki
From International Center for Computational Logic
Extensive research in the field of ontolog … 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.alism turns the problem undecidable again. +
@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}
}
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}
}
Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning +
Ostropolski-Nalewaja +
Piotr +
Piotr Ostropolski-Nalewaja, Sebastian Rudo … Piotr Ostropolski-Nalewaja, Sebastian Rudolph<br/> '''[[Inproceedings3388|<b>The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules</b>]]''' <br/>__NOTOC__In Pierre Marquis, Magdalena Ortiz, Maurice Pagnucco, eds., <i>Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning</i>, 574–584, 2024. IJCAI Organization<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3388|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:KR 2024 Characterization of Decidability for RPQs Under TGDs-iccl.pdf|Download]]KR 2024 Characterization of Decidability for RPQs Under TGDs-iccl.pdf|Download]] +
Piotr Ostropolski-Nalewaja, Sebastian Rudo … Piotr Ostropolski-Nalewaja, Sebastian Rudolph<br/> '''[[Inproceedings3388/en|<b>The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules</b>]]''' <br/>__NOTOC__In Pierre Marquis, Magdalena Ortiz, Maurice Pagnucco, eds., <i>Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning</i>, 574–584, 2024. IJCAI Organization<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3388|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:KR 2024 Characterization of Decidability for RPQs Under TGDs-iccl.pdf|Download]]KR 2024 Characterization of Decidability for RPQs Under TGDs-iccl.pdf|Download]] +
The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +
Display title of"Display title of" is a predefined property that can assign a distinct display title to an entity and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +
Modification date"Zuletzt geändert <span style="font-size:small;">(Modification date)</span>" is a predefined property that corresponds to the date of the last modification of a subject and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
13. November 2024, 16:24:11 +
Has query"Hat Abfrage <span style="font-size:small;">(Has query)</span>" is a predefined property that represents meta information (in form of a <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">subobject</a>) about individual queries and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +, The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +, The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +, The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +, The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules + and The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules +
