在线性和守卫存在规则下回答路径查询

# 在线性和保护存在规则下回答路径查询 来源：https://arxiv.org/html/2607.22636 \\JAIRAE Roberta Calegari\\JAIRTrack Jean\-François Baget,Meghyn Bienvenu0000\-0001\-6229\-8103 (https://orcid.org/0000-0001-6229-8103)meghyn\.bienvenu@labri\.fr (https://arxiv.org/html/2607.22636v1/mailto:[email protected])波尔多大学, CNRS, 波尔多国立理工学院, LaBRITalence法国,Marie\-Laure Mugnier0000\-0002\-0574\-3693 (https://orcid.org/%200000-0002-0574-3693)mugnier@lirmm\.fr (https://arxiv.org/html/2607.22636v1/mailto:[email protected])LIRMM, Inria, 蒙彼利埃大学, CNRS蒙彼利埃法国andMichaël Thomazo0000\-0002\-1437\-6389 (https://orcid.org/0000-0002-1437-6389)michael\.thomazo@inria\.fr (https://arxiv.org/html/2607.22636v1/mailto:[email protected])Inria, DIENS, 巴黎高等师范学院, PSL大学, CNRS巴黎法国 \(2026\) ###### 摘要\. 本体介导的查询回答关注的是在由数据库实例和本体构成的知识库上回答查询的问题。虽然该领域的大多数工作集中于合取查询（CQs），但导航查询已获得越来越多的关注。在本文中，我们研究了在由一组保护存在规则构成的本体的知识库上回答双向（合取）正则路径查询（(C)RPQs）的复杂性。我们首先考虑线性存在规则子类，并表明 (C)RPQ 回答在数据复杂性上是 NL-完全的，这与在普通图数据库（即没有本体）上回答 RPQ 的数据复杂性相匹配。在组合复杂性上，两种任务在一般情况下都是 ExpTime-完全的，但如果谓词元数有界，则 RPQ 和 CRPQ 回答分别降至 PTime-完全和 PSpace-完全。对于保护规则，我们提供了一个非平凡的归约到线性情况，这使我们能够证明 (C)RPQ 回答的复杂性与 CQs 相同，即在组合复杂性上是 2ExpTime-完全的（有界元数情况下是 ExpTime-完全的），而在数据复杂性上是 PTime-完全的。††copyright:cc††journalyear:2026††doi:10\.1613/jair\.1\.xxxxx††journalvolume:4††article:111††publicationmonth:8††journalyear:2026## 1\.引言 在过去的二十年中，大量的研究工作致力于*本体介导的查询回答* \(OMQA\)，其中数据通过表达领域知识的本体得到丰富，查询通过同时考虑数据和本体来回答（参见例如\(Poggi et al\.,2008 (https://arxiv.org/html/2607.22636#bib.bib54)\)的早期开创性工作和\(Xiao et al\.,2018 (https://arxiv.org/html/2607.22636#bib.bib58)\)的简短综述）。在数据之上添加本体层允许用户以更熟悉的方式、更接近其对应用领域概念化的方式来表达查询，从而抽象出数据库的实际结构（这些结构可能是为独立目的而设计的）。另一方面，它也可以提供更完整的查询答案，因为答案不仅基于数据中显式存储的事实，还基于本体和数据的推论。最后，在数据集成背景下，它提供了一个统一的中间层，有助于集成异构数据源。因此，OMQA 方法提供了几个重要优势，这些优势在不同应用领域都具有相关性（我们推荐读者参阅\(Xiao et al\.,2019 (https://arxiv.org/html/2607.22636#bib.bib59)\)以了解 OMQA 应用的概况）。然而，在计算查询答案时需要考虑本体信息，这可能会使查询回答任务显著复杂化，具体取决于本体和查询语言的表达能力。OMQA 中主要考虑两类本体语言，即描述逻辑（DLs）和存在规则（参见例如综述章节\(Ortiz and Simkus,2012 (https://arxiv.org/html/2607.22636#bib.bib52);Kontchakov et al\.,2013 (https://arxiv.org/html/2607.22636#bib.bib44);Bienvenu and Ortiz,2015 (https://arxiv.org/html/2607.22636#bib.bib12)\)关于 DLs 的 OMQA 和\(Calì et al\.,2009a (https://arxiv.org/html/2607.22636#bib.bib17);Mugnier and Thomazo,2014 (https://arxiv.org/html/2607.22636#bib.bib50)\)关于存在规则的内容）。这些本体语言允许在开放领域中进行推理，这意味着现有实体不应限于数据中显式编码的那些。存在规则，也称为元组生成依赖\(Abiteboul et al\.,1994 (https://arxiv.org/html/2607.22636#bib.bib2)\)，可以看作是 Datalog（等价于无函数 Horn 规则）的扩展，在规则头部引入存在量化的变量。例如，以下存在规则表达“每个人都有一个人作为父母”：∀x\.human\(x\)→∃y\.hasParent\(x,y\)∧human\(y\)\\forall x\.~human\(x\)\\rightarrow\\exists y\.~hasParent\(x,y\)\\land human\(y\)。应用到像 human\(a\)human\(a\) 这样的事实，该规则会导致推断出无限多个实体的存在。存在规则泛化了大多数在数据访问上下文中使用的 DLs，通常称为 Horn 描述逻辑。更广泛地说，它们通过无限制的谓词元数和表达原子之间非树形关系的能力，克服了 DLs 的一些已知局限性。这种增加的表达能力使得基本事实蕴涵变得不可判定（例如\(Beeri and Vardi,1981 (https://arxiv.org/html/2607.22636#bib.bib9)\)），然而已经发现许多可判定的存在规则类，它们在表达能力和推理复杂性之间提供了不同的权衡。我们这里关注两个核心类\(Calì et al\.,2009b (https://arxiv.org/html/2607.22636#bib.bib18),2013 (https://arxiv.org/html/2607.22636#bib.bib16)\)：*保护*存在规则，其中规则体有一个保护子，即包含规则体中所有变量的原子，以及*线性*存在规则，保护规则的一个子类，其中规则体仅包含一个原子，如上述示例规则。至于查询语言，OMQA 的大多数工作都集中在*合取查询* \(CQs\) 上，这是关系数据库和语义网中的一个基础查询类，在该类中也称为基本图模式查询。然而，图数据库的日益普及和知识图谱的兴起将注意力转向了导航查询\(Angles et al\.,2017 (https://arxiv.org/html/2607.22636#bib.bib3);Libkin et al\.,2025 (https://arxiv.org/html/2607.22636#bib.bib46)\)，它们能够捕获无界大小的结构模式。最简单的此类查询是*正则路径查询* \(RPQs\)\(Cruz et al\.,1987 (https://arxiv.org/html/2607.22636#bib.bib27);Mendelzon and Wood,1995 (https://arxiv.org/html/2607.22636#bib.bib49);Calvanese et al\.,2002 (https://arxiv.org/html/2607.22636#bib.bib25)\)，它询问标签符合给定正则语言的潜在任意长度的路径，从而允许在二元谓词上的一种受控递归形式。已经研究了许多 RPQ 的扩展，包括*合取正则路径查询* \(CRPQs\)\(Florescu et al\.,1998 (https://arxiv.org/html/2607.22636#bib.bib35);Calvanese et al\.,2000 (https://arxiv.org/html/2607.22636#bib.bib24);Cucumides et al\.,2023 (https://arxiv.org/html/2607.22636#bib.bib28)\)，它同时泛化了 RPQ 和 CQ。特别是，SPARQL 1\.1 的核心查询（W3C 标准111SPARQL 1\.1 查询语言 W3C 推荐标准：http://www.w3.org/TR/sparql11-query用于查询 RDF 数据）大致对应于 CRPQs。下一个示例说明了这些不同类型的查询在存在规则的本体介导查询回答背景下的应用。它将作为本文的贯穿示例，提供关键概念的高级概述。额外的专门示例将说明技术构造背后的细节和微妙之处。 ###### 示例 1 \(贯穿示例\)。考虑描述社交网络中关系的数据，使用谓词follows\\mathsf\{follows\}\(xx,yy\)、isFriendOf\\mathsf\{isFriendOf\}\(xx,yy\) 和 message\\mathsf\{message\}\(m,x,ym,x,y\)，意味着消息 mm 从 xx 发送到 yy。询问所有对 \(x,y\)\(x,y\) 使得 xx 和 yy 都关注某个人，可以表示为 CQ: q1\(x,y\)=∃z\.follows\(x,z\)∧follows\(y,z\)q\_\{1\}\(x,y\)=\\exists z\.~\\mathsf\{follows\}\(x,z\)\\land\\mathsf\{follows\}\(y,z\)它也可以表示为 RPQ: q2\(x,y\)=follows⋅follows−\(x,y\)q\_\{2\}\(x,y\)=\\mathsf\{follows\\cdot follows^\{\-\}\}\(x,y\)其中运算符 \- 表示逆关系。询问对 \(x,y\)\(x,y\) 使得 yy 是 xx 的直接或间接追随者，可以通过 RPQ 表示但不能通过 CQ 表示： q3\(x,y\)=follows−⋅\(follows−\)∗\(x,y\)q\_\{3\}\(x,y\)=\\mathsf\{follows\}^\{\-\}\\cdot\(\\mathsf\{follows\}^\{\-\}\)^\{\*\}\(x,y\)反过来，询问对 \(x,y\)\(x,y\) 使得 xx 和 yy 互相关注，可以通过 CQ 表示但不能通过 RPQ 表示： q4\(x,y\)=follows\(x,y\)∧follows\(y,x\)q\_\{4\}\(x,y\)=\\mathsf\{follows\}\(x,y\)\\land\\mathsf\{follows\}\(y,x\)现在，检索对 \(x,y\)\(x,y\) 使得 xx 关注 yy 且 yy 直接或间接关注 xx 需要 CRPQ 的表达能力，它通过用路径表达式替换标准谓词来泛化 q4q\_\{4\}： q5\(x,y\)=follows\(x,y\)∧follows⋅follows∗\(y,x\)q\_\{5\}\(x,y\)=\\mathsf\{follows\}\(x,y\)\\land\\mathsf\{follows\\cdot follows\}^\{\*\}\(y,x\)询问用户 Alice\\mathsf\{Alice\} 是否从她直接或间接关注的人那里收到了消息，可以通过一个（布尔）CRPQ 表示： q6\(\)=∃y,m\.follows⋅follows∗\(Alice,y\)∧message\(m,y,Alice\)q\_\{6\}\(\)=\\exists y,m\.~\\mathsf\{follows\\cdot follows\}^\{\*\}\(Alice,y\)\\land message\(m,y,Alice\)现在，让我们添加本体知识，说明 (1) 关系 isFriendOf\\mathsf\{isFriendOf\} 是对称的，(2) 它是关系 follows\\mathsf\{follows\} 的特例，(3) 关注某人意味着向该人发送消息。这可以使用以下三个线性规则来表达： > \(ρ1\)\(\\rho\_\{1\}\)∀x,y\.isFriendOf\(x,y\)→isFriendOf\(y,x\)\\forall x,y\.~\\mathsf\{isFriendOf\}\(x,y\)\\rightarrow\\mathsf\{isFriendOf\}\(y,x\) \(ρ2\)\(\\rho\_\{2\}\)∀x,y\.isFriendOf\(x,y\)→follows\(x,y\)\\forall x,y\.~\\mathsf\{isFriendOf\}\(x,y\)\\rightarrow\\mathsf\{follows\}\(x,y\) \(ρ3\)\(\\rho\_\{3\}\)∀x,y\.follows\(x,y\)→∃m\.message\(m,x,y\)\\forall x,y\.~\\mathsf\{follows\}\(x,y\)\\rightarrow\\exists m\.~\\mathsf\{message\}\(m,x,y\) 假设数据表明 Bob\\mathsf\{Bob\} 关注 Alice\\mathsf\{Alice\}，并且他们有一个共同的朋友 Carmen\\mathsf\{Carmen\}，这由事实 follows\(Bob,Alice\)、isFriendOf\(Carmen,Alice\)\\mathsf\{follows\(Bob,Alice\)\},\\mathsf\{isFriendOf\(Carmen,Alice\)\} 和 isFriendOf\(Carmen,Bob\)\\mathsf\{isFriendOf\(Carmen,Bob\)\} 表示。在这个数据上，前面的查询都没有答案，而当考虑规则时，所有查询都有答案。事实上，以下事实是从数据和规则推断出来的： > isFriendOf\(Alice,Carmen\)、isFriendOf\(Bob,Carmen\)\\mathsf\{isFriendOf\(Alice,Carmen\)\},\\mathsf\{isFriendOf\(Bob,Carmen\)\} follows\(Carmen,Alice\)、follows\(Carmen,Bob\)、follows\(Alice,Carmen\)、follows\(Bob,Carmen\)\\mathsf\{follows\(Carmen,Alice\)\},\\mathsf\{follows\(Carmen,Bob\)\},\\mathsf\{follows\(Alice,Carmen\)\},\\mathsf\{follows\(Bob,Carmen\)\} message\(m0,Bob,Alice\)、message\(m1,Carmen,Alice\)、message\(m2,Carmen,Bob\)、\\mathsf\{message\(m\_\{0\},Bob,Alice\)\},\\mathsf\{message\(m\_\{1\},Carmen,Alice\)\},\\mathsf\{message\(m\_\{2\},Carmen,Bob\)\}, message\(m3,Alice,Carmen\)、message\(m4,Bob,Carmen\)\\mathsf\{message\(m\_\{3\},Alice,Carmen\)\},\\mathsf\{message\(m\_\{4\},Bob,Carmen\)\} 例如，事实 follows\(Alice,Carmen\)\\mathsf\{follows\(Alice,Carmen\)\} 和 follows\(Carmen,Bob\)\\mathsf\{follows\(Carmen,Bob\)\} 对 q3q\_\{3\} 产生了答案 \(Bob,Alice\)\\mathsf\{\(Bob,Alice\)\}；从这两个事实和 message\(m0,Bob,Alice\)\\mathsf\{message\(m\_\{0\},Bob,Alice\)\}，我们得出结论 q6q\_\{6\} 被肯定回答。作为保护规则的一个例子，考虑定义谓词 isPaired\\mathsf\{isPaired\} 的规则： > \(ρ4\)\(\\rho\_\{4\}\)∀x,y\.follows\(x,y\)∧follows\(y,x\)→isPaired\(x,y\)\\forall x,y\.~\\mathsf\{follows\}\(x,y\)\\land\\mathsf\{follows\}\(y,x\)\\rightarrow\\mathsf\{isPaired\}\(x,y\) 最后，下面的规则定义了谓词 extFollows\\mathsf\{extFollows\}，它捕获正则表达式 follows\.follows∗\\mathsf\{follows\.follows\}^\{\*\}： > ∀x,y\.follows\(x,y\)→extFollows\(x,y\)\\forall x,y\.~\\mathsf\{follows\}\(x,y\)\\rightarrow\\mathsf\{extFollows\}\(x,y\) ∀x,y,z\.follows\(x,y\)∧extFollows\(y,z\)→extFollows\(x,z\)\\forall x,y,z\.~\\mathsf\{follows\}\(x,y\)\\land\\mathsf\{extFollows\}\(y,z\)\\rightarrow\\mathsf\{extFollows\}\(x,z\) 使用谓词 extFollows\\mathsf\{extFollows\}，上述 (C)RPQs 可以重新表述为 CQs。然而请注意，最后一条规则不是保护的，因此不属于本文研究的