KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Reasoning about Explanations for Non-validation in SHACL

  1. Shqiponja Ahmetaj(Vienna University of Economics and Business, Austria)
  2. Robert David(Semantic Web Company, Austria)
  3. Magdalena Ortiz(Technical University of Vienna, Austria)
  4. Axel Polleres(Vienna University of Economics and Business, Austria, Complexity Science Hub Vienna, Austria)
  5. Bojken Shehu(Polytechnic University of Tirana, Albania)
  6. Mantas Šimkus(Technical University of Vienna, Austria)


  1. KR and the Web, Semantic Web
  2. Explanation finding, diagnosis, causal reasoning, abduction


The Shapes Constraint Language (SHACL) is a recently standardized language for describing and validating constraints over RDF graphs. The SHACL specification describes the so-called validation reports, which are meant to explain to the users the outcome of validating an RDF graph against a collection of constraints. Specifically, explaining the reasons why the input graph does not satisfy the constraints is challenging. In fact, the current SHACL standard leaves it open on how such explanations can be provided to the users. In this paper, inspired by works on logic-based abduction and database repairs, we study the problem of explaining non-validation of SHACL constraints. In particular, in our framework non-validation is explained using the notion of a repair, i.e., a collection of additions and deletions whose application on an input graph results in a repaired graph that does satisfy the given SHACL constraints. We define a collection of decision problems for reasoning about explanations, possibly restricting to explanations that are minimal with respect to cardinality or set inclusion. We provide a detailed characterization of the computational complexity of those reasoning tasks, including the combined and the data complexity.