论文标题
SHACL的满足和遏制（扩展纸）
SHACL Satisfiability and Containment (Extended Paper)
论文作者
论文摘要
形状约束语言（SHACL）是用于验证RDF数据的最新W3C建议语言。具体而言，SHACL文档是在RDF图上执行特定形状的约束的集合。该主题的先前工作为验证问题提供了理论和实际结果，但没有考虑到可满足和遏制的标准决策问题，这对于验证约束的可行性至关重要，对于设计和优化目的而言很重要。在本文中，我们通过提供一种称为新的一阶语言的名为SCL的新一阶语言，对非恢复SHACL的不同特征进行了详尽的研究，该语言精确地捕获了Shacl W.R.T.的语义。令人满意和遏制。我们研究了SHACL特征在此逻辑中的相互作用，并为不同的SHACL Sublanguages提供了上述决策问题的详细映射和复杂性结果。值得注意的是，我们证明这两个问题对于完整语言都是不可决定的，但是我们提出了有趣的功能的可决定组合。
The Shapes Constraint Language (SHACL) is a recent W3C recommendation language for validating RDF data. Specifically, SHACL documents are collections of constraints that enforce particular shapes on an RDF graph. Previous work on the topic has provided theoretical and practical results for the validation problem, but did not consider the standard decision problems of satisfiability and containment, which are crucial for verifying the feasibility of the constraints and important for design and optimization purposes. In this paper, we undertake a thorough study of different features of non-recursive SHACL by providing a translation to a new first-order language, called SCL, that precisely captures the semantics of SHACL w.r.t. satisfiability and containment. We study the interaction of SHACL features in this logic and provide the detailed map of decidability and complexity results of the aforementioned decision problems for different SHACL sublanguages. Notably, we prove that both problems are undecidable for the full language, but we present decidable combinations of interesting features.
