The Shape Constraint Language (SHACL) was recently standardized by the
W3C as a formalism for checking the quality of RDF graphs; we refer to [
The standard speci es a syntax for expressing SHACL constraints and
describes when they are validated by RDF graphs. However, it leaves unde ned the
semantics of recursive constraints, i.e., constraints that involve cyclic
dependencies. To address this, some logic-based proposals to formalize the semantics of
full SHACL have emerged recently. Andresel et al. [
To make SHACL truly useful and facilitate its adoption, we need automated
tools that e ciently implement validation and scale well in the presence of large
RDF graphs and sets of constraints. There are already signi cant e orts in this
direction for fragments of SHACL [
In this extended abstract we present preliminary work on adapting the Magic
Sets technique, known from logic programs with (unstrati ed) negation [
Let N, C, and P denote countably in nite, mutually disjoint sets of nodes, class
names, and property names, respectively. A data graph G is a nite set of atoms
of the form B(c) and p(c; d), where B 2 C, p 2 P, and c; d 2 N. The set of
nodes appearing in G is denoted with V (G). We assume a countably in nite set
S of shape names, disjoint from N [ C [ P. A shape atom is an expression of the
form s(a), where s 2 S and a 2 N. A path expression E is a regular expression
built using the usual operators , , [ from symbols in P+ = P [ fp j p 2 Pg. If
p 2 P, then p is the inverse property of p. A (complex) shape is an expression
obeying the syntax: ; 0 ::= > j s j A j a j ^ 0 j : j n E: j E = E0; where
s 2 S, A 2 C, c 2 N, n is a positive integer, and E, E0 are path expressions.
A (shape) constraint is an expression s where s 2 S and is a possibly
complex shape; we may refer to as the body of the constraint and s as head.
W.l.o.g. we view targets as shape atoms of the form s(a), where s 2 S and a 2 N.
A SHACL document is a pair (C; T ), where (i) C is a set of constraints and (ii)
T is a set of targets. The evaluation of a shape expression is given by assigning
nodes of the data graph to shape names. A (shape) assignment for G is a set
I = G [ L, where L is a set of shape atoms such that a 2 V (G) for each s(a) 2 I.
The evaluation of a shape w.r.t. I is given in terms of a function that maps a
1 https://github.com/medinaandresel/shacl-asp
2 http://www.dlvsystem.com/dlv/
shape expression to a set of nodes, and a path expression to a set of pairs of
nodes. We refer to [
We now brie y describe the Magic algorithm for SHACL, which takes as input a document (C; T ) and outputs a new optimized shapes graph against which data graphs can be validated, see Figure 1. The method comprises four main steps: T C
Magic Shape Algorithm
Create Magic Seeds
Adorn Generate Modify
C_magic
T
data graph
SHACL
Validator
1. Create Magic Seeds: for each target shape atom s(a) 2 T , the algorithm
adds a constraint of the form s magic a, called a magic seed.
2. Adorn: for each shape name s occurring in the targets T , an adorned shape
sb is pushed onto a stack. Procedure Adorn then pops sb and propagates the
adornment to the body of the constraints with head s, pushing each freshly
adorned shape onto the stack.
3. Generate. The adorned set of constraints is then used to generate \magic"
constraints through the procedure Generate. Roughly, for a constraint r of
the form s , it creates a new constraint with s magic in the body and
s0 magic in the head for each adorned shape name s0 in . In case that in
the constraint two shapes are connected by a path expression E, the path
expression has to be inverted.
4. Modify enhances the body of each adorned constraint with a magic version
of the shape occurring in the head of the constraint, i.e. r will be rewritten
as s s magic ^ and added to the set of modi ed constrains.
In the presence of arbitrary negation and recursion, we also need to identify the
so-called dangerous constraints that appear under the scope of negation. If they
are relevant for validating the target, their adornments are propagated also from
the body to the head [
Example 1. Consider a SHACL document (C; T ), where C consists of the constraints s1 s2, s2 s3 ^ s4, s3 5 p:s5, s6 :s6, and T = fs1(a)g. The algorithm rst adds s1 magic a. Since s1 appears in T , the shape names s1 to s5 and the corresponding constraints will be adorned. The last (disconnected) constraint will not participate in the resulting program. Generate(ra) adds s3 magic^ s2 magic ^ s3 ^ s4, and s3 s2 magic s1 magic, s3 magic s2 magic, s4 magic s2 magic and s5 magic p :s3 magic. Finally, the modi ed constraints are: s1 s1 magic ^ s2, s2 5 p:s5.
1 3
We implemented a prototype of the Magic Shapes Algorithm. It receives as input a shapes graph (in Turtle syntax) and produces as output a new shapes graph. To evaluate the usefulness of the approach, we perform experiments with the Shacl-Asp validator. For each test case, we run the validator once with the original shapes graph and once with the magic variant.
Data Graph. The data for the experiments was obtained from DBPedia
(version 2016-10)3. More precisely, we used the datasets \PersonData", \Instance
Types", \Labels", \Mappingbased Literals" and \Mappingbased Objects". The
datasets are in Turtle syntax and contain about 61 million triples (7.7 GB).
Shapes Graph. We created six shapes graphs4 S1 to S6 from the domain of
movies and actors, similar to those in [
Setting. The experiments were performed on a Linux server with a 24 core Intel Xeon CPU running at 2.20 GHz and 264 GB of RAM. We used the DLV based Shacl-Asp validator. An Apache Jena TDB5 was used as an RDF triple store to retrieve the relevant triples from the data graph, which are transformed into ASP facts; this was done for the input shapes graph and for its magic version. Results. Table 1 summarizes the results of our experiments. Although all inputs except S1 are recursive, the output of the Magic Shapes algorithm is only recursive for S3, S5 and S6. The shapes graphs S4 to S6 are inconsistent in general. S4 and S5 become consistent after running the algorithm since the constraints causing inconsistency are not relevant for validating the targets; this is not the case for S6. In some cases the output of the algorithm falls in a fragment that is supported by Shacl2Sparql or Trav-Shacl although the original shapes graphs are not, e.g., S4 and S5. We distinguish the non-recursive fragment Lnon-rec and the fragment Ls, which restricts the interaction between recursion and negation. The last column shows that the Magic Shapes algorithm signi cantly improves the performance of the DLV validator. 4
In this extended abstract, we have presented initial results on adapting the Magic Set technique for improving the performance of SHACL validators. This is par3 http://downloads.dbpedia.org/wiki-archive/downloads-2016-10.html 4 https://github.com/biziloehnert/magicSHACL/tree/master/experiments 5 https://jena.apache.org/documentation/tdb/ case S1 S2 S3 S4 S5 S6
#shapes recursive inconsistent Lnon-rec Ls shacl-asp orig. magic orig. magic orig. magic orig. magic orig. magic orig. magic ticularly useful when the input shapes graphs contain unrestricted interaction of recursion and negation. We performed experiments with Shacl-Asp, the only SHACL validator that can support such shape graphs, and showed that the simpler shapes graphs produced by the Magic Shapes algorithm are evaluated signi cantly more e ciently than the original ones. The algorithm may also discard constraints with recursion or negation that are not relevant for validating the targets, possibly eliminating some irrelevant inconsistency. The resulting shapes graphs may fall into SHACL fragments that can be handled by more optimized SHACL adopters such as Shacl2Sparql and Trav-Shacl, thus enabling the use of these engines on graphs that they could not originally support.
We are running some experiments to identify cases where the Magic Shapes technique can also improve the performance of Shacl2Sparql or Trav-Shacl on inputs that they can handle.