《Artificial Intelligence》:SHACL validation in the presence of ontologies: Semantics and rewriting techniques
SHACL 与 OWL 是用于管理 RDF 数据的两项重要万维网联盟(W3C)标准。这两种语言共享许多特性,但存在一个根本差异:OWL 旨在从不完整数据中推断事实,因此采用开放世界假设(Open-World Assumption, OWA);而 SHACL 是一种约束语言,将数据视为完备,并且必须在封闭世界假设(Closed-World Assumption, CWA)下进行验证。两种形式化体系的结合极具吸引力,且已被明确提出需求,但二者之间的语义鸿沟在语义层面与计算层面都构成了重大挑战。
本文主张一种在本体存在条件下进行 SHACL 验证的语义,其基础是核心通用模型(core universal models)。研究人员给出了针对富表达且数据可处理的描述逻辑 Horn-ALCHIQ 的这类模型构造技术。此外,研究人员利用该模型的有限表示,发展出一种重写技术,将本体存在条件下的 SHACL 验证归约为标准验证。最后,研究人员研究了本体存在条件下 SHACL 验证的复杂性,并证明即使是非常简单的本体也会使该问题在组合复杂度上达到 ExpTime-完全,在数据复杂度上达到 PTime-完全。
这篇发表于《Artificial Intelligence》的论文聚焦于 RDF 数据管理中两个核心 W3C 标准——SHACL 与 OWL——之间长期存在而又极具现实意义的整合问题。研究背景在于:OWL 基于描述逻辑(Description Logics, DLs),遵循开放世界假设(OWA),擅长在不完备图数据上进行知识蕴含;而 SHACL 作为约束验证语言,则建立在封闭世界假设(CWA)之上,要求把输入数据图视为完整对象进行一致性检查。二者虽然都服务于语义网数据治理,但其语义基础根本不同,因此“在本体知识存在时如何进行 SHACL 验证”并不能直接沿用现有 OWL 推理语义,也不能简单照搬普通 SHACL 验证机制。特别是在 SHACL 含有否定、析取、路径等构造时,若直接采用对所有模型都成立的 certain answer 语义,往往会产生违背直觉的非验证结果;而若采用传统 Skolem chase 或最小模型思路,又可能因为引入冗余匿名后继而改变约束满足性。因此,如何在保留本体蕴含能力的同时,给出符合 SHACL 约束直觉的验证语义,成为该研究开展的直接动因。
围绕这一问题,研究人员提出了一种基于“节制规范模型”(austere canonical model)的验证语义,并证明该模型实质上是知识库的唯一通用核心模型(universal core model)。这一模型的关键思想是在满足 Horn-ALCHIQ TBox 公理的前提下,局部最小化新增结构,尽可能避免无必要的匿名后继,从而兼顾通用性(universality)与非冗余性(core-like minimality)。论文首先定义了 good successor configuration,用于精确描述在某个节点局部环境下,为满足存在性公理而必须引入的最小后继模式;然后在此基础上构造 austere canonical model,并证明它与已有文献中的某种 Horn-SHIQ/Horn-ALCHIQ 模型构造一致,同时进一步证明该模型不仅是通用模型,而且是核心(core),并且在一致知识库上是唯一的通用强核心(strong core)模型。该结果为“为何应在该模型上进行 SHACL 验证”提供了坚实的数据库理论支撑,因为对于不满足同态封闭而仅满足同构封闭的语言,核心结构通常被视为最合适的语义代表。
研究人员使用的主要技术方法包括:其一,基于 Horn-ALCHIQ 的 TBox 规范化表示与局部蕴含分析,定义 good successor configuration,并据此构造 austere canonical model 及其有限近似;其二,借助核心(core)、同态(homomorphism)、强核心覆盖(strong core cover)等数据库理论工具,证明该模型的通用性与唯一核心性;其三,针对分层 SHACL(stratified SHACL)建立最小不动点(least fixed point)语义与正规形(normal form);其四,设计基于四元组
(t, P, Q, H) 的约束重写算法,将“在本体+规范模型上验证”转化为“在扩充 ABox 或纯数据图上验证”;其五,分析组合复杂度与数据复杂度,给出 ExpTime-完全与 PTime-完全结论。论文未涉及样本队列研究,属于形式化方法与理论计算机科学研究。
1. Introduction
引言部分系统阐明了 OWL 与 SHACL 结合的必要性及困难所在。研究人员指出,OWL 被设计为面向不完整 RDF 图的知识推理框架,允许从已有事实推出隐含事实;SHACL 则用于描述和验证数据约束,其核心任务是针对目标节点或目标类检查约束是否在给定图上成立。二者结合的自然诉求在于:若图数据不完整,但配有本体知识,验证时理应利用这些被蕴含出的事实。然而,SHACL 中否定、相等性、互斥性、closed 约束与计数约束等构造会使传统“所有模型上都成立”的语义过弱,也使基于 Skolem 化最小模型的方案产生反直觉结果。为解决这一问题,论文提出采用一种“节制”的规范模型,只在必要时最小化加入后继对象,并将其作为验证基准。引言还概括了全文贡献:提出语义、给出 Horn-ALCHIQ 下的模型构造、证明其为核心、定义分层递归 SHACL、建立重写技术,并完成复杂性刻画。
2. Preliminaries
预备知识部分建立了全文的形式化基础。研究人员定义了数据图(ABox)、解释(interpretation)、规范解释、同态、强同态、嵌入与同构等基本概念;给出了标准名假设下 Horn-ALCHIQ 的规范化 TBox 语法,包括概念包含公理、角色包含公理、全称限制、存在限制和至多 1 限制等;同时说明一致知识库可忽略包含 ⊥ 的公理。随后,论文定义了正则路径表达式(regular path expressions)及其在解释上的语义,并引入非递归 SHACL 的形状表达式语法和验证语义。这里的 SHACL 语义为后续扩展到递归 SHACL 奠定基础,尤其强调了否定、路径与计数等构造对模型选择的敏感性。
3. Validation with ontologies
本节提出在本体存在条件下进行 SHACL 验证的核心语义框架。研究人员首先通过反例说明:若仅要求目标在所有模型中都成立,则一旦 SHACL 含否定,就会导致本应通过的约束被判为不通过。接着,论文通过另一个例子表明,不同 chase 变体产生的不同通用模型,可能对带否定的 SHACL 产生不同验证结果,因此必须谨慎选择模型语义。为此,研究人员提出 austere canonical model。
3.1. Good successor configuration
这一小节定义了 good successor configuration,用以刻画某节点在给定局部环境下,为满足 TBox 公理而必须引入的最小新后继集合。其表示依赖 2-type、1?-type 与 1-type:2-type 编码一个节点与其相邻节点之间的概念和角色信息,1?-type 编码某个新后继与当前节点之间的角色集合及该后继的概念集合。规则(R1)到(R4)共同确保:若某些存在性需求尚未被当前环境满足,则必须引入相应后继;每个引入的后继都确有公理根据;不存在被其他后继包含的冗余后继;也不存在已被环境吸收的多余后继。研究人员进一步证明,在满足输入条件时,good successor configuration 对每个局部环境都存在且唯一。这一结果确保后续模型构造是确定性的。
3.2. Austere canonical model
在局部后继配置基础上,论文先定义 A
T,即在不使用存在性公理的前提下,对 ABox 施加其余 TBox 公理得到的最小闭包;随后定义 austere canonical model can(T, A)。该模型使用“词”来表示匿名部分中的节点:首字符是 ABox 个体,之后每一步追加一个 2-type,表示沿着匿名树逐步下行。模型中的概念与角色解释由 A
T 和尾部类型决定。研究人员证明,该模型存在且唯一,并且与既有文献中的 Horn-ALCHIQ/Horn-SHIQ 规范模型构造一致。更重要的是,can(T, A) 是知识库的模型且是通用模型,因此本文最终将“知识库验证 SHACL”的语义正式定义为:在 can(T, A) 上验证 SHACL 目标或形状图。
4. Finite and infinite cores
本节从数据库理论角度论证 austere canonical model 的核心性。研究人员先回顾 core 的定义:一个解释若其每个自同态(endomorphism)都是嵌入,则称为核心。随后引入 can
n(T, A) 作为 can(T, A) 的有限近似,并证明这些有限截断构成 core cover,进而推出 can(T, A) 是 core。进一步,论文证明每个一致的 Horn-ALCHIQ 知识库都存在唯一的通用核心模型,而这正是 can(T, A)。不仅如此,研究人员还证明该模型甚至是 strong core,即每个自同态都是同构。这一唯一性结论使得所提出语义不再只是“某个合理选择”,而是由通用性和核心性共同刻画出的规范选择。之后论文还讨论了 core chase,与传统需要反复做 core-checking 的 core chase 相比,austere canonical model 在有限情形下与其结果一致,但避免了昂贵的核心计算步骤,并且在无限情形下依然总是定义良好。
5. Recursive SHACL
本节将前述非递归 SHACL 扩展到允许递归的情形。研究人员引入形状名(shape names)与形状约束 s ← φ,并用形状赋值(shape assignment)定义递归 SHACL 的语义。考虑到文献中递归 SHACL 缺乏统一语义,论文选择了分层 SHACL(stratified SHACL)这一可处理片段,支持有限形式的否定,但限制否定与递归的相互作用。
5.1. Stratified SHACL
论文将约束集合分层,要求某层中出现的否定形状名不能在本层及更高层中定义,从而对应经典分层逻辑程序(stratified logic programs)。在此基础上,研究人员定义了立即后果算子 T
I,C,并证明在适当条件下该算子具备单调性、有限性与增长性,因此可以逐层采用最小不动点计算 perfect assignment。最终,带本体的递归 SHACL 验证被定义为:在 can(T, A) 上检查目标形状原子是否属于 perfect assignment。
5.2. Normal form
为服务后续重写,论文证明所研究的递归 SHACL 片段可以在多项式时间内转化为正规形,包括 s ← c、s ← s′、s ← A、s ← s′ ∧ s″、s ← ?(?R).s′ 与 s ← ?s′ 等形式。对于正则路径、eq、disj 等构造,研究人员使用自动机编码为新的形状约束集合,从而将复杂表达式系统地规约到有限几类基本规则。该正规形是后续重写算法可行性的关键前提。
6. Rewriting for positive SHACL
本节首先处理不含否定的正 SHACL 重写。研究人员的目标是:给定 TBox T 与约束集 C,构造新的约束集 C
T,使得对任意与 T 一致的 ABox A,(T, A) 在语义上验证 (C, G) 当且仅当 A
T 验证 (C
T, G)。为此,论文设计了基于四元组 (t, P, Q, H) 的饱和推理过程。其中,t 为局部 2-type,P 和 Q 分别表示正向假设与负向条件,H 表示在该局部环境下必然成立的形状名集合。规则体系通过模拟匿名部分中形状满足性的传播,逐步推导出所有可能的局部结论。随后,研究人员把每个四元组转换成对应的 SHACL 约束,加入重写后的约束集。论文通过完备性与正确性命题证明:在正 SHACL 情形下,该重写精确地把“规范模型上的验证”转化为了“闭包 ABox 上的标准验证”。
7. Rewriting for stratified SHACL
在上一节基础上,论文进一步扩展到带分层否定的递归 SHACL。核心做法是:按 strata 从低到高依次运行饱和过程,并在层与层之间引入 completion 操作,为尚未推出的形状补充显式负信息,例如 ?s、??r.s 或个体条件的否定版本。相应地,原有规则 6 被扩展为 6′,并新增处理 s ← ?s′ 的规则 7。通过逐层构造 K
0, K
1, …, K
n 并生成最终约束集 C
T,研究人员证明了对于任意分层 SHACL 约束集 C:知识库 (T, A) 验证 (C, G) 当且仅当 A
T 验证 (C
T, G)。这标志着本文的核心技术目标已经达成:复杂的“本体+无限规范模型+递归/否定约束”验证,能够系统归约为有限数据上的普通 SHACL 验证问题。
8. Pure rewritings
虽然前文已经把验证归约到 A
T 上,但 A
T 仍是 ABox 的本体闭包,不是原始数据图本身。因此本节讨论“纯重写”(pure rewriting):能否进一步构造约束集 C′,使 A 直接验证 C′ 就等价于原问题。
8.1. Rewriting for normalised Horn-ALCHI
对于不含 ≤1 计数限制的 Horn-ALCHI,论文给出纯 SHACL 重写方案。研究人员为每个概念名引入新的形状名 s
A,并构造约束集 T
s 来模拟 A
T 中概念闭包的推导;同时在 C
T 中把概念名替换为相应形状名,并通过角色包含处理必要的路径修正。最终证明:在该逻辑片段上,可以直接在原始 ABox A 上做标准 SHACL 验证。
8.2. SHACLb
针对一般 Horn-ALCHIQ,难点在于 A
T 中可能新增角色事实,而标准 SHACL 主要描述节点,无法直接给边打标签。为此,论文提出扩展语言 SHACL
b,允许定义二元形状约束 b ← ψ,以描述节点对之间的关系。借助 s
A 和 b
r 两类新形状名,研究人员构造 T
s 来完全模拟 A
T 中概念事实与角色事实的闭包推理,并把 C
T 中所有概念名与角色名替换为这些形状名。于是,原始知识库上的验证可被纯粹归约为 SHACL
b 在原始 ABox A 上的验证。这一部分展示了论文方法在工程实现方向上的进一步延展性。
9. Complexity results
复杂性部分给出了全文最明确的计算结论。研究人员证明:在规范化 Horn-ALCHIQ TBox 存在时,SHACL 验证的组合复杂度为 ExpTime-完全,数据复杂度为 PTime-完全。PTime 上界来自重写后在固定 TBox 和约束集下对 ABox 的多项式时间验证;ExpTime 上界来自重写过程中四元组数量的指数增长。下界一方面继承自 Horn-ALCHIQ 本体推理本身的 ExpTime 困难性;另一方面,论文还进一步证明,即使本体逻辑极弱、SHACL 也限制为 simple-SHACL,仅允许 s、A、合取和 ?r.φ 这样的简单构造,问题仍可达到 ExpTime-完全。研究人员通过把多项式空间有界交替图灵机(Alternating Turing Machines, ATM)的字问题规约为验证问题,建立了这一强化下界。该结果说明,复杂性的提升并非仅仅来源于复杂本体,而是 SHACL 与本体结合后在表达能力层面具有内在的高复杂度。
10. Discussion and conclusion
讨论部分首先指出,本文工作目前针对的是规范化 Horn-ALCHIQ,而无法直接扩展到任意 Horn-ALCHIQ,因为常规规范化过程会改变核心通用模型的结构,使原本可由同一对象满足的约束被迫拆分到不同对象上。对于含传递角色的 Horn-SHIQ,论文进一步指出通用核心模型甚至可能不唯一,这会动摇以单一核心模型作为验证语义基础的做法。就 SHACL 片段而言,作者也坦言,当前结果尚未覆盖完整路径相等/互斥、正则路径计数、无 guard 的全局等价比较以及完全自由的否定,这些都属于未来值得研究的难点。
研究结论部分可译为:本文研究了规范化 Horn-ALCHIQ 本体存在条件下的 SHACL 约束验证问题。为此,研究人员在一种精心构造的规范模型上定义了验证语义,该模型在每一步 chase 过程中以最小方式引入用于满足本体公理的新后继,并且恰好是唯一的核心通用模型。研究人员进一步论证了这一语义的自然性与直观性。论文提出了递归 SHACL(带分层否定)的正规形与重写算法,该算法以 SHACL 形状图和本体为输入,构造新的 SHACL 形状图,使得无需在验证时显式对本体推理,只需在数据图的轻度扩展版本上即可进行正确且完备的验证。研究人员还讨论了进一步归约到纯数据图验证的方法。最后,论文证明在所提出语义下,规范化 Horn-ALCHIQ 本体存在条件下的验证问题在组合复杂度上是 ExpTime-完全的,而在数据复杂度上仍是 PTime-完全,因此在数据复杂度意义下并不比不含本体公理的分层 SHACL 验证更困难。