Paper deep dive
Rewrite Once, Validate Anywhere: Producing OWL-Aware SHACL Constraints (Extended Version)
Anouk Oudshoorn, Piotr Gorczyca, Dörthe Arndt
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/17/2026, 5:03:06 AM
Summary
The paper introduces ShacOWL, a tool that rewrites SHACL constraints based on OWL EL- ontologies to enable ontology-aware validation without requiring built-in reasoning support in validators. This approach internalizes OWL axioms into SHACL shapes, allowing any standard SHACL validator to detect violations that would otherwise require a separate reasoning step, resulting in improved efficiency and simplified maintenance.
Entities (10)
Relation Signals (10)
ShacOWL → implements → SHACL to OWL EL- rewriting
confidence 95% · we present ShacOWL, a tool which rewrites SHACL shapes based on OWL ontologies to enable ontology-aware validation.
OWL EL- → isfragmentof → OWL EL-
confidence 95% · OWL EL-, a fragment of OWL EL restricting the usage of existential restrictions
ShacOWL → supports → OWL EL-
confidence 95% · we construct a rewriting which takes as input both shapes and an OWL EL- ontology
SHACL → usedfor → RDF validation
confidence 95% · The Shapes Constraint Language (SHACL) is a W3C recommendation to express syntactic constraints, called shapes, on RDF graphs.
Dörthe Arndt → affiliatedwith → TU Dresden
confidence 90% · Dörthe Arndt... Affiliation: Computational Logic Group, TU Dresden, Germany
Anouk Oudshoorn → affiliatedwith → TU Wien
confidence 90% · Anouk Oudshoorn Affiliation: Institute of Logic and Computation, TU Wien, Austria
Piotr Gorczyca → affiliatedwith → TU Dresden
confidence 90% · Piotr Gorczyca Affiliation: Computational Logic Group, TU Dresden, Germany
ShacOWL → developedby → Piotr Gorczyca
confidence 90% · Piotr Gorczyca... we present ShacOWL
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.14104v1
- Canonical: https://arxiv.org/abs/2608.14104v1
Trouble viewing inline? Open PDF directly →
Full Text
85,474 characters extracted from source content.
Expand or collapse full text
Rewrite Once, Validate Anywhere: Producing OWL-Aware SHACL Constraints (Extended Version) Anouk Oudshoorn Affiliation: Institute of Logic and Computation, TU Wien, Austria Piotr Gorczyca Affiliation: Computational Logic Group, TU Dresden, Germany Dörthe Arndt E-mail piotr.gorczyca,doerthe.arndt@tu-dresden.de Affiliation: Computational Logic Group, TU Dresden, Germany Affiliation: ScaDS.AI, Dresden/Leipzig, Germany , E-mail anouk.oudshoorn@tuwien.ac.at 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. Keywords: SHACL validation OWL reasoning Rewriting 1 Introduction The W3C recommendation SHACL [21] makes it possible to specify syntactic constraints on RDF graphs, which may be checked for compliance. However, RDF graphs are not only syntactical constructs but also semantic statements. That is, they use OWL DL ontologies [6] to define classes and predicates; they come with implicit knowledge. According to the specification, SHACL implementations only need to support subclass reasoning, all other reasoning support is optional [21, Section 1.5]. As a result, the SHACL validation landscape is diverse. Many systems only take the required subclass reasoning into account when performing constraint validation (e.g. Jena [3], TopBraid [22], and Isaitb [16]), while others support OWL DL profiles (e.g., pySHACL [35]). The tasks of complex reasoning and validation are thus often executed by two independent systems, which creates a technical overhead. OWL reasoners are furthermore not always well maintained [1, 24] and not all reasoning results are relevant for validation. Ke et al. [18] address the latter problem in their paper. They carefully consider which facts need to be materialised and combine this with a slight rewriting. They present an efficient way to perform SHACL validation in presence of OWL LD [11]. However, their approach requires two distinct steps for each data graph: first the RE-SHACL system needs to be run, followed by a standard SHACL validator. We consider another ontology language that is not contained in OWL LD and aim to go another route; we propose a data independent rewriting. Based solely on the ontology axioms and shapes graph, we produce a new shapes graph. This shapes graph can then be applied to any input data graph with any SHACL validator. This is illustrated by the following example. We show a constraint which makes sure that every person has at least one name.11 1 We omit the prefix declarations for brevity. ⬇ 1 :PersonShape 2 a sh:NodeShape ; 3 sh:targetClass :Person ; 4 sh:property [ 5 sh:path :name ; 6 sh:minCount 1 ; 7 ] . Moreover, we know that every student is a person, :Student rdfs:subClassOf :Person.. Here, we can add a target declaration :PersonShape sh:targetClass :Student. to make sure that the shape :PersonShape also targets all instances of the class :Student. This does not only work for targets but also for constraints. If the ontology, for example, contains a subproperty :studentName rdfs:subPropertyOf :name., we can replace the IRI :name (line 5) by [ sh:alternativePath (:name :studentName) ], and ask for a name or a student name instead. The idea is thus that all constraint violations that could be found by first performing ontology reasoning and then executing constraint checking can also be found by only performing constraint checking using the rewritten shapes. The advantage of this approach is that the results become independent of the reasoning a SHACL validator supports and are therefore well-suited to be shared through the Web. In practical set-ups with fixed ontologies and shapes, but varying data graphs, only one system, the SHACL validator, needs to be maintained. Note that the idea behind this form of rewriting differs from classical rewriting of SPARQL [14] queries based on OWL-QL [23] as first proposed by Poggi et al. [32] and realised in many applications [37]. When we rewrite SPARQL based on OWL QL axioms, we modify one single existing query. This does not allow for any recursion beyond SPARQL’s property paths. A SHACL graph consists of several shapes which may depend on each other and while recursion between different shapes is not yet part of the standard, this extension is planned for the next version [8]. The SHACL working group furthermore plans to add rule support [9] to the specification. Engines supporting this feature will naturally be able to cope with RL using the corresponding rules [23, Section 4.3]. Being expressible in Datalog, these rules could alternatively be directly incorporated into SHACL shapes using the rewriting Pareti et al. provided [31]. We therefore do not focus on the RL fragment here. There have been different contributions to ontology-based SHACL rewriting: Savkovic et al. provide a rewriting of positive SHACL constraints based on OWL QL axioms [33]. This got extended in Ahmetaj et al. [2] to a rewriting for OWL QL and SHACL constraints with a restricted form of negation and recursion. However, their algorithm is best-case exponential and can thus not be used in practice. Oudshoorn et al. extended the former for the description logics ℰℒℋℐELHI [30] and Horn-ℒℋℐALCHIQ [29], which both subsume OWL QL. They present a rewriting procedure for ℰℒℋℐELHI that is no longer best-case exponential (only worst-case, but given their ExpTime-completeness results, this is inevitable) and thereby provide a first step towards an implementation. However, all of these contributions stayed on a theoretical level. If we broaden our horizon beyond SHACL, there are more approaches [10, 19, 25, 26] which discuss the theory of integrating constraints and implicit knowledge or OWL. In this paper we make the step from theory to practice: we present ShacOWL, a tool which rewrites SHACL shapes based on OWL ontologies to enable ontology-aware validation. We extend the existing theory by considering nominals, role chains and qualified existential restrictions on the left-hand side of the ontology axioms. However, we limit the usage of existential restrictions on the right-hand side as these are known to be the main reason for the exponential blow-ups [2, 30]. The resulting fragment OWL EL- still supports non-trivial axioms and is expressive enough to be used in practical applications [13]. Identifying this fragment for which we can extract an implementable algorithm, compared to the theoretically heavy rewriting techniques presented in related work (that are best case exponential size), is our first contribution. Our second contribution is to adapt existing rewriting techniques to our setting. In particular, we describe a new approach for rewriting targets as well. We provide an implementation, and perform an extensive evaluation using different OWL reasoners and SHACL validators. We compare the execution times between two approaches: (1) we rewrite the shapes based on the ontology and then validate the data graph against the rewritten shapes graph, (2) we reason on the data graph using the ontology and then validate the result against the original shapes graph. The pure validation times are similar in both approaches. This backs up our claim that rewritten shapes can be shared and used in practical applications. Links to the implementation source code and benchmarks are provided in the supplementary material statement before the references. 2 Preliminaries Before getting to the body of this paper, we define the following notions. Data Graphs. Let NC,NRN_C,N_R and NIN_I denote countably infinite, mutually disjoint sets of concept names (also known as class names), role names (or, property names), and individuals (or, constants), respectively. We assume ⊤,⊥⊆NC\ , \ N_C. Let NR¯:=p,p−∣p∈NR N_R:=\p,p^- p∈ N_R\ denote the set of roles. In general, we will write p∈NRp∈ N_R and r∈NR¯r∈ N_R, to denote the distinction. For every p∈NRp∈ N_R, let (p−)−=p(p^-)^-=p. An atom (or, assertion) is an expression of the form A(c)A(c) or p(c,c′)p(c,c ), for A∈NCA∈ N_C, p∈NRp∈ N_R and c,c′⊆NI\c,c \ N_I. A data graph A is a finite set of atoms. An interpretation is a pair ℐ=(Δℐ,⋅ℐ)I=( ^I,·^I), where Δℐ ^I is a non-empty set, called the domain, and ⋅ℐ·^I is a function that maps every A∈NCA∈ N_C to a set Aℐ⊆ΔℐA^I ^I, every p∈NRp∈ N_R to a binary relation pℐ⊆Δℐ×Δℐp^I ^I× ^I, and every individual c∈NIc∈ N_I to an element cℐ∈Δℐc^I∈ ^I. Let (p−)ℐ:=(c′,c)∣(c,c′)∈pℐ(p^-)^I:=\(c ,c) (c,c )∈ p^I\. The canonical interpretation ℐI_A of a data graph A is defined by letting Δℐ ^I_A contain all individuals occurring in A, and setting cℐ:=c^I_A:=c for each c∈NIc∈ N_I, Aℐ:=c∣A(c)∈A^I_A:=\c A(c) \ for each A∈NCA∈ N_C and rℐ:=(c,c′)∣r(c,c′)∈r^I_A:=\(c,c ) r(c,c ) \ for all r∈NR¯r∈ N_R. We make the standard name assumption, which means cℐ=c^I=c for all interpretations ℐI, and all c∈NIc∈ N_I. Note that this enforces a unique name assumption too. (Non-recursive) SHACL. Let NSN_S be an infinite set of shape names s. Based on the work of Corman et al. [7], we say a (SHACL) constraint s←φs← is formed from a shape name s∈NSs∈ N_S and a shape expression φ , defined in the following way φ::=c∣s∣A∣¬φ∣φ⊓φ∣≥nE.φ∣E=E′∣E≠E′, ::=c s A \; _n\!E. E=E E =E , where c∈NIc∈ N_I, s∈NSs∈ N_S, A∈NCA∈ N_C, n≥1n≥ 1, p∈NRp∈ N_R and E and E′E regular path expressions, i.e., regular expressions over the language NR¯ N_R, defined as E::=r|E∪E∣E⋅E∣E∗. E::=r E∪ E E· E E^*. We use ∀E.φ∀ E. as a shorthand for ¬≥1E.¬φ \!\! _1\!\!E. , and φ⊔φ′ for ¬(¬φ⊓¬φ′) ( ). Note that a similar trick does not work for E=E′E=E and E≠E′E =E , as sets of atoms being equal or completely disjoined cannot be simply expressed in terms of each other by using negation. Let LEL_E be the language defined by some regular expression E, containing words w∈Σ∗w∈ ^*, inductively defined as Lr:=rL_r:=\r\, LE∪E′:=LE∪LE′L_E∪ E :=L_E∪ L_E , LE⋅E′:=w⋅w′∈Σ∗∣w∈LE,w′∈LE′L_E· E :=\w· w ∈ ^* w∈ L_E,w ∈ L_E \, and LE∗:=w∗∈Σ∗∣w∈LEL_E^*:=\w^*∈ ^* w∈ L_E\. We say E is a regular path expression, when Σ=NR¯ = N_R. The semantics of regular path expressions is given in terms of the evaluation EℐE^I over an interpretation ℐI, which is defined as follows. A pair (e,e′)(e,e ) is contained in EℐE^I iff there exists r0⋯rn∈LEr_0·s r_n∈ L_E and e1,…en⊆Δℐ\e_1,… e_n\ ^I such that (e,e1)∈r0ℐ(e,e_1)∈ r_0^I, (en,e′)∈rnℐ(e_n,e )∈ r_n^I and for all 1≤i≤n−11≤ i≤ n-1, (ei,ei+1)∈riℐ(e_i,e_i+1)∈ r_i^I. A constraint set C is a set of SHACL constraints such that for each s∈NSs∈ N_S, there exists at most one s←φ∈s← , and such that there are no cyclic dependencies. The semantics of SHACL is defined in a recursive manner by the function ℐ(⋅)I(·), given in Figure 1. ℐ(c) (c) :=cℐ :=\c^I\ ℐ(s) (s) :=e∈φℐ∣s←φ∈ :=\e∈ ^I s← \ ℐ(A) (A) :=Aℐ :=A^I ℐ(¬φ) ( ) :=Δℐ∖ℐ(φ) := ^I ( ) ℐ(φ⊓φ′) ( ) :=ℐ(φ)∩ℐ(φ′) :=I( ) ( ) ℐ(∃≥nE.φ) ( _≥ nE. ) :=e∈Δℐ∣|e′∈Δℐ∣(e,e′)∈Eℐ∧e′∈ℐ(φ)|≥n :=\e∈ ^I |\e ∈ ^I (e,e )∈ E^I e ( )\|≥ n\ ℐ(E=E′) (E=E ) :=e∈Δℐ∣∃e′∈Δℐ∣(e,e′)∈Eℐ=e′∈Δℐ∣(e,e′)∈E′ℐ :=\e∈ ^I \∃ e ∈ ^I (e,e )∈ E^I\=\e ∈ ^I (e,e )∈ E \\ ℐ(E≠E′) (E =E ) :=e∈Δℐ∣∃e′∈Δℐ∣(e,e′)∈Eℐ∩e′∈Δℐ∣(e,e′)∈E′ℐ=∅ :=\e∈ ^I \∃ e ∈ ^I (e,e )∈ E^I\∩\e ∈ ^I (e,e )∈ E \= \ Figure 1: Evaluating shape expressions Given an interpretation ℐI and a shape assignment S, we say a node c∈NIc∈ N_I validates a shape expression φ , when c∈ℐ(φ)c ( ). Furthermore, let G be a set of targets of the form s(X)s(X), for X::=c∣A∣∃r.⊤X ::=c A ∃ r. where c∈NIc∈ N_I, A∈NCA∈ N_C and r∈NR¯r∈ N_R. A pair (,)(C,G) consisting of a constraint set and set of targets is called a shapes graph. Given an interpretation ℐI, we say ℐI validates (,)(C,G) if for all s(c)∈s(c) , we find c validates s, and for all s(X)∈s(X) , all nodes in XℐX^I validate s. Considering readability, we will write A validates (,)(C,G), for any set of atoms A, in which case the canonical interpretation ℐI_A is intended. 3 Ontology Language OWL EL- For the ontology axioms, we introduce the language OWL EL-, a fragment of OWL EL. This logic corresponds to the description logic ℰℒ++EL^++ [4, 5], but is disallowing the usage of existential restrictions on the right-hand side. An example of an ontology expressible in this fragment in the Riskman ontology [13]. Let an OWL EL- TBox T be a set of axioms of the form r⊑pr p, for r∈p′,p′∘p∣p′∈NRr∈\p ,p p p ∈ N_R\, or C⊑BC B, where C::=⊤∣A∣c∣(p)∣C⊓C∣∃p.C C ::= A c (p) C C ∃ p.C where A,B⊆NC\A,B\ N_C, c∈NIc∈ N_I and p,p′⊆NR\p,p \ N_R. Furthermore, we use (p)dom(p) as a shorthand for ∃p.⊤∃ p. . Any expression that may occur on the left-hand side of an OWL EL- axiom is referred to as an OWL EL- concept. Note that, to avoid intractability of this logic, we reduced the syntax of axioms of the form p′∘p⊑p′p p p to p∘p⊑p p p. This is a slightly weaker form of the syntactic restriction proposed by Baader et al. [5], which ensures tractability. Note that transitivity axioms may still be expressed using the form p∘p⊑p p p. The semantics of OWL EL- is, as is usual, defined in terms of interpretations ℐI: an axiom C⊑DC D is satisfied whenever Cℐ⊆DℐC^I D^I. To this end, the interpretation function is extended in the following way: ⊤ℐ:=Δℐ ^I:= ^I, (C⊓C′)ℐ:=Cℐ∩C′ℐ(C C )^I:=C^I∩ C , (∃p.C)ℐ:=c∣(c,c′)∈pℐ∧c′∈Cℐ(∃ p.C)^I:=\c (c,c )∈ p^I c ∈ C^I\, ((p))ℐ:=c∣(c′,c)∈pℐ(ran(p))^I:=\c (c ,c)∈ p^I\, and (p′∘p)ℐ:=(c,c′)∣(c,d)∈p′ℐ,(d,c′)∈pℐ(p p)^I:=\(c,c ) (c,d)∈ p ,(d,c )∈ p^I\. In case all axioms in T are satisfied in ℐI, we say ℐI is a model of T. As is standard, we define subformulas in the following recursive way: ():=(X),sub(B)∣X⊑B∈sub(T):=\sub(X),sub(B) X B \, and (C⊓C′):=C⊓C′,(C),sub(C′)sub(C C ):=\C C ,sub(C),sub(C )\, (∃p.C):=∃p.C,(C)sub(∃ p.C):=\∃ p.C,sub(C)\ and (Y):=Ysub(Y):=\Y\ for Y∈NC∪NI∪⊤,(p)∣p∈NRY∈ N_C∪ N_I∪\ ,ran(p) p∈ N_R\. Syntactic Restrictions. To ensure that counting to at least two on complex path expressions is restricted to simple roles, we assume the following restriction on C and T to be honoured: if ≥np.φ _n\!p. appears somewhere in C, there do not exist p′∘p⊑p∈p p p or p′⊑p∈p p . Moreover, in the rewriting itself we are considering acyclic TBoxes: for each T, we assume that there exists no C1⊑D1,…,Cn⊑Dn⊆\C_1 D_1,…,C_n D_n\ such that for each pair DiD_i and Ci+1C_i+1, and the pair Dn,C1D_n,C_1, there is a concept or role name in the intersection of the syntax of the pair. We note that both cyclic TBoxes as recursive SHACL do not break our theory, nor the correctness of our rewriting. However, to capture the cyclicity, we would produce (stratified) recursive SHACL constraints, that would need to be interpreted under a least fixed point semantics.22 2 Note that the stable-model and well-founded semantics would also suffice, as they coincide with the least fixed point semantics for stratified constraints. To the best of our knowledge, the only (proof-of-concept) implementation that handles recursion in a principled way is shaWell [28]. That is, to allow for a more extensive evaluation, we stick to non-recursive SHACL and acylic TBoxes in this paper. 4 Combining SHACL and OWL We aim to provide a feasible method to combine OWL reasoning and SHACL validation in practical applications. To this end, we first need to clarify which semantics we consider. Several papers investigated the theory of this combination [2, 30, 29, 33], and all of them have in common that SHACL constraints are evaluated over some minimised canonical model of the original data graph and OWL constraints. These papers mention multiple ways to define such a minimal model: minimisation after Skolemisation, or using the core operation on any universal model. As we disallow existential restrictions on the right hand side of an axiom, we do not face the problem these definitions aim to solve: for all new information we possibly derive using axioms, we always know which individuals are affected. Building a unique universal model that is minimal is thus straightforward. Definition 1 Given a set of OWL EL- axioms T and a data graph A, let A_T be the smallest set such that ⊆A _T and moreover: • for each C⊑B∈C B , for C an OWL EL- concept if c∈Cℐc∈ C^I, then B(c)∈B(c) _T; • for each r⊑p∈r p , for r∈p′,p′∘p∣p′∈NRr∈\p ,p p p ∈ N_R\, if (c,c′)∈rℐ(c,c )∈ r^I, then p(c,c′)∈p(c,c ) _T, where ℐI is a shorthand for ℐI_A_T. The following is immediate. Proposition 1 Given a set of OWL EL- axioms T and a data graph A, we find that the canonical interpretation of A_T is a model of (,)(T,A). Moreover, there does not exist a smaller model of (,)(T,A): for each model J of (,)(T,A), we find that Aℐ⊆A^I A^J and pℐ⊆p^I p^J, for all A∈NCA∈ N_C and p∈NRp∈ N_R. This brings us to the semantics of SHACL in presence of OWL EL- axioms. Definition 2 Given a data graph A, a set of OWL EL- axioms T and a shapes graph (,)(C,G). We say (,)(T,A) validates (,)(C,G) whenever A_T validates (,)(C,G). The rest of this paper focuses on how we can replace this two-stage method by a more direct one. We want to build a set of SHACL constraints, based on a shapes graph (,)(C,G) and a set of axioms T, that can directly be validated against any data graph. We will show the following: Theorem 4.1 Given a shapes graph (,)(C,G) and an OWL EL- TBox T, there exists a shapes graph (,)(C_T,G_T) such that for every data graph A, validates (,) iff validates (,).A_T validates (C,G) iff A validates (C_T,G_T). The main advantage of updating the shapes graph in this way is that for every data graph, and every update of any of these data graphs, it suffices to use (,)(C_T,G_T) – which only needs to be computed once – when testing validation. The rewriting approach consists of two key phases: • constraint rewriting – integration of the axioms in T into the input constraints C. • target rewriting – using the constraint rewriting, fine-tuning targeting such that also targets implied by T are addressed. To understand the distinction between the two aspects, consider the following example. Example 1 Let =∃p.A⊑B,p⊑qT= \∃ p.A B,p q \, =A(b),p(a,b)A= \A(b),p(a,b) \, =s←∃q.⊤C= \s←∃ q. \, =s(B)G= \s(B) \ be the sets of ontology axioms, assertions, shapes and targets, respectively. In this set-up, we get =∪B(a),q(a,b)A_T=A∪ \B(a),q(a,b) \. First, we want to internalise in the shapes graph that nodes like a conforming to ∃p.A∃ p.A should also be considered a target for s. This part is addressed in the target rewriting. Second, since q(a,b)∈∖q(a,b) _T , we would like to update the constraint set to s←∃(p∪q).⊤s←∃(p∪ q). , such that we may indeed conclude that a validates s. In the following section, we go into more detail of these rewriting techniques. 5 Rewriting Techniques The main idea of the rewriting is to capture all reasoning of the axioms in SHACL constraints. The most direct translation of the axioms can be found in the ℎ(X,)shape(X,T)-part: here, it is ensured that if a node is labelled with sCs_C for some concept C, then C must be derivable by T for that specific node. That is, let ℎ(X,)shape(X,T) be defined as ℎ(X,) (X,T) :=sa←aif X=as∃p.C←∃p.sCif X=∃p.Cs∃p.⊤←∃p.⊤if X=(p)s∃p−.⊤←∃p−.⊤if X=(p)sC1⊓…⊓Cn←sC1⊓…⊓sCnif X=C1⊓…⊓CnsB←Bif X=B,B∈NC⊔⨆p|(r)⊑B∈s∃p−.⊤⊔⨆p|(r)⊑B∈s∃p.⊤⊔⨆C|C⊑B∈sC := casess_a← a&if X=a\\ s_∃ p.C←∃ p.s_C&if X=∃ p.C\\ s_∃ p. ←∃ p. &if X=dom(p)\\ s_∃ p^-. ←∃ p^-. &if X=ran(p)\\ s_C_1 … C_n← s_C_1 … s_C_n&if X=C_1 … C_n\\ s_B← B&if X=B,B∈ N_C\\[-4.0pt] s_B←\;\; \; _ \p\ |\ ran(r) B \s_∃ p^-. \\ s_B←\;\; \; _ \p\ |\ dom(r) B \s_∃ p. \\ s_B←\;\; \; _ \C\ |\ C B \s_C cases A standard argument based on the induction on the construction of C suffices to conclude the following. Lemma 1 Given an OWL EL- TBox T, let :=⋃X∈()ℎ(X,)C:= _X (T)shape(X,T), then for all C∈()C (T) and c∈NIc∈ N_I, we have c∈ℐ(sC)c _A(s_C) iff c∈Cℐc∈ C^I_A_T. This is then used in multiple ways. First of all, to update the targets of shapes according to T, we use the so-called bridge-shapes: if s(X)∈s(X) , we add s⨝←¬sX⊔s ← s_X s, for s⨝s a fresh shape name that universally targets all nodes but constrains only those satisfying X, ensured by an implication encoded as a disjunction. In practice, we use the class, property, and individual declarations to perform the universal targeting.33 3 Note that tools like for example Protegé [27] automatically add such declarations. If the ontology contains, e.g., a triple :r a owl:ObjectProperty., we add target declarations for subjects and objects of :r using sh:targetSubjectOf and sh:targetObjectOf. We then filter out the nodes which can be labelled by sXs_X. For those nodes, we ensure that s is validated, as is required. Thus, let the set of targets be updated to _T =∪s⨝(⊤)|s(X)∈. =G∪ \s ( )\ |\ s(X) \. Next, to take care about the role inclusions, we first collect the relevant role dependencies. Here, → _role and →ℎ _chains are two relation given by p′→p _rolep iff p′⊑p∈p p , respectively p′→ℎp _chainsp iff p′∘p⊑p∈p p p . With ∗* and ++ we denote the reflexive-transitive and transitive closure of relations. That is, let (,p) (T,p) :=p′|p′→∗p := \p \ |\ p _role^*p \ (,p) (T,p) :=p′|p′→ℎ+p := \p \ |\ p →^+_chainsp \ Σ(,p) (T,p) :=⋃t∈(,p)(,t)if p∘p⊑p∈⋃t∈(,p)(,t)∖potherwise. := cases _t\,∈\,Dep(T,p)Base(T,t)&if p p p \\ _t\,∈\,Dep(T,p)Base(T,t) \p \&otherwise. cases With these dependencies defined, we can now provide the expressions that will be substituted for occurrences of p respectively p−p^-. L+(,p) L^+(T,p) :=(p1∪⋯∪pk)∗⋅(p1′∪⋯∪pn′) :=(p_1∪·s∪ p_k)^*·(p _1∪·s∪ p _n) L−(,p) L^-(T,p) :=(p1′−∪⋯∪pn′−)⋅(p1−∪⋯∪pk−)∗ :=(p -_1∪·s∪ p -_n)·(p^-_1∪·s∪ p^-_k)^* Here, p1,…,pk=Σ(,p)\p_1,…,p_k\= (T,p) and p1′,…,pn′=(,p)\p_1 ,…,p_n \=Base(T,p). To illustrate these auxiliary definitions for roles consider the following example. Example 2 Let p0⊑p1,p1∘p3⊑p3,p2⊑p3⊆ \p_0 p_1,p_1 p_3 p_3,p_2 p_3 \ , and p3p_3 and p3−p_3^- appearing in shapes. Then (,p3)=p2,p3Base(T,p_3)= \p_2,p_3 \, (,p3)=p1Dep(T,p_3)= \p_1 \, Σ(,p3)=p0,p1 (T,p_3)= \p_0,p_1 \, and p3p_3 will be substituted by (p0∪p1)∗⋅(p2∪p3)(p_0∪ p_1)^*·(p_2∪ p_3), whereas p3−p_3^- by (p2−∪p3−)⋅(p0−∪p1−)∗(p_2^-∪ p_3^-)·(p_0^-∪ p_1^-)^*. Since p3∘p3⊑p3∉p_3 p_3 p_3 , p3p_3 is excluded from Σ(,p3) (T,p_3) to prevent admitting repeated p3p_3-steps in the prefix; had p3p_3 been transitive, the path would expand to (p0∪p1∪p3)∗⋅(p2∪p3)(p_0∪ p_1∪ p_3)^*·(p_2∪ p_3) instead. In the rewriting we need to substitute certain roles or concept names by fresh objects, that is, let φ[x↦y(x)]x∈X [x y(x) ]_x∈ X and [x↦y(x)]x∈XC [x y(x) ]_x∈ X be the notation indicating that for each x∈Xx∈ X, every occurrence of x in φ resp. C is replaced by y(x)y(x), where for all p∈NRp∈ N_R, we consider p−p^- a symbol in itself, not containing p. Lemma 2 Let T be any OWL EL- TBox only containing axioms of the form r⊑pr p, and φ any shape expression, then we find that for each data graph A, we have c∈ℐ(φ)c _A_T( ) iff c∈ℐ(φ[p↦L+(,p),p−↦L−(,p)]p∈NR)c _A( [\,p L^+(T,p),\;p^- L^-(T,p)\, ]_p\,∈\,N_R) for all c∈NIc∈ N_I. The main idea why this substitution suffices is that for every axiom of the form p⊑p′p p , p′p is replaced by p∪p′p∪ p , whereas for axioms of the form p∘p′⊑p′p p p , p′p is replaced by p∗⋅p′p^*· p . The sets Σ(,p) (T,p) and (,p)Base(T,p) solely collect the whole set of dependent p’s, and do the replacements simultaneously to avoid termination issues. For the inverse substitution, dictated by L−L^-, exactly the same is happening, but in reverse. For the constraint rewriting, the main idea is to substitute all concept names B appearing in the constraint set C by the shape name sBs_B, which, as mentioned before, collects exactly all nodes for which B can be derived in T. That is, the final rewritten set of shapes, C_T is given by ℎ(,,) (T,C,G) :=[B↦SB]B∈NC∪s⨝←¬sX⊔s|s(X)∈ :=C [\,B S_B\, ]_B\,∈\,N_C∪ \s ← s_X s\ |\ s(X) \ ∪ℎ(X,)|X∈()∪X∣s(X)∈ :=C_norm\;∪ \shape(X,T)\ |\ X (T)∪\X s(X) \ _T :=ℎ(,,)[p↦L+(,p),p−↦L−(,p)]p∈NR. :=allShapes(T,C,G) [\,p L^+(T,p),\;p^- L^-(T,p)\, ]_p\,∈\,N_R. In a concrete setting, this produces the following constraints. Example 3 Consider the following TBox and shapes graph =A⊑B,∃p.B⊑C,(p)⊑A,(p)⊑B,p0⊑p,p1∘p⊑p,p0⊑p1 = \A B,\ ∃ p.B C,\ dom(p) A,\ ran(p) B,\ p_0 p,\ p_1 p p,\ p_0 p_1 \ =s1←∃p.B,s2←∃p−.A=s1(A),s2(∃p−.⊤), = \s_1←∃ p.B, s_2←∃ p^-.A \ = \s_1(A), s_2(∃ p^-. ) \, following the rewriting as described above, this produces the following rewritten shapes graph _T =s1←∃((p0∪p1)∗⋅(p0∪p)).sB,s2←∃((p0−∪p−)⋅(p0−∪p1−)∗).sAsA←A⊔s∃p.⊤,sB←B⊔sA⊔s∃p−.⊤,sC←C⊔s∃p.Bs∃p.⊤←∃((p0∪p1)∗⋅(p0∪p)).⊤s∃p−.⊤←∃((p0−∪p−)⋅(p0−∪p1−)∗).⊤s∃p.B←∃((p0∪p1)∗⋅(p0∪p)).sBs1⨝←¬sA⊔s1,s2⨝←¬s∃p−.⊤⊔s2 = \ array[]ls_1←∃ ((p_0∪ p_1)^*·(p_0∪ p) ).s_B, s_2←∃ ((p_0^-∪ p^-)·(p_0^-∪ p_1^-)^* ).s_A\\[4.0pt] s_A← A s_∃ p. , s_B← B s_A s_∃ p^-. , s_C← C s_∃ p.B\\[4.0pt] s_∃ p. ←∃ ((p_0∪ p_1)^*·(p_0∪ p) ). \\ s_∃ p^-. ←∃ ((p_0^-∪ p^-)·(p_0^-∪ p_1^-)^* ). \\ s_∃ p.B←∃ ((p_0∪ p_1)^*·(p_0∪ p) ).s_B\\[4.0pt] s_1 ← s_A s_1, s_2 ← s_∃ p^-. s_2 array \ _T =∪s1⨝(⊤),s2⨝(⊤). =G∪ \s_1 ( ), s_2 ( ) \. Proof of Theorem 1 The correctness of our rewriting follows from combining the intuitions of Lemmata 1 and 2 with the idea that for each s←φ∈s← , with s(X)∈s(X) , we find that for all c∈Xℐc∈ X^I_A_T that c validates s⨝s in A_T iff c validates s in A_T, and for all c∉Xℐc ∈ X^I_A_T, c validates s⨝s in A_T anyway, independent of whether c validates s in A_T or not. ∎ Note that our rewriting is data independent, which means that in size of the data graph, the size of our rewriting is a constant. In size of the in general much smaller TBox, the amount of newly introduced shapes is linear. The size of rewritten constraints itself is also limited: the only blow-up in size may be caused by replacing roles by a regular expression (which size only depends on the amount of role hierarchies in the TBox). 6 Implementation and Evaluation 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%) pySHACL 40 0.28h 0.81s 201 1259 (83.9%) TopBraid 1 0.49h 1.36s 200 1299 (86.6%) JFact 158.2h 379.7s Isaitb 0 0.32h 1.95s 902 598 (39.9%) Jena 1 0.17h 1.02s 902 597 (39.8%) pySHACL 1 0.06h 0.36s 901 598 (39.9%) TopBraid 0 0.20h 1.23s 902 598 (39.9%) Pellet 43.7h 105.0s Isaitb 0 0.72h 1.97s 185 1315 (87.7%) Jena 1 0.50h 1.38s 186 1313 (87.5%) pySHACL 47 0.21h 0.60s 186 1267 (84.5%) TopBraid 0 0.48h 1.31s 186 1314 (87.6%) pySHACL + OWL-RL 107 14.8h 38.3s 0 1393 (92.9%) + OWL-RL + RDFS 107 20.8h 53.7s 0 1393 (92.9%) 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. We implemented ShacOWL 44 4 Available at https://github.com/gorczyca/owl-aware-shacl, a JavaScript tool realising the rewriting shown in the previous section, using the rdflib.js library (v2.2.37) for RDF parsing, graph manipulation, and Turtle serialisation. Given an OWL EL- TBox T and SHACL shapes (,) (C,G ), it produces rewritten shapes (′,′) (C ,G ) that encode the terminological knowledge directly within the constraints, eliminating the need for a reasoner while providing the same validation results. To verify its correctness and evaluate its performance we designed and carried out a set of experiments and comparisons with related systems, that will be described in this section. Related Systems. ShacOWL offers an alternative to the baseline method, in which the datagraph is first materialised against the ontology, completing all the implicit class and role assertions. For the inference phase in the baseline method we used three OWL 2 reasoners: Pellet [34] (v2.4.0), HermiT [12] (v1.4.3.517), and JFact [36] (a Java port of FaCT++, v5.0.3), all integrated via the OWL API [15] (v5.1.20) through a custom JAR wrapper that returns all inferred class and object property assertions. We also considered ELK [17] (v0.6.0) and StructuralReasoner (the built-in OWL API reasoner), but excluded them as they do not support ABox completion through the OWL API, being primarily designed for other reasoning tasks such as classification. In the second phase, SHACL validation is carried out. For the ShacOWL approach this means verifying the initial datagraph against the rewritten constraints; for the baseline method it means validating the materialised datagraph against the original shapes. For validation we used four SHACL validators: Jena [3] (v4.10.0), TopBraid [22] (v1.4.3), Isaitb [16] (v1.10.0), and pySHACL [35] (v0.30.1). We additionally tested pySHACL’s built-in inference feature, which accepts an input ontology alongside the data and supports RDFS, OWL RL, or combined reasoning modes. Since OWL RL subsumes OWL EL-, we include this as a third evaluated approach. In summary, we evaluate the following approaches: • baseline: materialisation with an OWL reasoner followed by SHACL validation (3 reasoners × 4 validators = 12 combinations), • rewriting: rewriting with ShacOWL followed by SHACL validation (4 combinations, one per validator), • pySHACL with inference, using OWL RL or OWL RL+RDFS reasoning (2 combinations). Benchmarks and Experiments Setup. We generated 1500 benchmarks across 15 difficulty levels (100 per level), each consisting of an OWL EL- TBox, a set of SHACL shapes, and a data graph. Difficulty scales with ontology size and complexity, varying the number of classes, roles, GCIs, role chains, role inclusions, and shape complexity. All benchmarks are acyclic; while our algorithm would still terminate on cyclic GCIs yielding recursive rewritings, current SHACL validators do not support recursive shapes. We therefore restricted evaluation to non-recursive TBoxes – an assumption that can be dropped once such validators become available. Full pseudocodes of the generation algorithms, benchmark statistics, triple counts for benchmarks, rewritings and materialised data graphs as well as and Turtle encodings of the input and output from Example 3 are provided in the appendix. We note that due to the random generation process, the vast majority of instances are negative (i.e., the datagraph does not conform), with positive instances appearing almost exclusively at the lowest difficulty level. Approaches were given 1200s in total per each benchmark, split evenly between the reasoning/rewriting and validation phase, and pySHACL +inference approach was given full 1200s for its singular task. All experiments were run on an HPC cluster, with each job allocated 64 GB of memory. Results Analysis. The results of our experiments are presented in Figure 2 and Table 1. The first big column of the table displays the overall time (T.R) and the average time (Av.R.) of the rewriting process (first row) and of the reasoning performed by the different engines (rows 2–4). For all our test cases together the rewriting only took a little bit longer than one hour, while the fastest reasoner, Pellet, needed almost 44 hours to perform a materialisation. The reason for this difference partly lies in the complexity of the logics supported by the different systems and therefore has to be treated with some care: while our approach only supports the OWL EL- fragment, the reasoners we employed are OWL DL reasoners, which need to support more complex reasoning. As all ontologies in our benchmark fall under OWL EL-, we expect the results of the reasoners to be the same an OWL EL- reasoner, if it existed, would produce. The numbers however show that rewriting can be done in a short amount of time (2.53s on average). Note that the rewriting is furthermore independent of the data graph and only needs to be executed once for each combination of ontology and shapes, while in the reasoning set-up each new data graph requires a new reasoning run.55 5 If only one datagraph is updated, incremental reasoners could be used. In the second big column of the table, we collected the number of validation errors (V.E), the total time (T.V) and the average time (Av.V) per validation engine. Note, that the number of validation errors is significantly higher for pySHACL than for all other engines, in particular in combination with the rewriting. The reason is that the version of pySHACL we used only supports shapes with a depth of up to 30, that is, it does not allow deeply nested shapes.66 6 pySHACL allows the user to change the maximal depth for the shapes using the option --max-depth [35], but this feature was broken and only got fixed with version v0.40.0 https://github.com/RDFLib/pySHACL/issues/315. Such kind of nesting is rather unlikely to occur if shapes are created manually, but it is the expected output of our rewriting. If we take, for example, shape s1∈s_1 from Example 3, and compare it to its rewritten version s1∈s_1 _T, we see that the rewriting added a dependency on sBs_B which in turn depends on sAs_A and s∃r−.⊤s_∃ r^-. of which the former again depends on s∃r.⊤s_∃ r. . We thus create a chain of four dependent shapes from a single shape which had no connection to any other.77 7 Note that the example does not take SHACL’s property shapes into account as these are not represented as shapes in the logical representation. The turtle version of the translated shape can be found in the appendix. For the other validation engines the average times for the rewritten shapes are higher than the validation times of the original shape on the materialised graph. The main reason for that is that this number reflects the average of all successful validation runs. Especially for the more complex ontologies the materialisation performed by the reasoners often failed which make these numbers difficult to compare. The numbers for the cases which could successfully evaluated by (almost) all approaches can be found in the appendix. The last column of the table reflects the failures. We display the number of successful runs of (reasoning or rewriting)+validation run (Success) and the number of runs which resulted in a time out (T/O). Only the rewriting approach was successful in all cases. The timeouts for the other approaches were all caused by the reasoners which were not able to perform materialisation in less than 600s for complex ontologies. With JFact, we could only cover around 40% of the cases while the success rate of HermiT and Pellet is around 87%. In the last row of the table, we also display the reasoning and validation time for pySHACL enabled with entailment. With this approach, we could cover around 93% of all cases. In order to better compare all approaches to each other, we display a cactus plot in Figure 2. On the y-axis we count the number of test cases which were each solved in less than the amount of time displayed on the x-axis. The timings shown are the combined times for reasoning/rewriting and validation. We, observe that around 400 test cases could each be solved in 1 second or less with the reasoning+validation approach using Pellet and pySHACL (solid yellow line). This approach is the most successful for this short amount of time. However, for an execution time of 4s, the rewriting approach using TopBraid, Isaitb and Jena outperforms all other approaches and in less than 25s it solves all instances of the benchmark. We see that with the known exception of pySHACL, this result does not depend on the validator. This strengthens our claim that the rewritten shapes can be easily exchanged and used by different parties. 7 Discussion: towards OWL EL Before, we considered OWL EL-, a fragment of OWL EL in which existential restrictions on the right hand side of axioms are disallowed. In this section, we go over the ideas and challenges involved in converting our method into one for full OWL EL. The main issues to consider are handling the introduction of new edges to already existing nominals and the handling of the introduction of edges for which the object is not specified in the axiom. We will discuss them in this order. Existential restrictions to nominals. When encountering axioms of the form C⊑∃p.cC ∃ p.c, this means we have to simulate jumps from nodes in the extension of the concept C to the nominal c whenever p occurs in a shape expression. Consider for instance the constraint s←≥2p.φs← _2\!p. with target s(a)s(a). A possible way to rewrite this would be by using some kind of universal role u that connects every node to every other node: s←≥2p.φ⊔(≥1p.φ⊓C⊓¬≥1p.c⊓≥1u.(c∧φ)).s← _2\!p. ( _1\!p. C \! _1\!p.c\; _1\!u.(c )). However, such a universal role is in general not included in validators, meaning that we have to simulate the described setting in some way. Here, we may use that this is not a random jump through the data graph; each one of them is initiated by ontology axioms. That is, we may include the triple structure used to define the axiom C⊑∃p.cC ∃ p.c in the rewritten shape constraint:88 8 We omit prefixes for readability. the structure (a,C)type(a,C), (C,x)subclassOf(C,x), (x,y)someValuesFrom(x,y), (y,z)oneOf(y,z), (z,c)first(z,c) might be there, in which case, u=⋅u=type·subclassOf·someValuesFrom·oneOf·first will suffice. However, this gets more complicated if a being of type C is something that will need to be derived as well. Thus, we need to somehow move the validation process to the node c, but make it depend on the right conditions being met at the node a. Another way to achieve this would be to use Boolean combinations of targets: s(a)∨(s′(a)∧s′(c))s(a) (s (a) s (c)), where s←≥2p.φs← _2\!p. is the original constraint, and s′s and s′s are given as follows s′←≥1p.φ⊓C⊓¬≥1p.c s ← _1\!p. C \! _1\!p.c s′←φ. s ← . At the time of writing, there is a W3C working group developing SHACL 1.2 [20], an updated SHACL version, which among other things extends the targetting by so-called shape targets. These make it possible to target all nodes adhering to a specified shape, but they do not support boolean combinations of targets on different shapes as exemplified and needed above. That is, it remains unclear whether such an approach, although natural, will become supported in the near future. Existential restrictions. Considering unrestricted existential restrictions in the setting of combining SHACL with reasoning has been the topic of the works by Ahmetaj et al. and Oudshoorn et al. [2, 30, 29], although in fragments without nominals.99 9 Namely the description logics DL-LiteR (DL underlying OWL QL), ℰℒℋℐELHI and Horn-ℒℋℐALCHIQ. That is, rewriting techniques for SHACL and existential restrictions are known, but also known to be ExpTime-complete in combined complexity (data graph size plus ontology size), for relatively inexpressive ontologies like OWL QL already [2, 29]. The main reason for this exponential blow-up lays in having to consider every possible configuration that can appear in the data - which can only be resolved by considering which settings may actively appear in the data [30], at the cost of leaving the data independence behind. That is, it is not per se impossible to perform SHACL rewritings with unrestricted existential restrictions, but it requires care to obtain efficient rewritings. 8 Conclusion and Outlook In this work we presented the first step from the so far rather theoretical research around ontology aware shapes rewriting towards its practical application. We identified OWL EL- as an OWL EL fragment which is expressive enough to cover non trivial use cases [13] but which can still be incorporated into SHACL shapes with rather low effort. We detailed how the rewriting can be done and provided an implementation which can be reused in other work. We performed an evaluation and compared the rewriting approach to (1) the approach performing reasoning on a data graph to then validate the shapes on the resulting materialisation using different engines and (2) to a validator with built-in reasoning. We showed that the combination of rewriting and validation could solve all our test cases and was faster than the alternatives in most cases. Moreover, our rewritten shapes can be reused for new data graphs that come with the same ontology axioms and constraints further reducing validation times. Our evaluation also revealed a potential problem, namely that the rewritten shapes get rather complex. We do not expect users to directly modify these automatically generated files. However, depending on the engine, this complexity will also be visible in the validation reports. This will make reports harder to read, but allow users to better trace the cause for a violation. Future work will help to generate extracts from such complex reports optimised for the users’ needs. We furthermore want to extend our techniques to cover more expressive fragments of OWL EL by adding, for example, inverse roles. As our SHACL fragment already contains inverse roles, we expect that this generalisation could follow rather straightforwardly after a careful inspection of the described algorithms. Acknowledgements. The project leading to this application has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 101034440. Furthermore, this work was supported by funding from BMFTR within projects SEMECO (grant no. 03ZU1210B), KIMEDS (grant no. GW0552B), and MEDGE (grant no. 16ME0529). Supplemental Material Statement. The Turtle encoding of Example 3 (input and output of ShacOWL), pseudocodes of the benchmark generator, and benchmark statistics (positive-to-negative ratio, triple counts for benchmarks, materialised datagraphs, and rewritten shapes) are provided in the appendix. ShacOWL’s source code, is available from GitHub at https://github.com/gorczyca/owl-aware-shacl. Additional materials, including the Java OWL API wrappers for the reasoners, the benchmark generator, result summaries in CSV format, sample benchmarks for each difficulty level (1–15), scripts for setting up and running the experiments, and scripts for reproducing Table 1 and Figure 2, are available from GitHub at https://github.com/gorczyca/owl-aware-shacl-supplementary-material. The full benchmark set (1,500 instances) and raw experimental outputs are available from Figshare under a permanent DOI: https://doi.org/10.6084/m9.figshare.33169694. Use of Generative AI. Claude (Sonnet 4.6, Anthropic) through the Claude Code VS Code extension was used to aid in the implementation of parts of the produced code, by prompting it to provide, modify, or adjust code snippets, which were then manually reviewed and modified after careful inspection. In a similar manner, Claude aided in creating scripts for running experiments on a cluster, evaluating results, and generating summaries as seen in the paper’s tables and plots, all under careful supervision and with multiple reproductions. It was additionally used for minor text editing in Section 6. References [1] K. Abicht (2023) OWL reasoners still useable in 2023. External Links: 2309.06888, Link Cited by: §1. [2] S. Ahmetaj, M. Ortiz, A. Oudshoorn, and M. Simkus (2023) Reconciling SHACL and ontologies: semantics and validation via rewriting. In ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland - Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023), K. Gal, A. Nowé, G. J. Nalepa, R. Fairstein, and R. Radulescu (Eds.), Frontiers in Artificial Intelligence and Applications, Vol. 372, p. 27–35. External Links: Link, Document Cited by: §1, §1, §4, §7. [3] Apache Software Foundation (2024) Apache Jena. Note: https://jena.apache.org Cited by: §1, §6. [4] F. Baader, S. Brandt, and C. Lutz (2005) Pushing the EL envelope. In IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005, L. P. Kaelbling and A. Saffiotti (Eds.), p. 364–369. External Links: Link Cited by: §3. [5] F. Baader, C. Lutz, and S. Brandt (2008) Pushing the EL envelope further. In Proceedings of the Fourth OWLED Workshop on OWL: Experiences and Directions, Washington, DC, USA, 1-2 April 2008, K. Clark and P. F. Patel-Schneider (Eds.), CEUR Workshop Proceedings, Vol. 496. External Links: Link Cited by: §3, §3. [6] C. Bock, A. Fokoue, P. Haase, R. Hoekstra, I. Horrocks, A. Ruttenberg, U. Sattler, and M. Smith (2012)OWL 2 Web Ontology Language(Website) Note: http://w.w3.org/TR/owl2-syntax/w3c Recommendation Cited by: §1. [7] J. Corman, J. L. Reutter, and O. Savkovic (2018) Semantics and validation of recursive SHACL. In The Semantic Web - ISWC 2018 - 17th International Semantic Web Conference, Monterey, CA, USA, October 8-12, 2018, Proceedings, Part I, D. Vrandecic, K. Bontcheva, M. C. Suárez-Figueroa, V. Presutti, I. Celino, M. Sabou, L. Kaffee, and E. Simperl (Eds.), Lecture Notes in Computer Science, Vol. 11136, p. 318–336. External Links: Link, Document Cited by: §2. [8] Data Shapes Working Group Charter(Website) External Links: Link Cited by: §1. [9] R. David, D. Habgood, A. Seaborne, and S. Steyskal (Eds.) (2026) SHACL 1.2 Rules. W3C Working Draft. Note: Available at https://w.w3.org/TR/shacl12-rules/ Cited by: §1. [10] W. Fan and F. Geerts (2010) Relative information completeness. ACM Trans. Database Syst.. External Links: Link, Document Cited by: §1. [11] B. Glimm, A. Hogan, M. Krötzsch, and A. Polleres (2012) OWL: yet to arrive on the web of data?. In W2012 Workshop on Linked Data on the Web, Lyon, France, 16 April, 2012, C. Bizer, T. Heath, T. Berners-Lee, and M. Hausenblas (Eds.), CEUR Workshop Proceedings. External Links: Link Cited by: §1. [12] B. Glimm, I. Horrocks, B. Motik, G. Stoilos, and Z. Wang (2014) HermiT: an OWL 2 reasoner. Journal of Automated Reasoning 53 (3), p. 245–269. External Links: Document Cited by: §6. [13] P. Gorczyca, D. Arndt, M. Diller, J. Hampe, G. Heidenreich, P. Kettmann, M. Krötzsch, S. Mennicke, S. Rudolph, and H. Straß (2025) Supporting risk management for medical devices via the riskman ontology and shapes. In Proceedings of the 21st International Conference on Semantic Systems (SEMANTiCS 2025), Cited by: §1, §3, §8. [14] S. Harris and A. Seaborne (2013) SPARQL 1.1 query language. W3C Recommendation W3C. External Links: Link Cited by: §1. [15] M. Horridge and S. Bechhofer (2011) The OWL API: a Java API for OWL ontologies. Semantic Web 2 (1), p. 11–21. External Links: Document Cited by: §6. [16] Interoperability Test Bed, European Commission DIGIT (2024) ISAITB SHACL Validator. Note: https://github.com/ISAITB/shacl-validator Cited by: §1, §6. [17] Y. Kazakov, M. Krötzsch, and F. Simančík (2014) The incredible ELK: from polynomial procedures to efficient reasoning with ℰℒEL ontologies. Journal of Automated Reasoning 53 (1), p. 1–61. External Links: Document Cited by: §6. [18] J. Ke, Z. G. Zacouris, and M. Acosta (2024) Efficient validation of SHACL shapes with reasoning. Proc. VLDB Endow. 17 (11), p. 3589–3601. External Links: Link, Document Cited by: §1. [19] M. Knorr, J. J. Alferes, and P. Hitzler (2011) Local closed world reasoning with description logics under the well-founded semantics. Artif. Intell.. External Links: Link, Document Cited by: §1. [20] H. Knublauch, T. Bergwinkl, Y. Taghzouti, and J. Wright (Eds.) (2026) SHACL 1.2 Core. W3C Working Draft. Note: Available at https://w.w3.org/TR/shacl12-core/ Cited by: §7. [21] H. Knublauch and D. Kontokostas (2017) Shape constraint language (SHACL). W3C Recommendation W3C. Note: https://w.w3.org/TR/shacl/ Cited by: §1. [22] H. Knublauch (2025) TopBraid SHACL API. Note: https://github.com/TopQuadrant/shacl Cited by: §1, §6. [23] M. Krötzsch (2012) OWL 2 profiles: an introduction to lightweight ontology languages. In Reasoning Web. Semantic Technologies for Advanced Query Answering - 8th International Summer School 2012, Vienna, Austria, September 3-8, 2012. Proceedings, T. Eiter and T. Krennwallner (Eds.), Lecture Notes in Computer Science, Vol. 7487, p. 112–183. External Links: Link, Document Cited by: §1, §1. [24] A. N. Lam, B. Elvesæter, and F. Martin-Recuerda (2015) A performance evaluation of OWL 2 DL reasoners using ORE 2015 and very large bio ontologies. In Proceedings of the 5th OWL Reasoner Evaluation Workshop (ORE 2015), Cited by: §1. [25] B. Motik, I. Horrocks, and U. Sattler (2007) Adding integrity constraints to OWL. In Proceedings of the OWLED 2007 Workshop on OWL: Experiences and Directions, Innsbruck, Austria, June 6-7, 2007, C. Golbreich, A. Kalyanpur, and B. Parsia (Eds.), CEUR Workshop Proceedings, Vol. 258. External Links: Link Cited by: §1. [26] B. Motik, I. Horrocks, and U. Sattler (2007) Bridging the gap between OWL and relational databases. In Proceedings of W, External Links: Link, Document Cited by: §1. [27] M. A. Musen (2015) The protégé project: a look back and a look forward. AI Matters 1 (4), p. 4–12. External Links: Link, Document Cited by: footnote 3. [28] C. Okulmus and M. Simkus (2024) SHACL validation under the well-founded semantics. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi, Vietnam. November 2-8, 2024, P. Marquis, M. Ortiz, and M. Pagnucco (Eds.), External Links: Link, Document Cited by: §3. [29] A. M. Oudshoorn, M. Ortiz, and M. Šimkus (2026) SHACL validation in the presence of ontologies: semantics and rewriting techniques. Artificial Intelligence 352, p. 104483. External Links: ISSN 0004-3702, Document, Link Cited by: §1, §4, §7. [30] A. Oudshoorn, M. Ortiz, and M. Simkus (2024) Reasoning with the core chase: the case of SHACL validation over ELHI knowledge bases. In Proceedings of the 37th International Workshop on Description Logics (DL 2024), Bergen, Norway, June 18-21, 2024, L. Giordano, J. C. Jung, and A. Ozaki (Eds.), CEUR Workshop Proceedings, Vol. 3739. External Links: Link Cited by: §1, §1, §4, §7. [31] P. Pareti, G. Konstantinidis, T. J. Norman, and M. Şensoy (2019) SHACL constraints with inference rules. In The Semantic Web – ISWC 2019, C. Ghidini, O. Hartig, M. Maleshkova, V. Svátek, I. Cruz, A. Hogan, J. Song, M. Lefrançois, and F. Gandon (Eds.), Cham, p. 539–557. External Links: ISBN 978-3-030-30793-6 Cited by: §1. [32] A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati (2008) Linking data to ontologies. In Journal on Data Semantics X, S. Spaccapietra (Ed.), Berlin, Heidelberg, p. 133–173. External Links: ISBN 978-3-540-77688-8 Cited by: §1. [33] O. Savkovic, E. Kharlamov, and S. Lamparter (2019) Validation of SHACL constraints over KGs with OWL 2 QL ontologies via rewriting. In The Semantic Web - 16th International Conference, ESWC 2019, Portorož, Slovenia, June 2-6, 2019, Proceedings, P. Hitzler, M. Fernández, K. Janowicz, A. Zaveri, A. J. G. Gray, V. López, A. Haller, and K. Hammar (Eds.), Lecture Notes in Computer Science, Vol. 11503, p. 314–329. External Links: Link, Document Cited by: §1, §4. [34] E. Sirin, B. Parsia, B. C. Grau, A. Kalyanpur, and Y. Katz (2007) Pellet: a practical OWL-DL reasoner. Journal of Web Semantics 5 (2), p. 51–53. External Links: Document Cited by: §6. [35] A. Sommer and N. Car (2021) pySHACL. Note: https://github.com/RDFLib/pySHACL External Links: Document Cited by: §1, §6, footnote 6. [36] D. Tsarkov and I. Horrocks (2006) FaCT++ description logic reasoner: system description. In Proc. of IJCAR 2006, p. 292–297. Note: JFact is a Java port of FaCT++, available at https://jfact.sourceforge.net/ External Links: Document Cited by: §6. [37] G. Xiao, D. Calvanese, R. Kontchakov, D. Lembo, A. Poggi, R. Rosati, and M. Zakharyaschev (2018) Ontology-based data access: a survey. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, p. 5511–5519. External Links: Document, Link Cited by: §1. Appendix Turtle Encoding. Figure 3 (Figure 4) contains the input (output) of our rewriting algorithm in Turtle format. It corresponds to the logic-based encoding from Example 3, helping to establish the relationship between these two notations. For example, the shape s2(∃r−.⊤)s_2(∃ r^-. ) corresponds to the triple :s2 sh:targetObjectsOf :r. (Figure 3, right, Line 15) On the other hand, the universal targetting of bridge shapes s1⨝(⊤)s_1 ( ) and s2⨝(⊤)s_2 ( ) is obtained by addressing all named individuals, instances of all class names, subjects and objects of all role names present in the ontology as shown in Figure 4, Lines 29 and 35. For this, and other computational reasons names of all ontology individuals, roles and classes have to be declared as in (Figure 3, Lines 7–13). ⬇ 1 @prefix : <http://example.org/> . 2 @prefix owl: <http://w.w3.org/2002/07/owl#> . 3 @prefix rdfs: <http://w.w3.org/2000/01/rdf-schema#> . 4 @prefix rdf: <http://w.w3.org/1999/02/22-rdf-syntax-ns#> . 5 6 # Classes 7 :A a owl:Class . 8 :B a owl:Class . 9 :C a owl:Class . 10 # Object properties 11 :r a owl:ObjectProperty . 12 :r0 a owl:ObjectProperty . 13 :r1 a owl:ObjectProperty . 14 # A⊑BA B 15 :A rdfs:subClassOf :B . 16 # ∃r.B⊑C∃ r.B C 17 [ a owl:Restriction ; 18 owl:onProperty :r ; 19 owl:someValuesFrom :B ] rdfs:subClassOf :C . 20 # dom(r)⊑Adom(r) A 21 :r rdfs:domain :A . 22 # ran(r)⊑Bran(r) B 23 :r rdfs:range :B . 24 # r0⊑r_0 r 25 :r0 rdfs:subPropertyOf :r . 26 # r1∘r⊑r_1 r r 27 :r owl:propertyChainAxiom ( :r1 :r ) . 28 # r0⊑r1r_0 r_1 29 :r0 rdfs:subPropertyOf :r1 . ⬇ 1 @prefix : <http://example.org/> . 2 @prefix sh: <http://w.w3.org/ns/shacl#> . 3 4 # s1←∃r.B,s1(A)s_1←∃ r.B, 8.19447pts_1(A) 5 :s1 a sh:NodeShape ; 6 sh:targetClass :A ; 7 sh:property [ 8 sh:path :r ; 9 sh:class :B ; 10 sh:minCount 1 11 ] . 12 13 # s2←∃r−.A,s2(∃r−.⊤)s_2←∃ r^-.A, 8.19447pts_2(∃ r^-.\! ) 14 :s2 a sh:NodeShape ; 15 sh:targetObjectsOf :r ; 16 sh:property [ 17 sh:path [ sh:inversePath :r ] ; 18 sh:class :A ; 19 sh:minCount 1 20 ] . Figure 3: Input to the implementation, Turtle encoding of the example from Example 3: TBox T (left) and shapes C (right). ⬇ 1 @prefix ex: <http://example.org/> . 2 @prefix rdf: <http://w.w3.org/1999/02/22-rdf-syntax-ns#> . 3 @prefix s: <https://example.org/shapes#> . 4 @prefix sh: <http://w.w3.org/ns/shacl#> . 5 @prefix xsd: <http://w.w3.org/2001/XMLSchema#> . 6 7 # s1←∃((r0∣r1)∗⋅(r0∣r)).sBs_1←∃ ((r_0 r_1)^*·(r_0 r) ).s_B 8 ex:s1 a sh:NodeShape ; 9 sh:property [ sh:minCount 1 ; 10 sh:node s:S_CLASS_B ; 11 sh:path ( [ sh:zeroOrMorePath [ sh:alternativePath ( ex:r0 ex:r1 ) ] ] [ sh:alternativePath ( ex:r ex:r0 ) ] ) ] ; 12 sh:targetClass ex:A . 13 # s2←∃((r0−∣r−)⋅(r0−∣r1−)∗).sAs_2←∃ ((r_0^- r^-)·(r_0^- r_1^-)^* ).s_A 14 ex:s2 a sh:NodeShape ; 15 sh:property [ sh:minCount 1 ; 16 sh:node s:S_CLASS_A ; 17 sh:path ( [ sh:alternativePath ( [ sh:inversePath ex:r ] [ sh:inversePath ex:r0 ] ) ] [ sh:zeroOrMorePath [ sh:alternativePath ( [ sh:inversePath ex:r0 ] [ sh:inversePath ex:r1 ] ) ] ] ) ] ; 18 sh:targetObjectsOf ex:r . 19 # sA←A∨s∃r.⊤s_A← A s_∃ r. 20 s:S_CLASS_A a sh:NodeShape ; 21 sh:node [ sh:or ( s:S_DomainOf_r [ sh:class ex:A ] ) ] . 22 # sB←B∨sA∨s∃r−.⊤s_B← B s_A s_∃ r^-. 23 s:S_CLASS_B a sh:NodeShape ; 24 sh:node [ sh:or ( s:S_CLASS_A s:S_RangeOf_r [ sh:class ex:B ] ) ] . 25 # sC←C∨s∃r.Bs_C← C s_∃ r.B 26 s:S_CLASS_C a sh:NodeShape ; 27 sh:node [ sh:or ( s:S_EXISTS_r_CLASS_B [ sh:class ex:C ] ) ] . 28 # s1⨝←¬sA∨s1,s1⨝(⊤)s_1 ← s_A s_1, 8.19447pts_1 ( ) 29 s:s1_Bridge a sh:NodeShape ; 30 sh:node [ sh:or ( [ sh:not [ sh:or ( s:S_CLASS_A ) ] ] ex:s1 ) ] ; 31 sh:targetClass ex:A, ex:B, ex:C ; 32 sh:targetObjectsOf ex:r, ex:r0, ex:r1 ; 33 sh:targetSubjectsOf ex:r, ex:r0, ex:r1 . 34 # s2⨝←¬s∃r−.⊤∨s2,s2⨝(⊤)s_2 ← s_∃ r^-. s_2, 8.19447pts_2 ( ) 35 s:s2_Bridge a sh:NodeShape ; 36 sh:node [ sh:or ( [ sh:not [ sh:or ( s:s2_TargetObjectsOf_r ) ] ] ex:s2 ) ] ; 37 sh:targetClass ex:A, ex:B, ex:C ; 38 sh:targetObjectsOf ex:r, ex:r0, ex:r1 ; 39 sh:targetSubjectsOf ex:r, ex:r0, ex:r1 . 40 # s∃r.⊤←∃((r0∣r1)∗⋅(r0∣r)).⊤s_∃ r. ←∃ ((r_0 r_1)^*·(r_0 r) ). 41 s:S_DomainOf_r a sh:NodeShape ; 42 sh:property [ sh:minCount 1 ; 43 sh:path ( [ sh:zeroOrMorePath [ sh:alternativePath ( ex:r0 ex:r1 ) ] ] [ sh:alternativePath ( ex:r ex:r0 ) ] ) ] . 44 # s∃r−.⊤←∃((r0−∣r−)⋅(r0−∣r1−)∗).⊤s_∃ r^-. ←∃ ((r_0^- r^-)·(r_0^- r_1^-)^* ). 45 s:S_RangeOf_r a sh:NodeShape ; 46 sh:property [ sh:minCount 1 ; 47 sh:path ( [ sh:alternativePath ( [ sh:inversePath ex:r ] [ sh:inversePath ex:r0 ] ) ] [ sh:zeroOrMorePath [ sh:alternativePath ( [ sh:inversePath ex:r0 ] [ sh:inversePath ex:r1 ] ) ] ] ) ] . 48 # s∃r.B←∃((r0∣r1)∗⋅(r0∣r)).sBs_∃ r.B←∃ ((r_0 r_1)^*·(r_0 r) ).s_B 49 s:S_EXISTS_r_CLASS_B a sh:NodeShape ; 50 sh:property [ sh:path ( [ sh:zeroOrMorePath [ sh:alternativePath ( ex:r0 ex:r1 ) ] ] [ sh:alternativePath ( ex:r ex:r0 ) ] ) ; 51 sh:qualifiedMinCount 1 ; 52 sh:qualifiedValueShape s:S_CLASS_B ] . 53 # helper shape for target of s2s_2, evaluates to the same as s∃r−.⊤s_∃ r^-. , because objects of r is the same as range of r 54 s:s2_TargetObjectsOf_r a sh:NodeShape ; 55 sh:property [ sh:minCount 1 ; 56 sh:path ( [ sh:alternativePath ( [ sh:inversePath ex:r ] [ sh:inversePath ex:r0 ] ) ] [ sh:zeroOrMorePath [ sh:alternativePath ( [ sh:inversePath ex:r0 ] [ sh:inversePath ex:r1 ] ) ] ] ) ] . Figure 4: Turtle output of the implementation for the example from Example 3, given the input from Figure 3. Benchmarks Generation. Throughout this subsection, parameter names are typeset in teal italics (e.g., numClasses) to make them easily distinguishable across the table and algorithms. Table 2 lists all parameters of the benchmark generator together with their descriptions, and provides the concrete instantiations of each parameter across the 15 difficulty levels used in the evaluation. The benchmarks are generated by three algorithms. GenerateTBox (Algorithm 1) produces an OWL EL- TBox T along with the sets of class names NCN_C, role names NRN_R, and two set of individuals NIN_I, NAN_A. GenerateDataGraph (Algorithm 2) populates a data graph A with random class and role assertions over the data graph individuals NAN_A, class names NCN_C, and role names NRN_R. GenerateSHACL (Algorithm 3) produces a set of SHACL shapes C with targets G, using randomly generated property paths via the auxiliary GeneratePath function; as pathContinueProbability increases with the difficulty level, higher levels yield more deeply nested and structurally complex paths. Each difficulty level is instantiated with 100 benchmark instances, yielding 1,500 instances in total. 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 (NIN_I), rest are data graph individuals (NAN_A) numGCIs (nGCI) Number of general concept inclusions numDomains (nD) Number of domain axioms (r)⊑Cdom(r) C numRanges (nRn) Number of range axioms r⊑Cranr C numRoleChains (nCh) Number of role chain axioms ri∘rj⊑rjr_i r_j r_j numRoleInclusions (nInc) Number of role inclusion axioms ri⊑rjr_i r_j avgClassAssertions (aCA) Average class assertions per individual in the data graph avgRoleAssertions (aRA) Average role assertions per individual in the data graph numShapes (nS) Number of SHACL shapes to generate pathContinueProbability (pCP) Probability of extending a property path recursively Level nC nR nI nGCI nD nRn nCh nInc aCA aRA nS pCP 1 4 2 10 4 2 2 1 1 2.5 3.0 2 0.30 2 11 5 20 10 2 2 1 1 2.5 3.1 2 0.31 3 17 8 35 22 2 2 1 2 2.5 3.2 2 0.32 4 24 12 50 40 2 2 2 4 2.5 3.5 2 0.35 5 50 25 100 80 5 5 4 8 3.0 4.0 3 0.40 6 80 40 150 130 8 8 6 12 3.0 4.5 4 0.45 7 120 60 250 200 12 12 8 18 3.5 5.0 4 0.50 8 180 90 400 300 18 18 12 25 3.5 5.5 5 0.55 9 250 125 600 450 25 25 16 35 4.0 6.0 5 0.60 10 350 175 900 650 35 35 22 50 4.0 6.5 6 0.65 11 500 250 1,300 950 50 50 30 70 4.5 7.0 7 0.65 12 700 350 2,000 1,400 70 70 40 100 5.0 8.0 8 0.70 13 1,000 500 3,000 2,000 100 100 55 140 5.0 9.0 9 0.70 14 1,500 750 4,500 3,000 150 150 75 200 5.5 10.0 10 0.75 15 2,200 1,100 6,500 4,500 220 220 100 280 6.0 11.0 11 0.75 Table 2: Benchmark generator parameters (top) and their instantiations across difficulty levels 1–15 (bottom). Input: numClasses, numRoles, numGCIs, numDomains, numRanges, numRoleChains, numRoleInclusions, numIndividuals Output: OWL EL- TBox T; sets NCN_C, NRN_R, NIN_I, NAN_A NC←C1,…,CnumClassesN_C←\C_1,…,C_ [rgb]0,0.5,0.5numClasses\ with index (Ci)=iidx(C_i)=i 1 NR←r1,…,rnumRolesN_R←\r_1,…,r_ [rgb]0,0.5,0.5numRoles\ with index (ri)=iidx(r_i)=i 2 NI′←a1,…,anumIndividualsN_I ←\a_1,…,a_ [rgb]0,0.5,0.5numIndividuals\ 3 NI←N_I← first ⌊0.2⋅|NI′|⌋ 0.2·|N_I | elements of NI′N_I 4 NA←NI′∖NIN_A← N_I N_I 5 ←∅T← 6 // GCI generation n←0n← 0 7 while n<numGCIsn< [rgb]0,0.5,0.5numGCIs do 8 L←L← random LHS from A,A⊓B,∃r.A,A⊓∃r.B,∃r.a,A⊓∃r.a\A,\ A B,\ ∃ r.A,\ A ∃ r.B,\ ∃ r.\a\,\ A ∃ r.\a\\ where A,B∈NCA,B∈ N_C, r∈NRr∈ N_R, a∈NIa∈ N_I 9 B←random(NC)B← random(N_C) 10 if (C)<(B)idx(C)<idx(B) for every class C appearing in L then 11 add L⊑BL B to T 12 n←n+1n← n+1 13 // Domain/range axioms foreach r in numDomains randomly chosen elements of NRN_R do 14 add (r)⊑random()dom(r) random(C) to T 15 foreach r in numRanges randomly chosen elements of NRN_R do 16 add (r)⊑random()rang(r) random(C) to T 17 // Role chain axioms n←0n← 0 18 while n<numRoleChainsn< [rgb]0,0.5,0.5numRoleChains do 19 pick ri,rj∈NRr_i,r_j∈ N_R randomly 20 if i<ji<j then 21 add ri∘rj⊑rjr_i r_j r_j to T 22 n←n+1n← n+1 23 // Role inclusions n←0n← 0 24 while n<numRoleInclusionsn< [rgb]0,0.5,0.5numRoleInclusions do 25 pick ri,rj∈NRr_i,r_j∈ N_R randomly 26 if i<ji<j then 27 add ri⊑rjr_i r_j to T 28 n←n+1n← n+1 29 return T, NCN_C, NRN_R, NIN_I, NAN_A 30 Algorithm 1 GenerateTBox Input: numIndividuals, avgClassAssertions, avgRoleAssertions Output: Data Graph A ←∅A← 1 // Class assertions n←0n← 0 2 while n<⌊numIndividuals⋅avgClassAssertions⌋n< [rgb]0,0.5,0.5numIndividuals· [rgb]0,0.5,0.5avgClassAssertions do 3 C←random(NC)C← random(N_C) 4 i←random(NA)i← random(N_A) 5 add C(i)C(i) to A 6 n←n+1n← n+1 7 // Role assertions n←0n← 0 8 while n<⌊numIndividuals⋅avgRoleAssertions⌋n< [rgb]0,0.5,0.5numIndividuals· [rgb]0,0.5,0.5avgRoleAssertions do 9 r←random(NRCLOSEr← random(N_R 10 i←random(NA)i← random(N_A) 11 j←random(NA)j← random(N_A) 12 add r(i,j)r(i,j) to A 13 n←n+1n← n+1 14 return A 15 Algorithm 2 GenerateDataGraph Input: numShapes, pathContinueProbability, NCN_C, NRN_R, NAN_A Output: SHACL shape set C, target set G ←∅C← 1 ←∅G← 2 n←0n← 0 3 while n<numShapesn< [rgb]0,0.5,0.5numShapes do 4 ←random(class,node,subjects,objects)kind← random(\ class,\ node,\ subjects,\ objects\) 5 ℎ←GeneratePath()path← GeneratePath( ) 6 if =classkind= class then 7 C←random(NC)C← random(N_C) 8 C′←random(NC)C ← random(N_C) 9 s←∃ℎ.C′s←∃\,path.\,C 10 add s to C 11 add s(C)s(C) to G 12 if =nodekind= node then 13 i←random(NA)i← random(N_A) 14 s←∃ℎ.⊤s←∃\,path. 15 add s to C 16 add s(i)s(i) to G 17 if =subjectskind= subjects then 18 r←random(NR)r← random(N_R) 19 s←∃ℎ.⊤s←∃\,path. 20 add s to C 21 add s(∃r.⊤)s(∃ r. ) to G 22 if =objectskind= objects then 23 r←random(NR)r← random(N_R) 24 C←random(NC)C← random(N_C) 25 s←Cs← C 26 add s to C 27 add s(∃r−.⊤)s(∃ r^-. ) to G 28 n←n+1n← n+1 29 return C, G 30 Function GeneratePath(): 31 ←random(simple,sequence,alternative,inverse)kind← random(\ simple,\ sequence,\ alternative,\ inverse\) 32 pick p∈[0,1]p∈[0,1] uniformly 33 if p>pathContinueProbabilityp> [rgb]0,0.5,0.5pathContinueProbability or =simplekind= simple then 34 r←random(NR)r← random(N_R) 35 return r 36 if =sequencekind= sequence then return GeneratePath()⋅GeneratePath() GeneratePath( )· GeneratePath( ) 37 if =alternativekind= alternative then return GeneratePath()|GeneratePath() GeneratePath( ) GeneratePath( ) 38 if =inversekind= inverse then return GeneratePath()− GeneratePath( )^- 39 Algorithm 3 GenerateSHACL Benchmarks Statistics. Table 3 reports statistics for each of the 15 difficulty levels across the 1,500 generated instances. Since both the ontology and the shapes are randomly generated, it is unlikely that the data will conform to the shapes, and indeed most instances are non-conforming (negative). Level 1 is an exception with an exactly even 50/50 split; from level 2 onward virtually all instances are negative. The table also reports mean RDF triple counts per instance for the input TBox (owl.ttl), the input SHACL shapes (shacl.ttl), and the rewritten output (rewriting.ttl), to help get an idea of how large the output rewriting becomes with respect to the input ontology and shapes. As expected, triple counts grow with the difficulty level. Level #instances mean #triples per instance 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 6 0 100 1 083 29 1 125 3 022 2 380 2 367 2 383 7 0 100 1 654 30 2 125 4 567 4 370 4 514 4 370 8 0 100 2 498 45 3 600 7 082 7 267 – 7 271 9 0 100 3 681 45 6 000 10 230 12 049 – 12 051 10 0 100 5 299 70 9 450 15 396 19 083 – 19 084 11 0 100 7 699 86 14 950 23 130 29 894 – 29 896 12 0 100 11 315 106 26 000 35 117 51 491 – 51 523 13 0 100 16 146 128 42 000 52 280 83 256 – 83 252 14 0 100 24 168 372 69 750 80 679 – – 135 196 15 0 100 36 054 340 110 500 122 659 – – – Total 56 1 444 7 395 88 19 124 23 854 – – – 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. Extra Results. Table 4 complements Table 1 by reporting, for the same full instance set, the minimum, median, and maximum reasoning/rewriting and validation time per approach and validator, computed over successfully completed instances only. Table 5 shows evaluation results restricted to instances solved by every approach, but excluding JFact for the baseline method and pySHACL for rewriting, since both are unable to solve too many instances. Table 6 reports the corresponding minimum, median, and maximum timing statistics for this same restricted instance set. 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 pySHACL 0.29s 0.39s 270.3s TopBraid 1.14s 1.27s 41.4s JFact 0.52s 1.40s 573.1s Isaitb 1.78s 1.83s 42.0s Jena 0.92s 0.99s 4.24s pySHACL 0.29s 0.32s 0.82s TopBraid 1.14s 1.19s 4.61s Pellet 0.49s 1.17s 599.4s Isaitb 1.78s 1.89s 6.21s Jena 0.92s 1.05s 306.0s pySHACL 0.29s 0.38s 3.01s TopBraid 1.14s 1.23s 7.26s pySHACL + OWL-RL 0.42s 6.51s 360.7s + OWL-RL + RDFS 0.47s 10.9s 480.3s 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. V.E. T.V. Av.V. T/O Succ. (%) Rewrit. 0.44h 1.26s Isaitb 0 0.78h 2.25s 0 1254 (100.0%) Jena 0 0.47h 1.36s 0 1254 (100.0%) TopBraid 0 0.54h 1.54s 0 1254 (100.0%) HermiT 15.4h 44.3s Isaitb 0 0.69h 1.97s 0 1254 (100.0%) Jena 0 0.47h 1.36s 0 1254 (100.0%) pySHACL 0 0.28h 0.81s 0 1254 (100.0%) TopBraid 0 0.47h 1.36s 0 1254 (100.0%) Pellet 9.08h 26.1s Isaitb 0 0.68h 1.95s 0 1254 (100.0%) Jena 0 0.47h 1.36s 0 1254 (100.0%) pySHACL 0 0.20h 0.59s 0 1254 (100.0%) TopBraid 0 0.45h 1.28s 0 1254 (100.0%) pySHACL + OWL-RL 0 5.80h 16.6s 0 1254 (100.0%) + OWL-RL + RDFS 0 8.77h 25.2s 0 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 TopBraid 1.14s 1.26s 41.4s Pellet 0.49s 1.03s 432.7s Isaitb 1.78s 1.88s 6.21s Jena 0.92s 1.04s 306.0s pySHACL 0.29s 0.37s 2.47s TopBraid 1.14s 1.22s 4.79s pySHACL + OWL-RL 0.42s 4.59s 112.5s + OWL-RL + RDFS 0.47s 7.47s 165.0s 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.