提出可转为图查询语言的扩展型描述逻辑，突破传统DL-Lite限制。
A Horn extension of DL-Lite with NL data complexity
- 通过分层机制控制合取与递归交互，构建新描述逻辑ELbotpreceq
- 支持可达性公理和受限合取，推理复杂度为NL，优于原有PTime限制
- 适合需要图结构数据查询的领域，如知识图谱、数据库集成
在本体中介查询回答（OMQA）研究中，两个关键结果确立了地位：DL-Lite具有一阶可重写性，而几乎所有超越它的描述逻辑都达到数据复杂度的PTime难。这使DL-Lite成为唯一实际可行的选择，限制了查询仅限于一阶形式，且依赖可重写的本体。这一AC0与PTime的二分法尤其受限，因OMQA面向图结构数据，而标准图查询语言（如最新ISO标准GQL和SQL/PGQ）通常为NL完全。为寻找一个丰富且为霍恩型的描述逻辑，可被重写为图查询语言，并仍表达大量ELI与DL-Lite本体，我们引入一种对ELI的分层机制，以控制合取与递归间的交互。由此获得的描述逻辑ELbotpreceq，严格扩展了核心DL-Lite，支持可达性公理与受限合取，且推理可在NL完成。通过将其重写为嵌套的双向正则路径查询（一种GQL片段），我们建立了NL上界，初步表明该本体语言是将OMQA拓展至图查询语言的有力候选。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。