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

• URL: http://arxiv.org/abs/2407.14384v1
• Date: Fri, 19 Jul 2024 15:11:09 GMT
• Title: The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules
• Authors: Piotr Ostropolski-Nalewaja, Sebastian Rudolph,
• Abstract summary: This paper considers the question for which of these fragments decidability of querying extends to regular path queries (RPQs) For the second major family of fragments, known as finite unification sets (short: fus), corresponding results have been largely elusive so far. 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.
• Score: 4.557963624437784
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Aggregation of Reasoning: A Hierarchical Framework for Enhancing Answer Selection in Large Language Models [84.15513004135576]
  Current research enhances the reasoning performance of Large Language Models (LLMs) by sampling multiple reasoning chains and ensembling based on the answer frequency. This approach fails in scenarios where the correct answers are in the minority. We introduce a hierarchical reasoning aggregation framework AoR, which selects answers based on the evaluation of reasoning chains.
  arXiv  Detail & Related papers  (2024-05-21T17:12:19Z)
• Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering [83.74210749046551]
  We propose to leverage question decomposing for heterogeneous knowledge integration. We propose a novel two-stage XQA framework, Reasoning over Hierarchical Question Decomposition Tree (RoHT) Experiments on complex QA datasets KQA Pro and Musique show that our framework outperforms SOTA methods significantly.
  arXiv  Detail & Related papers  (2023-05-24T11:45:59Z)
• Shortcomings of Question Answering Based Factuality Frameworks for Error Localization [51.01957350348377]
  We show that question answering (QA)-based factuality metrics fail to correctly identify error spans in generated summaries. Our analysis reveals a major reason for such poor localization: questions generated by the QG module often inherit errors from non-factual summaries which are then propagated further into downstream modules. Our experiments conclusively show that there exist fundamental issues with localization using the QA framework which cannot be fixed solely by stronger QA and QG models.
  arXiv  Detail & Related papers  (2022-10-13T05:23:38Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  This paper introduces a simple efficient learning algorithms for general sequential decision making. We prove that OMLE learns near-optimal policies of an enormously rich class of sequential decision making problems.
  arXiv  Detail & Related papers  (2022-09-29T17:56:25Z)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  We consider the query language, unions of conjunctive regular path queries (UCRPQs) We show a tight 2EXP bound for entailment of UCRPQs using the description logic ALC. There is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input automaton.
  arXiv  Detail & Related papers  (2022-04-29T17:38:13Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  We propose a query embedding method to answer complex logical queries on knowledge graphs with missing edges. The answer entities are selected according to the similarities between the entity embeddings and the query embedding. A complex KG query answering method, Q2P, is proposed to retrieve diverse answers from different areas over the embedding space.
  arXiv  Detail & Related papers  (2022-04-27T11:16:08Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Answering Fuzzy Queries over Fuzzy DL-Lite Ontologies [0.2741266294612776]
  We study the problem of answering conjunctive queries and threshold queries in fuzzy DL-Lite. For the idemdent G"odel t-norm, we provide an effective method based on a reduction to the classical case.
  arXiv  Detail & Related papers  (2021-11-23T10:45:54Z)
• First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics [22.32075802508239]
  We show that FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.
  arXiv  Detail & Related papers  (2020-11-19T14:24:02Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries. We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups) Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
  arXiv  Detail & Related papers  (2020-06-07T14:47:07Z)
• Containment of Simple Regular Path Queries [1.869065967043578]
  Testing containment of queries is a fundamental reasoning task in knowledge representation. We focus here on severely restricted fragments, which are known to be highly relevant in practice. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for np, pitwo, pspace or expspace.
  arXiv  Detail & Related papers  (2020-03-09T21:05:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.