Magic Shapes Algorithm for SHACL Validation

Abstract

Für die Validierung von RDF Graphen hat das W3C mit der Shapes Constraint Language (SHACL) einen Standard definiert. Für eine erfolgreiche Anwendung von SHACL, selbst auf sehr große RDF Graphen, werden Methoden benötigt, die eine effiziente Validierung ermöglichen. Ansätze für eine effiziente Validierung von SHACL existieren bereits, aber diese optimierten Validierer konzentrieren sich auf die “tractable” Fragmente der SHACL Sprache und unterstützen nicht die uneingeschränkte Interaktion zwischen Rekursion und Negation in Shapes Graphen. Bei Vorhandensein von Rekursion und Negation ist ein Ziel-orientierter Ansatz, wie bestehende Validatoren ihn verfolgen, nicht anwendbar, da dies die Betrachtung des gesamten Datengraphens und damit eine globale Berechnung erfordert. Dies ist auch erforderlich wenn die Targets des Shapes Graphen nur einen Teil des Datengraphen adressieren, der von der Interaktion zwischen Rekursion und Negation nicht betroffen ist. Neben der Tatsache, dass das Zusammenspiel von Rekursion und Negation die Validierung rechenintensiv macht, können bei der globalen Validierung der Graphen Inkonsistenzen auftreten, die aber für die Validierung der Ziele des ShapesGraphen möglicherweise irrelevant sind.Aus diesem Grund beschäftigt sich diese Masterarbeit mit der Validierung von SHACL bei uneingeschränkter Interaktion von Rekursion und Negation. Zu diesem Zweck wird der Magic Shapes Algorithmus vorgestellt, der als Eingabe einen Shapes Graphen erhält und einen Magic Shapes Graphen ausgibt, der ebenfalls dem Standard von SHACL entspricht. Der Magic Shapes Graph enthält nur die für die Validierung der Targets relevanten Constraints. Diese Constraints werden um magic Shape Constraints erweitert, die den RDF Graphen während der Validierung auf die notwendigen Knoten reduzieren. Im Fall, dass keine Inkonsistenzen durch den RDF Graph und der Interaktion von Rekursion und Negation entstehen, ist das Ergebnis der Validierung für den Eingangs Shapes Graphen, sowie für die magic Variante äquivalent. Andernfalls ermöglicht der Magic Shapes Algorithmus eine Ziel-orientierte Validierung und lässt Inkonsistenzen, die das Validieren der fokusierten Knoten nicht betreffen außen vor. Im Rahmen der Masterarbeit wurde der Algorithmus implementiert und Experimente mit dem existierenden Validierer shacl-asp durchgeführt.

The Shapes Constraint Language (SHACL) is the W3C standard for the validation of RDF graphs. A key prerequisite for its successful adoption is the availability of automated tools that efficiently validate targeted constraints (known as shapes graphs) over possibly very large RDF graphs. There are already significant efforts to produce optimized engines for SHACL validation, but they focus on fragments of SHACL that restrict the use of recursion and negation. Without such restrictions, there is no validator beyond a proof-of-concept prototype. Existing techniques require a global computation on the entire data graph that is not only computationally very costly, but also brittle, and can easily result in validation failures due to conflicts that are irrelevant to the validation targets. For this reason, the aim of this master thesis is the validation of SHACL in presence of unrestricted interaction of recursion and negation. We present a 'magic' transformation—based on Magic Sets as known from Logic Programming—that receives as input a SHACL shapes graph, and transforms it into a new `magic' shapes graph whose validation considers only the relevant neighbourhood of the targeted nodes. The magic shapes graph is equivalent to the input whenever there are no conflicts with the data, and in case the validation of the original input fails due to conflicts that are irrelevant to the target, the magic version may still admit a lazy, target-oriented validation. The algorithm was implemented as part of the master thesis, and we perfomerd experiments to assess its effect on the existing protptype SHACL-ASP, and its potential to help develop scalable validators for full SHACL.