2024/07/19 by Ahmetaj, Shqiponja, David, Robert, Polleres, Axel +1
Computer Science · #Advanced Database Systems and Queries #Answer Set Programming #Computing methodologies → Logic programming and answer set programming #Database Repairs #Knowledge Graphs #Logic, Reasoning, and Knowledge #SHACL #Semantic Web #Semantic Web and Ontologies #Shapes Constraint Language #Theory of computation → Constraint and logic programming
paper · pdf · doi:10.4230/tgdk.3.3.1
openalex publication_date 2024/07/19 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28
The Shapes Constraint Language (SHACL) is a recent standard, a W3C recommendation, for validating RDF graphs against shape constraints to be checked on target nodes of a data graph. The standard also describes the notion of validation reports, which detail the results of the validation process. In case of violation of constraints, the validation report should explain the reasons for non-validation, offering guidance on how to identify or fix violations in the data graph. Since the specification left it open to SHACL processors to define such explanations, a recent work proposed the use of explanations in the style of database repairs, where a repair is a set of additions to or deletions from the data graph so that the resulting graph validates against the constraints. In this paper, we study such repairs for non-recursive SHACL, the largest fragment of SHACL that is fully defined in the specification. We propose an algorithm to compute repairs by encoding the explanation problem - using Answer Set Programming (ASP) - into a logic program, where the answer sets contain (minimal) repairs. We then study a scenario where it is not possible to simultaneously repair all the targets, which may be the case due to overall unsatisfiability or conflicting constraints. We introduce a relaxed notion of validation, which allows to validate a (maximal) subset of the targets and adapt the ASP translation to take into account this relaxation. Finally, we add support for repairing constraints which use property paths and equality of paths. Our implementation in clingo is - to the best of our knowledge - the first implementation of a repair program for SHACL.