RDF abstract syntax

This document uses the following labels for terms in the RDF abstract syntax:

• Iri - RDF IRI
• Blank - RDF blank node
• Lit - RDF literal

Simple shape expression schemas

The abstract syntax of shape expression schemas (or simply schemas) is given below. For now we use a simplified definition of one non-terminal, namely ShapeConstr, which is indicated by the temporary rule ShapeConstrTemp. We make this simplification in order to make defining the semantics easier, and we give the complete definition in Section sec: complex shape constraints.

A Schema is composed of at least one rule (Rule). Every rule associates with a label (ShapeLabel), a shape definition (ShapeDefinition), and possibly a number of additional conditions (ExtensionCondition) defined using an extension mechanism.

A shape definition is either a closed shape (ClosedShape), or an open shape (OpenShape). Both closed and open shapes are defined by a shape expression (ShapeExpr). Open shapes can have associated set of included properties (InclPropSet): properties of which arbitrary extra occurances are permitted. Closed and open shapes will be distinguished thanks the keywords close and open, respectively.

A shape expression is either the empty shape (EmptyShape) represented by the keyword emptyshape, or a triple constraint (TripleConstraint) or an inverse triple constraint (InverseTripleConstraint) followed by a cardinality constraint (Cardinality), or a negated version of the two latter (NegatedTripleConstraint, NegatedInverseTripleConstraint), or a some-of shape (SomeOfShape), or a one-of shape (OneOfShape), or a grouping shape (GroupShape), or a repetition shape (RepetitionShape).

Triple constraints are used to specify constraints to be satisfied by the triples having the focus node as subject, and the associated cardinality specifies how many triples satisfying the triple constraint are required. Inverse triple constraints play a similar role, but define constraints to be satisfied by the triples having the focus node as object. We will write a::C for the triple constraint with IRI a, and with value or shape constraint C. Cardinalities will be written as an interval in square brackets, and which maximum bound can be the special value unbound. In the examples, we omit writing the cardinality when the minimal and the maximal cardinality are both equal to one. That is, we write simply a::C for a::C[1;1]. Negated triple and inverse triple constraints are preceded by an exclamation mark (!).

A triple constraint can constraint the object of a triple in two different ways. It either requires for the object to have some particular value (value constraint), or it requires for the object node to satisfy a shape constraint. Inverse triple constraints are preceded by the ^ symbol, and allow only shape constraints for the subject node.

A value constraint can be specified in three different ways: as a set of concrete values, that can be IRI or literals; or as a literal data possibly XSD facet restriction attached to it; or as a kind of the node, among IRI, Blank, literal or non literal.

A shape constraint requires for the node type to satisfy one or more shapes. A disjunctive shape constraint requires for the object node to satisfy at least one among the enumerated shapes. A conjunctive shape constraint requires for the object node to satisfy all of the enumerated shapes. Additionally, a shape constraint can be negated, when preceded by an exclamation mark. This negates the required types, where negation is the usual logical negation; for instance, the negation of a disjunctive shape constraint requires for the object node to satisfy none of the enumerated shapes.

Complex shape expressions can be built thanks to the four operators: some-of, one-of, grouping, and repetition. A some-of shape (SomeOfShape) requires for one of the sub-expressions to be satisfied, but does not forbid for more of the sub-expressions to be satisfied. A one-of sape (OneOfShape) requires that exactly one of the sub-expressions is satisfied. A group shape (GroupShape) requires for the neighbourhood of the focus node to be split in as many sets of triples as there are sub-expressions, and every such set of triples must satisfy the constraint given by the corresponding sub-expression. A repetition shape (RepetitionShape) requires for the sub-shape to be repeted a number of times as specified by the cardinality constraint.

Finally, an extension mechanism allows to attach additional constraints to be satisfied by the nodes of given shape. Each such condition can be written in some extension language (ExtLangName), and the actual constraint is a Boolean function definition in the corresponding language with true asserting that the focus node does not meet the constraints in ExtDefinition.

We require an obvious criterion that every shape label that appears in the schema, appears in the left hand side of exactly one rule (that is, all shape labels are defined).

RDF instance example

The following example represents a shape my:UserShape composed of an group shape with two conjuncts:

1. An disjunctive shape with two disjuncts:
   1. A triple constraint with a predicate of foaf:name, a datatype of xsd:string, a minimum cardinality of 1, a maximum cardinality of 1.
   2. A triple constraint with a predicate of foaf:givenName, a datatype of xsd:string, a minimum cardinality of 1, no maximum cardinality.
2. A triple constraint with a predicate of foaf:mbox, a node type of RDF IRI, a minimum cardinality of 1, no maximum cardinality.

# shapes (Turtle)
	  my:UserShape a sh:Shape ;
	  sh:choice [
          sh:property [
          sh:predicate foaf:name ;
          sh:valueType xsd:string ;
          sh:minCount 1 ; sh:maxCount 1
          ] ;
	  
          sh:property [
          sh:predicate foaf:givenName ;
          sh:valueType xsd:string ;
          sh:minCount 1
          ] ;
	  ] ;                                          
	  sh:property [
          sh:predicate foaf:mbox ;
          sh:nodeType sh:IRI ;
          sh:minCount 1
	  ] .

Preliminaries

We start with few preliminary definitions and notations.

Intuitively, negshapes(S) is the set of shapes labels for which one needs to check whether some nodes in a graph do not satisfy these shapes, in order to validate the graph against the schema S. Whatever the kind of a value constraint (value set, or literal data type, or node kind), it defines a set of values. For instance, the allowed values of the literal data type constraint int are all the literal integer values; the allowed values of the nonliteral value constraint are all IRI and all blank nodes.

The semantics of shape expression schemas is sound only for well-defined schemas. Therefore, from now on, we consider only well defined schemas.

Declarative semantics of shape expression schemas

Negated triple and inverse triple constraints are introduced as syntactic facility, their semantics being defined using their non negated versions and zero cardinality. More precisely, for every triple or inverse triple constraint X, its negated version !X is a shortcut for X[0;0]. Therefore, in what follows we do not give semantics for negated constraints. Note also that, even though called negated, these constraints do not introduce negation in the sense of negated shapes, and do not interfere with well-definedness of schemas.

In order to handle triple constraints and inverse triple constraints, the triples of a graph will be labeled depending on whether they have the focus node as subject, or as object. Concretely a labeled triple is either an outgoing triple of the form (out, n, p, u), or an incoming triple of the form (inc, u, p, n), where (n, p, u) and (u, p, n) are triples, and out and inc are special labels. From now on, we consider that all triples are labeld, and call them simply triples (even though technically they are quadruples).

The following definition introduces the notion of satisfiability of a shape constraint by a set of triples. Such satisfiability is going to be used for checking that the neighborhood of a node satisfies locally the constraints defined by a shape expression, without taking into account whether the shapes required by the triple constraints and inverse triple constraints are satisfied.

Note that the conditions for some-of and one-of shapes are identical. The distinction between both will be made by taking into account also the non-local, shape constraints.

The above definition can be written using the following set of inference rules. We denote Neigh |- Expr the fact that Neigh satisfies Expr.

If a set of triples Neigh satisfies a shape expression Expr, then one can construct (at least one) proof tree which root is Neigh |- Expr, using the above induction rules. Given such proof tree, it can be shown that every outgoing triple (out, n, p, u) in Neigh appears in the conclusion of exactly one application of rule-triple-constraint. Similarly, every incoming triple (out, u, p, n) in Neigh appears in the conclusion of exactly one application of rule-inverse-triple-constraint. For every outgoing, resp. incoming triple (x, n, p, u) in Neigh, let wm(x, n, p, u) be the triple constraint p::C, resp. the inverse triple constraint ^p::C, that appears in the conclusion of the same rule application as (x, n, p, u) (where x is one of out or inc). We call wm a witness mapping (for the fact that Neigh satisfies Expr). Note that every proof tree defines a unique witness mapping.

For an RDF graph G and a node n in G, the outgoing neighbourhood of n in G is the set of labeled triples out(G,n) = (out, n, p, u) s.t. (n, p, u) is a triple that belongs to the graph G, and the incoming neighbourhood of n in G is the set of labeled triples inc(G, n) = (inc,u, p, n) s.t. (u, p, n) is a triple that belongs to the graph G.

On the implementation level, extension conditions are to be handled by a plugin mechanism, in which the validation procedure delegates checking of the extension condition to a registered plugin. The result of evaluating the extension condition can be true: the extension condition is satisfied, or false: the extension condition is not satisfied, or error: there was an error during the execution, or undefined: the evaluation procedure didn't find the appropriate plugin. On the semantics level, we suppose that for every extension language lang, there exists an oracle function f_lang that takes as parameters an RDF graph, an IRI corresponding to the focus node, and a string corresponding to the extension condition, and returns as result one of true, false, error, and undefined. For the unsupported extension languages (the result is undefined), the default behaviour is to consider that the constraint is satisfied; this however can be parametrized.

We now give a more intuitive explanation of the above definition.

The fact that t(u) satisfies a shape constraint C is used to ensure that the typing t correctly propagates the shape constraints required in the shape triple constraints.

The set Matching(n, t, X) contains all the triples in the neighbourhood of the node n that match the constraint X while propagating the shape constraints required by X.

Now, passing into review all the conditions for a valid typing. Intuitively, a valid typing will associate the shape T to a the node n only if n satisfies the constraints for T. As some constraints require to check that some nodes do not satisfy some shapes, we also keep track of the non-satisfied shapes, by associating negated types with those nodes.

• Intuitively, we want to associate the negated shape !T to a node n only if n does not satisfy the constraints for T. This requirement is insured by the fact that replacing !T by T does not yield a valid typing.
• All the other conditions are there to ensure that the typing t properly captures the satisfiability of the non negated constraints.
  1. The triples in the neighborhood of the node n contribute to satisfy the shape T in different ways, and are therefore dispatched to three disjoint sets, Matching, OpenProp and Rest.
  2. The set Rest contains all the triples which property is not mentioned in the definition of the shape T. Note that we consider separately the outgoing and incoming properties.
  3. The set Matching contains all the triples that satisfy some of the triple constraints or inverse triple constraints from the definition of the shape T. It follows that OpenProp contains the triples whose property is mentioned in T, but that do not satisfy the condition for the object node (for outgoing triples) or for the subject node (for incoming triples).
  4. A closed shape does not allow outgoing triples which property is not mentioned in the shape definition, nor triples which property is mentioned, but did not satisfy the recursive shape constraints or the value constraints. On the other hand, the "closedness" criterion applies only on the outgoing triples: the fact that there is no constraint on Rest_inc means that we always allow incoming triples whose properties are not mentioned. The asymmetric treatment of incoming and outgoing triples is a design choice: we offer the possibility to define more precise constraints for outgoing triples, as such constraints appear to be more useful, according to the use cases.
  5. An open shape allows all triples which properties are not mentioned (no restriction on the set Rest), and allows also outgoing triples in OpenProp as soon as their property is authorized by the included open properties. Note that the included properties are only allowed for the outgoing triples.
  6. The most complex condition ensures that the constraints are satisfied recursively. As a first condition, all the triples that matched some of the triple constraints (or inverse triple constraints), must participate in satisfying the local and recursive constraints specified in the type definition. This requirement is translated by the fact that Matched |- expr(T, S). Moreover,
     • If an outgoing triple (out, n, p, u) participates in satisfying some triple constraint p::C, then the shape or value constraint C is satisfied by the object node u. Additionally, we give a "priority" to the value constraints, requiring that whenever the triple (out, n, p, u) satisfies some of the value triple constraints, it cannot be used as a witness for some of the shape triple constraints;
     • Similarly, the shape constraints required by the inverse triple constraints are correctly propagated through the incoming triples.
     • The next condition ensures that in every one-of constraint, only one of the sub-constraints is satisfied. This is ensured by the fact that if this sub-constraint is removed, then no valid typing can be found.
  7. The very last condition ensures that the extension constraints are satisfied.

Stemming for properties

A stem is an IRI ending with a '~', and representing the (infinite) set of IRI that share the same prefix. For instance, issue:assigned~ stands for all IRI that start with issue:assigned. In shape expression, an IRI can appear in the following positions (excluding the IRI from the SHACL vocabulary):

• in the set of included properties for an open shape;
• in value constraints for defining the set of allowed values;
• in triple constraints (or inverse triple constraints) as properties.

The two former situations already correspond to sets (of properties, or of values), so stems are already handled by the semantics. In what follows, we explain how to handle stems that appear as properties in triple constraints (it is similar for inverse triple constraints, so we omit them here). More precisely, we show how instead of single properties, triple constraints can be defined on top of sets of properties.

Consider the following modification of the abstract syntax for the TripleConstraint rule.

Such set of IRI can be defined by a stem, or by any other means (e.g. enumeration of the elements of the set, or regular expression, etc.). We then modify the following definitions.

properties(Expr) is the union of the sets of properties A of all triple constraints A::C that appear in the shape expression Expr.

[Triple matches constraint] An outgoing triple (out, n, p, u) matches a triple constraint A::C (where A is a set of properties) if p ∈ A.

[Typing, valid typing]

• Matching(n, t, A::C) = {(out, n, p, u) ∈ G | p ∈ A and u ∈ allowed(C)} if A::C is a value triple constraint;
• Matching(n, t, A::C) = {(out, n, p, u) ∈ G | p ∈ A and t(u) satisfies C} if A::C is a shape triple constraint.

All the other definitions remain unchanged. This allows to handle sets of properties in triple constraints.