Julien Corman, Juan L. Reutter and Ognjen Savkovic.
Abstract: One of the most promising schema languages for RDF is SHACL, a recent W3C recommendation.
However, the original semantics of SHACL is undefined in the presence of recursive constraints.
This omission is important because SHACL by design favors constraints that reference other ones, which in practice may easily yield reference cycles.
We showed that extending the existing semantics to accommodate the recursion leads to intractability in the size of the graph for the so-called "core constraint components" of SHACL.
In fact, we show intractability already for stratified constraints, which may come as a surprise, considering that stratification guarantees tractability in well studied languages such as Datalog.
In our previous work we propose a syntactic fragment of SHACL that guarantees tractability.
In this paper instead we retain all SHACL operators, and strengthen the stratification condition.
In particular, we introduce a syntactic condition of shape constraints called "strict stratification", that guarantees that graph validation is in PTIME.
We also introduce an algorithm which runs in PTIME and decides graph validation over a set of shapes satisfying this requirement.
Keywords: SHACL; formal semantics; computational complexity; graph constraint language