在本研究中，我们探讨了基于知识库的路径查询问题，特别是受限存在规则的情况。尽管大多数相关研究集中在结合查询（CQs）上，导航查询的关注度逐渐增加。我们主要研究了在给定受限存在规则的本体下，如何回答双向（结合）正则路径查询（(C)RPQs）。
首先，我们考虑线性存在规则的子类，并证明在数据复杂性方面，(C)RPQ 的回答是 NL-完全的，这与在没有本体的普通图数据库上回答 RPQs 的数据复杂性相匹配。在组合复杂性方面，尽管一般情况是 ExpTime-完全的，但如果对谓词的元数有界，RPQ 和 CRPQ 的回答分别降为 PTime-完全和 PSpace-完全。
对于受限规则，我们提供了一个非平凡的归约到线性情况，这使我们能够展示 (C)RPQ 的回答复杂性与 CQs 相同，即在组合复杂性中是 2ExpTime-完全（在有界元数的情况下为 ExpTime-完全），而在数据复杂性中为 PTime-完全。
博主点评： 本文提供了对路径查询复杂性的新视角，尤其是在处理受限存在规则时的深刻分析，具有重要的理论价值与实际应用潜力。