Validating RDF graphs against constraints has gained interest in recent years, due to the popularity of RDF and the growth of knowledge bases. SHACL, a constraint language for RDF, has recently become a W3C recommendation, with a specification detailing syntax, semantics and common use cases. Unfortunately, this (otherwise complete) specification does not cover validation against recursive constraints. This omission is important, because SHACL by design favors constraint references. We investigate the possibility of a formal semantics for SHACL which covers the recursive case, while being compliant with the current standard.
Introduction Recent years have seen an increased interest in standardizing a declarative constraint language for RDF, and devising mechanisms to detect violations of such constraints. One of the most promising candidate languages is SHACL, or Shapes Constraint Language,3 which has become a W3C recommendation in 2017.
SHACL constraints are grouped in so-called “shapes” to be verified by certain nodes of the graph under validation, and such that a shape may reference another. Figure 1 presents two SHACL shapes. The left one, named :AddressShape, is meant to define valid addresses. A node v satisfying this shape must satisfy two (nested) constraints: the first one states that there must be at least one successor (sh:minCount 1) of v via property :telephone, and the second one states that there must be at most one successor of v via property :postalCode.
Validating an RDF graph against a set of shapes is based on the notion of “target nodes”, which mandates for each shape which nodes have to conform to it. In Figure 1, the right shape contains the triple :PersonShape sh:targetClass :Person, stating that its target nodes are all nodes of type :Person. Nodes may have to conform to additional shapes, due to shape references. For example, the right shape of Figure 1 contains one (non-recursive) shape reference, stating that every node v conforming to :PersonShape has at most one :address, which must conform to :AddressShape, and one recursive reference, stating that each foaf:friend of v must conform to :PersonShape. By recursion, we refer to (possibly n-ary) shape reference cycles. Unfortunately, the validation of a graph 3 https://www.w3.org/TR/shacl : AddressShape a sh : NodeShape ; sh : p r o p e r t y [ sh : path : t e l e p h o n e ; sh : minCount 1 ] ; sh : p r o p e r t y [ sh : path : postalCode ; sh : maxCount 1 ] .
: PersonShape a sh : NodeShape ; sh : t a r g e t C l a s s : Person ; sh : p r o p e r t y [ sh : path : a d d r e s s ; sh : maxCount 1 ; sh : node : AddressShape ] ; sh : p r o p e r t y [ sh : path f o a f : f r i e n d ; sh : node : PersonShape ] . against recursive shapes is left explicitly undefined in the SHACL specification. This is an important limitation for RDF graphs which are not tree-shaped. As an illustration, in Example 1, the RDF graph G1 is valid w.r.t. the shapes of Figure 1, whereas G2 is invalid, and the validity of G3 is left unspecified. Example 1.
G1 = f:p1 rdf:type :Person ; :address :a2 . :a2 :telephone :t3 .g G2 = G1 [ f:a2 :postalcode :c4 . :a2 :postalcode :c5 .g G3 = G1 [ f:p1 foaf:friend :p6 . :p6 foaf:friend :p1 .g
In this work, we set up the task of defining a robust semantics for graph validation in SHACL (including circular references), and studying its computational properties. A report is available online, which reflects the current state of our investigations: https://www.inf.unibz.it/krdb/KRDB%20files/tech-reports/ KRDB18-01.pdf.
Related Work. Boneva et al. [
Another related line of work, advocated in [
Validating a graph against recursive constraints In order to devise a formal semantics, we abstract away from the concrete syntax of SHACL. For shape constraints, we chose a concise notation inspired by Description Logics, expressive enough to encode the SHACL “Core Constraint Components” of the specification. For instance, the constraints in Figure 1 would be translated into two constraint definitions, one for each shape:
: AddressShape = ( 1 telephone:>) ^ ( 1 postalCode:>) PersonShape =: ( 1 address:>) ^ ( 0 address::AddressShape) ^
( 0 friend::PersonShape)
The semantics given in the SHACL specification needs to be extended in order to
handle recursive shapes. To this end, we follow the same path as in [
How to handle non-stratified constraints? For an input graph G and set S of shapes, let atoms(G; S) be the set of all atoms of the form s(v) built from shape names in S and nodes in G. Then a shape assignment may be viewed as a function from atoms(G; S) to truth values. But should be required to be a total function to ftrue; falseg? Such semantics may not behave well in the presence of non-stratified negation, as illustrated in Example 2. The only target node is v1, for shape s1. v1 has an r1-successor (namely v2) in G, therefore it verifies the left disjunct 1 r1:> of the constraint for s1. So intuitively, one would want to validate this unique target, and therefore the whole graph. But s2(v1) cannot be assigned a truth value which complies with the constraint for s2. If (s2(v1)) = true, then v1 does not verify 1 r2::s2 given . Conversely, if (s2(v1)) = false, then v1 does not violate 1 r2::s2 given .
Example 2.
G =: f(v1; r1; v2); (v1; r2; v1)g s1 =: ( 1 r1:>) _ ( 1 r2:s2) s2 = 1 r2::s2 target: v1 for s1
A solution is to allow to be a partial function, or equivalently a total function
from atoms(G; S) to ftrue; unknown; falseg, in order to define constraint evaluation
given . This is a key difference from the approach followed in [
How to define partial validation? The SHACL specification describes a graph
validation mechanism (for non-recursive shapes) which starts from a target atom, and
propagates the constraints required by this target only. One way to generalize this
approach to recursive shapes is to allow assigning unknown to an atom, even though
the corresponding constraint evaluates to true or false. For instance, in Example 2,
assigning a truth value to s1(v2) and s2(v2) seems unnecessary for the (unique)
target under validation. So could one also validate the graph with another assignment
0 = fs1(v1) 7! true; s2(v1) 7! unknown; s1(v2) 7! unknown; s2(v2) 7! unknowng, even
though s1(v2) and s2(v2) evaluate to false given 0? And in which cases (if any) do
these two semantics differ?
Is validation scalable? Our investigations so far indicate that graph validation
under such requirements is intractable in data complexity (i.e. when the constraints are
assumed to be fixed), even for constraints with stratified negation, as opposed to
seemingly comparable frameworks, such as stratified datalog [