SHACL Validation under the Well-founded Semantics

W3C has recently introduced SHACL as a new standard for writing integrity constraints on graph-structured data (specifically, on RDF graphs). Unfortunately, the standard defines the semantics of non-recursive constraints only, leaving the case of recursive constraints open. This has spurred recent research efforts into finding a suitable, mathematically crisp semantics for constraints with cyclic dependencies. In this paper, we argue that recursive SHACL can be naturally equipped with a semantics inspired in the well-founded semantics for recursive logic programs with default negation. This semantics is not only intuitive, but it is also computationally tractable, unlike the previous proposals. The semantics is tolerant to constraint violations that are outside the realm of the so-called validation targets, which is a feature that is highly relevant in practice. In addition to defining the well-founded semantics using a notion of unfounded sets, we draw a connection to the classic definition of the well-founded semantics in logic programming: we provide a simple (yet inefficient) translation of recursive SHACL under the well-founded semantics into propositional logic programs under the well-founded semantics. This translation also provides a basis for a highly optimized SHACL validation engine, which we also present in this paper. Our system performs graph validation by producing a optimized logic program that can be evaluated using the DLV deductive database engine. The system has pay-as-you-go behavior: for validation with non-recursive constraints, the system avoids using a deductive database and instead only uses SPARQL queries over a RDF triplestore.