Rewrite Once, Validate Anywhere: Producing OWL-Aware SHACL Constraints (Extended Version)

Anouk Oudshoorn; Piotr Gorczyca; Dörthe Arndt

cs.LOAug 14, 2026

Rewrite Once, Validate Anywhere: Producing OWL-Aware SHACL Constraints (Extended Version)

Authors: Anouk Oudshoorn, Piotr Gorczyca, Dörthe Arndt

Organizations: Institute of Logic and Computation, TU Wien, Austria · Computational Logic Group, TU Dresden, Germany · ScaDS.AI, Dresden/Leipzig, Germany

Abstract

The Shapes Constraint Language (SHACL) is a W3C recommendation to express syntactic constraints, called shapes, on RDF graphs. SHACL validators are used to test whether a given graph adheres to such a shape. However, RDF graphs often come with OWL ontologies, whose implicit knowledge needs to be taken into account. This is classically handled by first applying reasoning and then performing the constraint checking on the results, often using different technologies which makes the process inefficient and vulnerable for mistakes. To overcome this, we propose to internalise the OWL axioms in the SHACL constraints; we construct a rewriting which takes as input both shapes and an OWL EL $^-$ ontology -- a fragment of OWL EL restricting the usage of existential restrictions -- and produces SHACL constraints. This output can then be evaluated by any validator supporting SHACL core regardless of its reasoning support, while yielding the same results as the traditional approach. The implementation of our translation is evaluated both against applying state-of-the-art reasoners and validators consecutively, as against validators with built-in reasoning support. For our benchmark, we show that our approach is in general more efficient in finding violations compared to the sequential approach, thus providing a powerful tool which simplifies combining reasoning with validation.

Figures & tables

	$\displaystyle\mathcal{I}(c)$	$\displaystyle:=\{c^{\mathcal{I}}\}$
	$\displaystyle\mathcal{I}(s)$	$\displaystyle:=\{e\in\varphi^{\mathcal{I}}\mid s\leftarrow\varphi\in\mathcal{C}\}$
	$\displaystyle\mathcal{I}(A)$	$\displaystyle:=A^{\mathcal{I}}$
	$\displaystyle\mathcal{I}(\lnot\varphi)$	$\displaystyle:=\Delta^{\mathcal{I}}\setminus\mathcal{I}(\varphi)$
	$\displaystyle\mathcal{I}(\varphi\sqcap\varphi^{\prime})$	$\displaystyle:=\mathcal{I}(\varphi)\cap\mathcal{I}(\varphi^{\prime})$
	$\displaystyle\mathcal{I}(\exists_{\geq n}E.\varphi)$	$\displaystyle:=\{e\in\Delta^{\mathcal{I}}\mid\|\{e^{\prime}\in\Delta^{\mathcal{I}}\mid(e,e^{\prime})\in E^{\mathcal{I}}\land e^{\prime}\in\mathcal{I}(\varphi)\}\|\geq n\}$
	$\displaystyle\mathcal{I}(E=E^{\prime})$	$\displaystyle:=\{e\in\Delta^{\mathcal{I}}\mid\{\exists e^{\prime}\in\Delta^{\mathcal{I}}\mid(e,e^{\prime})\in E^{\mathcal{I}}\}=\{e^{\prime}\in\Delta^{\mathcal{I}}\mid(e,e^{\prime})\in E^{\prime\mathcal{I}}\}\}$

Figure 1: Evaluating shape expressions

Figure 2: Cactus plot comparing successful instances across evaluated approaches. The x-axis shows total execution time per instance in seconds (symlog scale: linear below 1s, logarithmic above). The y-axis shows the cumulative number of instances solved within that time; lines reaching higher values indicate better coverage, lines further left indicate faster execution. Colors denote the approach: blue – rewriting, green/red/orange – baseline ( HermiT / JFact / Pellet ), purple – pySHACL with inference. Line styles distinguish validators ( TopBraid : dash-dot, Isaitb : dashed, Jena : dotted, pySHACL : solid). Rewriting (blue) achieves complete coverage of all 1500 instances in under 10s. Among the baseline methods, HermiT and Pellet reach up to 1300 instances and require up to several hundred seconds; JFact stalls at around 600 instances. Both pySHACL inference modes reach around 1400 instances and are considerably slower than the rewriting approach.

Approach	T.R.	Av.R.	Validator	V.E.	T.V.	Av.V.	T/O	Success (%)
Rewriting	1.05h	2.53s	Isaitb	0	1.11h	2.66s	0	1500	(100.0%)
			Jena	0	0.71h	1.71s	0	1500	(100.0%)
			pySHACL	892	0.51h	3.02s	0	608	(40.5%)
			TopBraid	0	0.81h	1.93s	0	1500	(100.0%)
HermiT	51.4h	123.3s	Isaitb	1	0.71h	1.98s	200	1299	(86.6%)
			Jena	0	0.49h	1.36s	201	1299	(86.6%)

Table 1: Results per approach and validator. T.R./Av.R. – total/average reasoning or rewriting time; T.V./Av.V. – total/average validation time; V.E. – validator errors; T/O: timeouts; Success – successfully solved instances and success rate. For pySHACL with inference, reasoning and validation are a single step, so only validation statistics are reported.

Parameter	Description
numClasses (nC)	Number of named classes (class names)
numRoles (nR)	Number of object properties (role names)
numIndividuals (nI)	Total individuals; first 20% are nominals ( $N_{I}$ ), rest are data graph individuals ( $N_{A}$ )
numGCIs (nGCI)	Number of general concept inclusions
numDomains (nD)	Number of domain axioms $\mathit{dom}(r)\sqsubseteq C$
numRanges (nRn)	Number of range axioms $\mathit{ran}{r}\sqsubseteq C$

Table 2: Benchmark generator parameters (top) and their instantiations across difficulty levels 1–15 (bottom).

Level	#instances		mean #triples per instance
Level	Pos.	Neg.	TBox	Shapes	Data Graph	Rewriting	HermiT	JFact	Pellet
1	50	50	44	12	55	196	135	135	134
2	4	96	97	12	112	302	242	242	242
3	0	100	193	12	199	519	420	419	421
4	2	98	333	12	300	849	669	664	678
5	0	100	666	19	700	1 789	1 498	1 490	1 505

Table 3: Per-level instance statistics and mean RDF triple counts. Positive/Negative: conforming/non-conforming instances. OWL: input TBox; SHACL: input shapes; Rewriting: output of the OWL-aware rewriting; HermiT / JFact / Pellet : materialized data graph after reasoning.

Approach	Min.	Med.	Max.	Validator	Min.	Med.	Max.
Rewrit.	0.18s	0.88s	15.6s	Isaitb	1.75s	2.13s	8.52s
				Jena	0.93s	1.26s	6.92s
				pySHACL	0.24s	0.48s	145.0s
				TopBraid	1.14s	1.40s	8.35s
HermiT	0.47s	2.29s	511.6s	Isaitb	1.78s	1.92s	7.84s
				Jena	0.92s	1.04s	317.8s

Table 4: Minimum, median, and maximum reasoning/rewriting time (Min./Med./Max., left) and validation time (Min./Med./Max., right) per approach and validator, computed over successfully completed instances only (i.e., excluding reasoning/rewriting timeouts and validator errors). Note that the minimum validation times are nearly identical between validators. This is likely due to the overhead of the validator itself per call, i.e., a fixed cost of launching the validator as a fresh process. The minima do in fact differ slightly between validators (by a few milliseconds), but this difference is lost due to rounding.

Approach	T.R.	Av.R.	Val.	T.V.	Av.V.	Succ. (%)
Rewrit.	0.44h	1.26s	Isaitb	0.78h	2.25s	1254	(100.0%)
			Jena	0.47h	1.36s	1254	(100.0%)
			TopBraid	0.54h	1.54s	1254	(100.0%)
HermiT	15.4h	44.3s	Isaitb	0.69h	1.97s	1254	(100.0%)
			Jena	0.47h	1.36s	1254	(100.0%)
			pySHACL	0.28h	0.81s	1254	(100.0%)

Table 5: Results per approach and validator, restricted to instances solved by every approach excluding JFact for the baseline method and pySHACL for rewriting.

Approach	Min.	Med.	Max.	Validator	Min.	Med.	Max.
Rewrit.	0.18s	0.62s	6.80s	Isaitb	1.75s	2.02s	4.92s
				Jena	0.93s	1.17s	3.61s
				TopBraid	1.14s	1.32s	4.38s
HermiT	0.47s	2.22s	511.6s	Isaitb	1.78s	1.92s	7.84s
				Jena	0.92s	1.03s	317.8s
				pySHACL	0.29s	0.39s	270.3s

Table 6: Minimum, median, and maximum reasoning/rewriting and validation time per approach and validator, restricted to the same instance set as Table 5 (solved by every approach, excluding JFact for the baseline method and pySHACL for rewriting), computed over successfully completed instances only.

Knowledge Representation

Knowledge representation studies how to encode facts, concepts, rules, context, and uncertainty so machines can interpret and reason over them.

See all 128 papers

Static Analysis of Recursive SHACL
May 4, 2026Anouk Oudshoorn, Magdalena Ortiz, Mantas SimkusFormal Verification
Institute of Logic and Computation, TU Wien
NL2SHACL-Bench: A Benchmark Suite for Natural Language to SHACL Translation
Jul 24, 2026Yuchen Zhou, Niels Bobet, Maribel AcostaLLM Evaluation Knowledge Graphs
Technical University of Munich, Munich, Germany
Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
Jul 30, 2026Bente Gortworst, Cem Okulmus, Magdalena Ortiz +1Knowledge Representation Knowledge Graphs
TU Wien, Vienna, Austria · Paderborn University, Paderborn, Germany

May 4, 2026J/K move · Enter open · S save

Static Analysis of Recursive SHACL

Anouk Oudshoorn, Magdalena Ortiz, Mantas Simkus

Institute of Logic and Computation, TU Wien

Formal Verification

Open paper AskPDF arXiv

SHACL (Shapes Constraint Language) expresses constraints on RDF data by means of so-called shapes. Its central service is validation: verifying whether a data graph complies with a SHACL document. But so far, there are no static analysis services to compare documents. In this paper, we study the following problem: decide whether all graphs that validate one SHACL document also validate another. Unlike previous works that have considered the implication of shape expressions only, we consider documents comprising (recursive) shape definitions and targets. We show that implication (a.k.a. containment) is undecidable under the supported and the stable model semantics, even for the fragment that uses the description logic ALCIO for shape expressions. Under the well-founded semantics, in surprising contrast, it is decidable in single exponential time. Our key technical contribution is a translation of SHACL under the well-founded semantics into the full hybrid mu-calculus, revealing a novel link between well-founded models and a fixed point modal logic, and a worst-case optimal automata-based decision procedure.

Abstract

Knowledge Representation

Explore similar work

Static Analysis of Recursive SHACL

NL2SHACL-Bench: A Benchmark Suite for Natural Language to SHACL Translation

Shapes from Examples: Foundations of Shape Learning in Recursive SHACL