从样例中学习形状：递归 SHACL 中形状学习的基础
文章背景与核心概要
本文研究了数据图验证形状（Shapes）的自动化学习，特别是聚焦于递归 SHACL（Shapes Constraint Language，形状约束语言）。作者探讨了“拟合方法”（fitting approach），即从输入图中的正例节点集（\(P\)）和负例节点集（\(N\)）出发，计算出形状表达式 \(C\)。
研究聚焦于对应于描述逻辑 \(\mathcal{ELI}\) 的 SHACL 核心片段（在递归形状目录中采用良基、稳定和支撑语义）。该研究针对拟合存在性以及最具体拟合计算问题，确立了严格的指数时间上界，并在特定相关情形下获得了多项式时间上界，为知识图谱应用中的自动化形状推理奠定了理论基础。
摘要 (Abstract)
SHACL 形状能够实现数据图验证，这使得自动形状学习对于知识图谱应用至关重要。我们研究了针对该任务的著名拟合方法：给定输入图中的正例和负例节点集 \(P\) 和 \(N\)，计算形状表达式 \(C\)（可能使用递归形状目录中定义的形状名称），使得 \(C\) 能够验证 \(P\) 中的所有节点，而不验证 \(N\) 中的任何节点。我们重点关注 \(C\) 编写在对应于描述逻辑 \(\mathcal{ELI}\) 的 SHACL 核心片段中的情况。对于形状目录，我们考虑了良基、稳定和支撑语义。我们探讨了拟合存在性和最具体拟合计算，为这两个问题确立了严格的指数时间上界，并在相关的特殊情况下获得了多项式上界。
SHACL shapes enable data graph validation, making automatic shape learning essential for knowledge graph applications. We investigate the well-known fitting approach to this task: given sets \(P\) and \(N\) of positive and negative example nodes from an input graph, compute a shape expression \(C\), possibly using shape names defined in a recursive shape catalogue, that validates at every node in \(P\) and none in \(N\). We focus on the case where \(C\) is written in a core fragment of SHACL corresponding to the Description Logic \(\mathcal{ELI}\). For the catalogue, we consider the well-founded, stable, and supported semantics. We address fitting existence and most specific fitting computation, establish tight exponential-time upper bounds for both problems, and obtain polynomial bounds for relevant special cases.
访问与资源 (Access & Resources)
全文链接： * 查看 PDF * HTML（实验性） * TeX 源码 * 许可证： 知识共享署名 4.0
* 外部引用： * Google Scholar * Semantic Scholar * NASA ADS
Full-Text Links: * View PDF * HTML (experimental) * TeX Source * License: Creative Commons Attribution 4.0