研究带约束的规则下路径查询的复杂度，发现其数据复杂度与普通图数据库相同。
Answering Path Queries under Linear and Guarded Existential Rules
- 将线性存在规则下的路径查询归约到简单情形，简化计算逻辑
- 数据复杂度为PTime，联合复杂度在有界谓词数时为ExpTime
- 适用于知识库中路径查询的高效推理，适合逻辑与数据库研究者
本研究关注基于知识库（包含数据实例和本体）的语义查询回答问题。尽管多数工作聚焦于合取查询（CQs），导航查询日益受到重视。本文探讨了在由守卫存在规则定义的本体上，对双向（合取）正则路径查询（(C)RPQs）的复杂度问题。首先分析线性存在规则情形，证明(C)RPQ回答在数据复杂度下为NL-complete，与无本体的纯图数据库中RPQ回答的复杂度一致。在联合复杂度下，两者均为ExpTime-complete；若限定谓词的阶数上限，则分别降至PTime-complete和PSpace-complete。对于守卫规则，我们给出非平凡归约至线性情形的方法，从而得出：(C)RPQ回答的联合复杂度为2ExpTime-complete（有界阶数时为ExpTime-complete），数据复杂度为PTime-complete，与合取查询复杂度一致。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。