0


递归SHACL的语义与验证

Semantics and Validation of Recursive SHACL
课程网址: http://videolectures.net/iswc2018_savkovic_sematics_validation_sh...  
主讲教师: Ognjen Savkovic
开课单位: 博赞博尔扎诺自由大学
开课时间: 2018-11-22
课程语种: 英语
中文简介:
随着RDF作为一种独立数据模型的普及,需要在RDF图上指定约束,并需要检测违反这些约束的机制。最有前途的RDF模式语言之一是SHACL,这是W3C最近的一项建议。不幸的是,SHACL的规范留下了针对递归约束的验证问题。这一遗漏很重要,因为SHACL在设计上倾向于引用其他约束,这在实践中可能很容易产生参考循环。 在本文中,我们为SHACL的所谓“核心约束组件”提出了一种简洁的形式语义。该语义处理任意递归,同时符合当前标准。图形验证基于SHACL“形状”分配给被验证图形中的节点的存在,说明哪些形状被验证或违反,同时验证验证过程的目标。我们特别指出,SHACL的性质迫使我们考虑这些赋值是部分的情况,或者换句话说,在图的某些节点处约束的真值可能是未知的。 处理递归是要付出代价的,因为根据SHACL约束验证RDF图在图的大小上是NP困难的,并且这个下限对于使用分层否定的SHACL片段仍然有效。因此,我们还提出了验证问题的可处理近似。
课程简介: With the popularity of RDF as an independent data model came the need for specifying constraints on RDF graphs, and for mechanisms to detect violations of such constraints. One of the most promising schema languages for RDF is SHACL, a recent W3C recommendation. Unfortunately, the specification of SHACL leaves open the problem of validation against recursive constraints. This omission is important because SHACL by design favors constraints that reference other ones, which in practice may easily yield reference cycles. In this paper, we propose a concise formal semantics for the so-called "core constraint components" of SHACL. This semantics handles arbitrary recursion, while being compliant with the current standard. Graph validation is based on the existence of an assignment of SHACL "shapes" to nodes in the graph under validation, stating which shapes are verified or violated, while verifying the targets of the validation process. We show in particular that the nature of SHACL forces us to consider cases in which these assignments are partial, or, in other words, where the truth value of a constraints at some nodes of a graph may be left unknown. Dealing with recursion comes at a price, as validating an RDF graph against SHACL constraints is NP-hard in the size of the graph, and this lower bound still holds for a fragment of SHACL using stratified negation. Therefore we also propose a tractable approximation to the validation problem.
关 键 词: 独立数据模型的普及; RDF图上指定约束; RDF模式语言; 核心约束组件
课程来源: 视频讲座网
数据采集: 2023-01-14:cyh
最后编审: 2023-01-14:cyh
阅读次数: 41