Satisfiability and Containment of Recursive SHACL
  The Shapes Constraint Language (SHACL) is the recent W3C recommendation
language for validating RDF data, by verifying certain shapes on graphs.
Previous work has largely focused on the validation problem and the standard
decision problems of satisfiability and containment, crucial for design and
optimisation purposes, have only been investigated for simplified versions of
SHACL. Moreover, the SHACL specification does not define the semantics of
recursively-defined constraints, which led to several alternative recursive
semantics being proposed in the literature. The interaction between these
different semantics and important decision problems has not been investigated
yet. In this article we provide a comprehensive study of the different features
of SHACL, by providing a translation to a new first-order language, called SCL,
that precisely captures the semantics of SHACL. We also present MSCL, a
second-order extension of SCL, which allows us to define, in a single formal
logic framework, the main recursive semantics of SHACL. Within this language we
also provide an effective treatment of filter constraints which are often
neglected in the related literature. Using this logic we provide a detailed map
of (un)decidability and complexity results for the satisfiability and
containment decision problems for different SHACL fragments. Notably, we prove
that both problems are undecidable for the full language, but we present
decidable combinations of interesting features, even in the face of recursion.
