A Horn extension of DL-Lite with NL data complexity

• URL: http://arxiv.org/abs/2605.13367v1
• Date: Wed, 13 May 2026 11:26:32 GMT
• Title: A Horn extension of DL-Lite with NL data complexity
• Abstract summary: 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.
• Score: 1.376408511310322
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The literature on ontology-mediated query answering (OMQA) has been shaped by two key results: first-order rewritability for DL-Lite, and PTime-hardness of data complexity for essentially every description logic beyond it. This has effectively positioned DL-Lite as the only practical choice for query rewriting, restricting OMQA solutions to first-order queries and ontologies that can be rewritten into them. This AC0 vs. PTime dichotomy is especially limiting if we consider that OMQA targets graph-structured data, and that standard graph query languages (including the recent ISO standards GQL and SQL/PGQ) are typically NL-complete. Towards identifying a rich Horn DL that can be rewritten into graph query languages and that can still express many ELI and DL-Lite ontologies, we introduce a stratification mechanism for ELI that controls the interaction between conjunction and recursion. In this way, we obtain ELbotpreceq, a description logic that strictly extends the core DL-Lite, supports reachability axioms and restricted conjunction, and allows for reasoning in NL. We establish the NL upper bound via a rewriting into nested two-way regular path queries, a fragment of GQL, providing initial evidence that our ontology language is a promising candidate for extending OMQA to graph query languages.

Related papers

• Natural Language Knowledge Graph Query Execution: Leveraging Controlled Semantics in the LLM Context Window [0.0]
  We show that for database queries, data model concepts pass to LLMs more effectively through representations whose vocabulary terms carry declared, machine-readable semantics.<n> NLKGQ is a working system and reusable framework that does this for data modeled in a knowledge graph.<n>We evaluate on the DBLP-QuAD 2.0 benchmark (57.6% Match under deterministic re-scoring), DBLP-QuAD 3.1 (89.9% Match on 1,000 questions), SemOpenAlex (98% Match against a published baseline's 86% on the identical test set)
  arXiv  Detail & Related papers  (2026-09-13T16:36:40Z)
• A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL [6.033257307910245]
  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.
  arXiv  Detail & Related papers  (2026-08-05T15:12:01Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• 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)
• 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)
• Improving Text-to-SQL Semantic Parsing with Fine-grained Query Understanding [84.04706075621013]
  We present a general-purpose, modular neural semantic parsing framework based on token-level fine-grained query understanding. Our framework consists of three modules: named entity recognizer (NER), neural entity linker (NEL) and neural entity linker (NSP)
  arXiv  Detail & Related papers  (2022-09-28T21:00:30Z)
• Expressivity of Planning with Horn Description Logic Ontologies (Technical Report) [12.448670165713652]
  We address open-world state constraints formalized by planning over a description logic (DL) ontology. We propose a novel compilation scheme into standard PDDL with derived predicates. We show that our approach can outperform previous work on existing benchmarks for planning with DL.
  arXiv  Detail & Related papers  (2022-03-17T14:50:06Z)
• Counting Query Answers over a DL-Lite Knowledge Base (extended version) [14.504450881786214]
  We study the data complexity of query answering over a Knowledge Base (KB) We improve upon existing results by providing a PTIME and coNP lower bounds, and upper bounds in PTIME and LOGSPACE.
  arXiv  Detail & Related papers  (2020-05-12T16:01:09Z)
• 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.