The Shape Constraint Language (SHACL) is a recently standardized language for expressing constraints on RDF graphs. It is the result of industrial and academic e orts to provide solutions for checking the quality of RDF graphs and for declaratively describing (parts of) their structure. We recommend [9] for an introduction to SHACL and its close relative ShEx. Among others, the SHACL standard provides a syntax for writing down constraints, as well as describes the way RDF graphs should be validated w.r.t. a given set of SHACL constraints. However, some aspects of validation were not completely speci ed in the standard, like the semantics of validation for constraints with cyclic dependencies. To address these shortcomings, recently several formalizations of SHACL have emerged, which describe it in logic-based languages with clear semantics. E.g., some works resort to rst-order logic [6], while some use logic programming [2]. SHACL is closely related to expressive Description Logics (DLs). Such connections have already been observed in [10], where the authors reduce implication of SHACL constraints to concept subsumption in DLs. The key di erence between SHACL and DLs is that SHACL makes the closed-world assumption (CWA), while DLs use the open-world assumption (OWA). To understand the di erence, RDF graphs equipped with SHACL constraints can be thought of as DL knowledge bases in which all roles and some concept names are closed predicates in the context of DLs with closed predicates (see [8, 11]), i.e., where only some concept names are allowed to be non-closed predicates. In SHACL, the basic computational problem is to check whether a given RDF graph G validates a SHACL document (C; T ), where C is a speci cation of validation rules (constraints ) and T is a speci cation of nodes to which the validation rules should apply (targets). In order to make SHACL truly useful and widely accepted, we need automated tools that implement not only validation, which results in \yes" or \no" answers, but also support the users in their e orts Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). ? Partially supported by the Vienna Business Agency and the Austrian Science Fund (FWF) projects P30360 and P30873. Axel Polleres' work is supported by funding in the European Commission's Horizon 2020 Research Programme under Grant Agreement Number 957402.
to understand the reasons why a given graph validates or not against a given document. The SHACL speci cation stresses the importance of explaining validation outcomes and introduces the notion of validation reports for this purpose. If a graph validates a document, the standard has clear guidance how the validation reports should look like. However, the situation is di erent when the graph does not validate. The principles of validation reports in case of non-validation are left largely open in the standard, which speci es little beyond requiring that the node and constraint violated are indicated. It is not hard to see that, in general, there may be a very large number of possible reasons for a speci c validation target to fail, and it is far from obvious what should be presented to the user in validation reports. This is precisely the topic of our study.
In this work6, we advocate explanations in the style of database repairs [
The main goal of this work is to formalize the notion of explanations for SHACL, to de ne a collection of reasoning tasks for exploring explanations, and to characterize their computational complexity. In a nutshell, the contributions of this paper are as follows:
To explain non-validation of a SHACL document (C; T ) by an RDF graph G, we introduce the notion of a SHACL Explanation Problem (SEP). A solution to a SEP is a pair (A; D) that describes a collection A of facts to be added to G and a collection D of facts to be deleted from G, so that the resulting graph does validate the document (C; T ). We consider natural preference orders over explanations, and study also explanations that are minimal w.r.t. set inclusion or w.r.t. cardinality. We illustrate the use of explanations with some examples.
We de ne a collection of inference services for reasoning about explanations
for non-validation. We start with the basic tasks of recognizing whether a given
candidate is indeed a (preferred) explanation, and deciding whether a (preferred)
explanation exists. We also de ne the problems of checking whether a given atom
is relevant (resp., necessary) as an addition or as a deletion in some explanation
(resp., all explanations). These tasks are reminiscent of basic reasoning problems
in logic-based abduction [
We study the computational complexity of the introduced reasoning tasks and characterize both combined and data complexity. Our results range from tractability to completeness for the second level of the polynomial hierarchy.
After studying the general setting, we turn our attention to non-recursive
SHACL constraints. We show that with one exception, reasoning about
explanations in the presence of non-recursive constraints does not become easier in
terms of computational complexity. The exception is the problem of recognizing
an explanation, which becomes tractable in the absence of a preference order.
6 This is an extended abstract of [
Title Suppressed Due to Excessive Length As a side result we show that SHACL validation in the presence of non-recursive constraints is P-complete.
Finally we consider a generalization of SEPs with restricted explanation signatures. This useful feature allows, e.g., to specify that some classes and properties are read-only, prohibiting deletions from them during explanations. Also for this setting, we establish a collection of complexity results, including the case of non-recursive constraints.
Ahmetaj et al.