Answering Path Queries under Linear and Guarded Existential Rules

• URL: http://arxiv.org/abs/2607.22636v1
• Date: Mon, 22 Jun 2026 09:34:08 GMT
• Title: Answering Path Queries under Linear and Guarded Existential Rules
• Abstract summary: We show that (C)RPQ answering is NL-complete in data complexity, which matches the data complexity of answering RPQs over plain graph databases.<n>For guarded rules, we provide a non-trivial reduction to the linear case, which allows us to show that the complexity of (C)RPQ answering is the same as for CQs.
• Score: 2.4779082385578337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ontology-mediated query answering is concerned with the problem of answering queries over knowledge bases consisting of a database instance and an ontology. While most work in the area focuses on conjunctive queries (CQs), navigational queries have gained increasing attention. In this paper, we investigate the complexity of answering two-way (conjunctive) regular path queries ((C)RPQs) over knowledge bases whose ontology is given by a set of guarded existential rules. We first consider the subclass of linear existential rules and show that (C)RPQ answering is NL-complete in data complexity, which matches the data complexity of answering RPQs over plain graph databases (i.e., without an ontology). In combined complexity, both tasks are ExpTime-complete in the general case, but RPQ and CRPQ answering drop to PTime-complete and PSpace-complete respectively if there is a bound on predicate arity. For guarded rules, we provide a non-trivial reduction to the linear case, which allows us to show that the complexity of (C)RPQ answering is the same as for CQs, namely 2ExpTime-complete in combined complexity (ExpTime-complete in the bounded-arity case) and PTime-complete in data complexity.

Related papers

• The benefits of query-based KGQA systems for complex and temporal questions in LLM era [55.20230501807337]
  Large language models excel in question-answering (QA) yet still struggle with multi-hop reasoning and temporal questions.<n> Query-based knowledge graph QA (KGQA) offers a modular alternative by generating executable queries instead of direct answers.<n>We explore multi-stage query-based framework for WikiData QA, proposing multi-stage approach that enhances performance on challenging multi-hop and temporal benchmarks.
  arXiv  Detail & Related papers  (2025-07-16T06:41:03Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  We propose an efficient and scalable symbolic search framework for complex queries.<n>Our framework reduces the computational load of symbolic methods by 90% while maintaining nearly the same performance.
  arXiv  Detail & Related papers  (2025-05-13T01:24:09Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  We argue that different logical operator types, rather than the different complex query types, are the key to improving generalizability. We propose a meta-learning algorithm to learn the meta-operators with limited data and adapt them to different instances of operators under various complex queries. Empirical results show that learning meta-operators is more effective than learning original CQA or meta-CQA models.
  arXiv  Detail & Related papers  (2024-03-15T08:54:25Z)
• Adapting Neural Link Predictors for Data-Efficient Complex Query Answering [45.961111441411084]
  We propose a parameter-efficient score emphadaptation model optimised to re-calibrate neural link prediction scores for the complex query answering task. CQD$mathcalA$ produces significantly more accurate results than current state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-01-29T00:17:16Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• 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)
• The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard [11.193504036335503]
  In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking. For knowledge bases in the basic description logic ALC, the computational complexity of conjunctive query (CQ) answering is well known to be ExpTime-complete. We show that even extending ALC by just the Self operator increases the complexity of CQ entailment to 2ExpTime.
  arXiv  Detail & Related papers  (2021-06-29T08:12:03Z)
• Answering Counting Queries over DL-Lite Ontologies [0.0]
  We introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries. We consider some practically relevant restrictions, for which we establish improved complexity bounds.
  arXiv  Detail & Related papers  (2020-09-02T11:10:21Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  We study privacy-preserving query answering in Description Logics (DLs) We derive data complexity results query answering over DL-Lite$_mathcal$$. We identify a semantically well-founded notion of approximated confidentiality answering for CQE.
  arXiv  Detail & Related papers  (2020-04-24T17:28:24Z)
• 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.