A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL

• URL: http://arxiv.org/abs/2608.04945v1
• Date: Wed, 05 Aug 2026 15:12:01 GMT
• Title: A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL
• Abstract summary: We introduce DL automata, a novel formalism that captures the semantics of first-order rewritable queries.<n>We identify a large class of DL automata that can be rewritten into unions of conjunctive two-way regular path queries.<n>This yields a broad class of Horn-AL OMCHIQs that are GQL-rewritable.
• Score: 6.033257307910245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The emergence of the ISO standard GQL introduces a powerful query language extending first-order logic with controlled recursion, raising the question of its applicability to evaluation of ontology-mediated queries (OMQs). We focus on OMQs consisting of atomic queries over ontologies expressed in Horn-ALCHI, an expressive Description Logic that is not, in general, first-order rewritable. To address this, we introduce DL automata, a novel formalism that captures the semantics of such OMQs via runs over fact sets. We then identify a large class of DL automata that can be rewritten into unions of conjunctive two-way regular path queries (UC2RPQs), a central fragment of GQL. Our class of automata relies on a stratification of their states, ruling out specific forms of cyclic dependencies known to raise the complexity. This yields a broad class of Horn-ALCHI OMQs that are GQL-rewritable.

Related papers

• A Horn extension of DL-Lite with NL data complexity [1.376408511310322]
  We introduce a description logic that strictly extends the core DL-Lite, supports reachability restricted conjunction, and allows for reasoning in NL.<n>We establish the NL via a rewriting into two-way regular path queries, providing initial evidence that our language is a promising candidate for extending OMQA to graph query languages.
  arXiv  Detail & Related papers  (2026-05-13T11:26:32Z)
• Graph Query Generation with Constraint-guided Large Language Agents [9.418317695662516]
  UniQGen is a constraint-based framework that extracts and refines representative graph query clauses.<n>We demonstrate that UniQGen outperforms state-of-the-art graph query generation techniques in both accuracy and efficiency.<n>We release Cypher outputs and a Neptune-ready Freebase snapshot to support cross-language KGQA research.
  arXiv  Detail & Related papers  (2026-04-09T21:50:47Z)
• KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering [64.62317305868264]
  We present textbfKBQA-R1, a framework that shifts the paradigm from text imitation to interaction optimization via Reinforcement Learning.<n>Treating KBQA as a multi-turn decision process, our model learns to navigate the knowledge base using a list of actions.<n>Experiments on WebQSP, GrailQA, and GraphQuestions demonstrate that KBQA-R1 achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-12-10T17:45:42Z)
• FIRESPARQL: A LLM-based Framework for SPARQL Query Generation over Scholarly Knowledge Graphs [0.5120567378386615]
  We propose a modular framework that supports fine-tuned LLMs as a core component, with optional context provided via RAG and a SPARQL query correction layer.<n>We measure query accuracy using BLEU and ROUGE metrics, and query result accuracy using relaxed exact match(RelaxedEM)<n> Experimental results demonstrate that fine-tuning achieves the highest overall performance, reaching 0.90 ROUGE-L for query accuracy and 0.85 RelaxedEM for result accuracy on the test set.
  arXiv  Detail & Related papers  (2025-08-14T09:08:50Z)
• 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)
• Respecting Temporal-Causal Consistency: Entity-Event Knowledge Graphs for Retrieval-Augmented Generation [69.45495166424642]
  We develop a robust and discriminative QA benchmark to measure temporal, causal, and character consistency understanding in narrative documents.<n>We then introduce Entity-Event RAG (E2RAG), a dual-graph framework that keeps separate entity and event subgraphs linked by a bipartite mapping.<n>Across ChronoQA, our approach outperforms state-of-the-art unstructured and KG-based RAG baselines, with notable gains on causal and character consistency queries.
  arXiv  Detail & Related papers  (2025-06-06T10:07:21Z)
• Neuro-Symbolic Query Compiler [57.78201019000895]
  This paper presents QCompiler, a neuro-symbolic framework inspired by linguistic grammar rules and compiler design, to bridge this gap.<n>It theoretically designs a minimal yet sufficient Backus-Naur Form (BNF) grammar $G[q]$ to formalize complex queries.<n>The atomicity of the sub-queries in the leaf ensures more precise document retrieval and response generation, significantly improving the RAG system's ability to address complex queries.
  arXiv  Detail & Related papers  (2025-05-17T09:36:03Z)
• Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
  Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. Recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. We propose an effective Query Instruction Parsing (QIPP) that captures latent query patterns from code-like query instructions.
  arXiv  Detail & Related papers  (2024-10-27T03:18:52Z)
• An In-Context Schema Understanding Method for Knowledge Base Question Answering [70.87993081445127]
  Large Language Models (LLMs) have shown strong capabilities in language understanding and can be used to solve this task. Existing methods bypass this challenge by initially employing LLMs to generate drafts of logic forms without schema-specific details. We propose a simple In-Context Understanding (ICSU) method that enables LLMs to directly understand schemas by leveraging in-context learning.
  arXiv  Detail & Related papers  (2023-10-22T04:19:17Z)
• Allies: Prompting Large Language Model with Beam Search [107.38790111856761]
  In this work, we propose a novel method called ALLIES. Given an input query, ALLIES leverages LLMs to iteratively generate new queries related to the original query. By iteratively refining and expanding the scope of the original query, ALLIES captures and utilizes hidden knowledge that may not be directly through retrieval.
  arXiv  Detail & Related papers  (2023-05-24T06:16:44Z)
• 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)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  We study the evaluation of ontology-mediated queries over relational databases. We provide a characterization of the classes of OMQs that are tractable in combined complexity. We also study the complexity of deciding whether a given OMQ is equivalent to an OMQ of bounded tree width.
  arXiv  Detail & Related papers  (2020-03-17T16:32:00Z)

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.