SHACL (SHApe Constraint Language) is a W3C standardized constraint language for RDF graphs. In this paper, we study SHACL validation in evolving RDF graphs. We identify an update language that can capture intuitive and realistic modifications on RDF graphs and study the problem of static validation under updates, which asks to verify whether a given RDF graph that validates a set of SHACL constraints will remain valid after applying a set of updates. Reducing this problem to usual validation (for a minor SHACL extension) on the current graph allows us to identify problematic updates before applying them to the graph, thus avoiding incorrect and costly computations on potentially huge RDF graphs. More importantly, it provides a basis for further services for reasoning about evolving RDF graphs. In this spirit, we provide preliminary results for a version ofstatic validation under updates that verifies whether every graph that validates a SHACL specification will still do so after applying a given update sequence. This result builds on previous work that addresses analogous problems but using Description Logics instead of SHACL to describe conditions on graphs.
CEUR ceur-ws.org
updates, which asks whether a given RDF graph will validate a SHACL shapes graph after applying a sequence of updates. In this way, problematic updates may be detected before they are applied, avoiding costly incorrect computations. We also provide preliminary results for a more interesting version ofstatic validation under updates that verifies whether every graph that validates a SHACL specification will still do so after applying a given update sequence.
In our previous work [
This work describes our first steps in this direction. We present a framework for specifying
transformations on RDF graphs in the presence of SHACL constraints. We propose a language
to express modifications on RDF graphs, related to SPARQL Update, but also allowing sequences
of updates that admit conditional actions. In particular, the update language uses SHACL shapes
for selecting nodes or arcs for modification and for expressing the preconditions in conditional
actions. We then study the problem ofvalidation under updates in this setting, using SHACL
to describe the constraints that are to be preserved and in particular, we adapt theregression
method from [
In this section, we introduce RDF graphs and SHACLvalidation. We follow the abstract syntax
and semantics for the fragment of SHACL core studied in 5[]; for more details on the W3C
specification of SHACL core we refer to [
We assume a countably infinite set of shape names, disjoint from in , , . A shape atom is an expression of the form() , where ∈ and ∈ . A path expression is a regular expression built using the usual operators∗, ⋅, ∪ from symbols + = ∪ { − ∣ ∈ }, where − is the inverse property of . A (complex) shape is an , ′ ∶∶= ⊤ ∣ ∣ ∣ ∣ ∧
′ ∣ ¬ ∣≥ . ∣ = ∣ (, ) ∣ ( ) where ∈ , ∈ , ∈ , is a set of property names, is a positive integer, and is a path
′ instead of ¬(¬ ∧ ¬ ′); ≥ instead of ≥ .⊤ ; ∃. expression. In what follows, we write ∨ instead of ≥1 . ; ∀.
instead of ¬∃.¬ .
A (shape) constraint is an expression of the form ↔ , where ∈ and is a possibly complex shape. Targets in SHACL prescribe that certain nodes of the input data graph should validate certain shapes. Atarget expression is of the form ( , ) , where is a shape name and takes one of the following forms: • constant from , also called node target, • class name from , also called class target, • expressions of the form∃ with ∈ , also called subjects-of target, • expressions of the form∃ − with ∈ , also called objects-of target.
A target is any set of target expressions. Ashapes graph is a pair (, ) , where is a set of constraints and is a set of targets. We assume that each shape name appearing in occurs exactly once on the left-hand side of a constraint, and each shape name occurring in must also appear in . A set of constraints is recursive, if there is a shape name in that directly or indirectly refers to itself. In this work, we focus onon-recursive constraints.
The semantics of SHACL can naturally be given in terms of interand an interpretation function⋅ that maps each shape name or class name ∈ pretations. More precisely, an interpretation consists of a non-empty finite domain Δ ⊂ set ⊆ Δ and each property name ∈ to a set of pairs ⊆ Δ × Δ. The evaluation of complex shape expressions w.r.t. an interpretation is given in terms of a function⋅ that maps ∪ to a a shape expression to a set of nodes, and a path expression to a set of pairs of nodes as in Table 1. Then, an interpretation satisfies a constraint s ↔ if s = , and satisfies a shapes graph (, ) , if satisfies all constraints in and ⊆ for each( , ) ∈ . If satisfies Γ, for Γ a constraint, set of constraints, target, or shapes graph, we say is a model of Γ and denote it in symbols by ⊧ Γ . An interpretation is a shape assignment for a data graph , if = { ∣ () ∈ } for each class name , and = {(, ) ∣ (, ) ∈ } for each property name .
Intuitively, is a shape assignment for if class and property names are interpreted as specified by . For simplicity, in this work, we view shape assignments as sets of atoms of the form ∪ , where = {() ∣ ∈
} is a set of shape atoms. A data graph validates a shapes graph (, )
if there exists a shape assignment for that satisfies (, ) .
Clearly, for non-recursive constraints, which is the setting we consider here, the unique assignment ,
obtained in a bottom-up fashion, starting from and evaluating each constraint once, is a model of . More precisely, since the constraints i n are non-recursive, ⊤ = Δ
= {} s = { ∣ s() ∈ } (≥ .) = { ∣ |{(, ) ∈ () ( = ) = { ∣ ∀ ∶ (, ) ∈ () and ∈ () }| ≥ } if (, ) ∈ ()
} ((, )) (()) = { ∣ ∄ ∶ (, ) ∈ () = { ∣ ∀ ∉ ∶ ∉ (∃) () = {(, ) ∣ (, ) ∈ }
( ( ⋅ ′) = {(, ) ∣ ∃ ∶ (, ) ∈ () and (, ) ∈ ()
} } −) = {(, ) ∣ (, ) ∈ } and (, ) ∈ ( ′) } = { ∣ () ∈ } (¬) = Δ ⧵ ()
( 1 ∧ 2) = ( 1) ∩ ( 2) ( ∪ ′) = () ∪ ( ′) ( ∗) = {(, ) ∣ ∈ Δ} ∪ () ∪ ( ⋅ ) ∪ ⋯ one can start from constraints of the form 1 ↔ 1, where 1 has no shape names, and add of the form 2 ↔ 2, where 2 has only shape names occurring in 1 and add in 2 all 2() ∪ 1; the new assignment is ∪ 1 ∪ 2. We proceed like this with the rest of the constraints, by evaluating each of them once, until all of them are processed. The such that ∈ J 1K and obtain ∪ 1
. We then proceed with constraints is unique and is a model that satisfies all the constraints in ; we call the model of and . Then, we can formulate validation as follows: a data if , satisfies ( , ) for every target( , ) ∈ .
Example 2.1. Consider the following data graph and shapes graph (, ) : = { ( 1), ( 2), ( 1), (
2), (), (), ( ), (, 1), (, 1), ( , 2)} = { PrjShape ↔ ∨ ℎ ,
EmplShape ↔ ∨
∃ . }, = {( , Intuitively, the data graph contains 2 projects, 1, 2 which are also active projects, as well as three employees, , , ; the first two work for 1 and works for 2. Together, the constraints and target intuitively state that all projects must be either active or finished, and all those working for some projects must be instances of the class or work for some active project. In this case, validates (, ) PrjShape( 2), EmplShape(),
; this is witnessed by the assignment ∪ { PrjShape( 1), EmplShape(),
EmplShape( )} which satisfies .
In this section, we propose an extention of SHACL with a construc(t, ) for a singleton property and with diference of properties. We also allow for complex target expressions( , ) , where can now be any complex shape expression without shape names, and we allow for variables to occur in the place of constants. Moreover, we allow for targets to support Boolean combinations of target expressions. We denote with SHACL+ this extended version of SHACL. This extension turns out to be necessary to capture the efects of actions on SHACL constraints and to express preconditions in the update language defined in the following section.
Assume a countable set of variables (disjoint from the rest). More precisely, SHACL+ properties are defined according to the following syntax:
, ′ ∶∶= ∣ ( 1, 2) ∣ − ∣ ⧵ ′ where 1, 2 ∈ ∪ and ∈ ; we call them complex properties. Paths over complex properties and (complex) shape expressions over such paths are defined as expected. Targets are extended to allow variables in the places of nodes and complex shapes and Boolean combinations of target expressions as well.
More formally, SHACL+ target expressions are defined as follows: • ( , ) , where is a complex shape expression without shape names, is a target, • a target expression(, ) , where ∈ ∪ is a target, • if 1 and 2 are targets, then 1 ∧ 2, 1 ∨ 2, and ¬ 1 are targets.
If no variables appear in (or ), then it is calledground. Now, when an assignment is a model of a target is naturally defined as follows.
Definition 3.1. Consider a shape assignment and a ground target in SHACL+. Then, is a model of , that is ⊧ , if the following hold: • ∈ , if is a target expression of the form ( , ) , • ⊧ 1 and ⊧ 2, if is of the form 1 ∧ 2, • ⊧ 1 or ⊧ 2, if is of the form 1 ∨ 2, and • ⊧ ̸ 1, if is of the form ¬ 1
Finally, in SHACL+ we also allow for Boolean combinations of shapes graphs. More formally, a SHACL+ shapes graph is defined recursively as follows: • (, ) is a SHACL+ shapes graph, where and are ground SHACL+ sets of constraints and targets, respectively, and • if 1, 2 are SHACL+ shapes graphs, then 1 ∧ 2, 1 ∨ 2, and ¬ 1 are SHACL+ shapes graphs.
A SHACL+ shapes graph is called normal, if it is of the form(, ) , where and are ground SHACL+ constraints and targets, respectively. Validation is naturally defined as follows. Definition 3.2. Consider SHACL+ shapes graph and data graph . Then, validates , if the following hold: • , ⊧ , if is of the form (, ) , • validates 1 and 2 if if of the form 1 ∧ 2, • validates 1 or 2 if if of the form 1 ∨ 2, and • does not validate 1 if is of the form ¬ 1
Allowing Boolean combinations of shapes graphs is just syntactic sugar, as each SHAC+L shapes graphs can be converted into equivalent normal shapes graphs by simply renaming the shape names in each normal shapes graph appearing in , taking the union of all constraints, and pushing the Boolean operators to the targets.
Proposition 3.3. Consider a shapes graph in SHACL+ and consider a data graph . Then, can be converted in linear time into a normal SHACL+ shapes graph ( , ) such that for every data graph , it holds that validates if validates ( , ).
The above proposition shows that allowing Boolean combinations of shapes graphs is just syntactic sugar, since we can equivalently transform such shapes graphs into a unique normal shapes graph (, ) in SHACL+.
We now present the action language for updating RDF graphs. It is composed of two types of actions, namely basic and complex actions. Roughly, the basic actions allow to insert or delete constants from the evaluation of a shape expression or arbitrary property over the graph to a class or property name, respectively. The complex actions allow for composing various actions and to perform conditional checks over the data. In particular, we assume that a set of SHACL constraints that contains all the necessary and suficient shape constraints is given in the input together with the set of actions. The preconditions in the actions are targets in SHAC+L,that is any Boolean combination of target expressions that will be checked w.r.t. a set of constraints.
Basic actions are defined by the following grammar: ∶∶= ( ⊕ ⟵ ) ∣ ( ⊖ ⟵ ) ∣ ( ⊕ ⟵ ) ∣ ( ⊖ ⟵ ) where is a class name, a complex shape without shape names, a property name, and a complex property. Complex actions are defined by the following grammar: ∶∶= ∅ ∣ ⋅ ∣ ((, +)?[]) ⋅ where is a basic action,∅ is an empty action, is a complex action, and(, +) is a SHACL+ normal shapes graph. We may sometimes write ( +?[]) ⋅ , omitting from the actions if is given in the input, and the precondition target s + are required to be applied on the input .
A substitution is a function from to . For a Boolean target, an action, or an action sequence , we use ( ) to denote the result of replacing in every occurrence of a variabl e by a constant () . An action is ground if it has no variables, and ′ is a ground instance of an action if ′ = () for some substitution .
Intuitively, an application of a ground action( ⟵⊕ ) on a graph and a ground set of constraints , stands for the addition of() to for each that makes true in the model , of and ; analogously for( ⟵⊖ ) , where now () will be removed from for each that makes true in , . The two operations can also be performed on complex properties. Composition stands for successive action execution, and a conditional actio((n, +)? 1[ 2]) expresses that 1 is executed if is true in , , and 2 is performed otherwise. If 2 = ∅, then we have an action with a simple precondition as in classical planning languages, and we write it as (, +)? 1, without 2. The semantics of applying actions on data graphs, w.r.t. a set of constraints, is defined only on ground actions and constraints.
Definition 4.1. Let be a data graph, and a ground complex action. Then, the result of applying on is defined recursively as follows: • if is a basic action, then – = ∪ {() ∣ ∈ – = ⧵ {() ∣ ∈ – = ∪ {(, ) ∣ (, ) ∈ – = ⧵ {(, ) ∣ (, ) ∈ } for of the form ( } for of the form ( ⊕ ⟵ ) , ⊖ ⟵ ) ,
⊕ } for of the form ( ⟵ ) , and
⊖ } for of the form ( ⟵ ) • if is a complex action of the form ⋅ , then = ( ) • if is a complex action of the form ((, +)? 1[ 2]) ⋅ , then is – 1⋅ , if , satisfies , – 2⋅ if ,
does not satisfy .
We illustrate the efects of an action update on a data graph with an example.
Example 4.2. Consider again and (, ) from Example 2.1. Now, consider the action that expresses the termination of project 2, which is removed from the active projects and added to the ifnished ones; the employees working only for this project are removed.
= ( ⊖ ⟵ 2) ⋅ ( ℎ ⊕ ⟵ 2) ⋅ ( ⊖ ⟵ ∀ . 2) After applying to , we obtain the updated data graph = ( ⧵ { ( 2), ( )}) ∪ { ℎ ( 2)}. The updated data graph does not validate the shapes graph (, ) since now will still have a -relation to project 2, but he does not satisfy the constraint for the shape name EmplShape– is not an employee and does not work for an active project.
Note that we have not defined the semantics of actions with variables, that is non-ground actions. In our approach, all variables of an action are seen as parameters whose values are given before execution by a substitution with actual constants, such as by grounding. Note that the execution of actions on an initial data graph is allowed to modify the extensions of class and property names, yet the domain remains fixed. In many scenarios, we would like actions to have the ability to introduce “fresh” nodes to a data graph. Intuitively, the introduction of new nodes can be modeled in our setting by separating the domain of an assignment into the active domain and the inactive domain. The active domain consists of all nodes that occur in the data graph, whereas the inactive domain contains the remaining nodes, which can be seen as a supply of fresh nodes that can be introduced into the active domain by executing actions. Since we are interested only in finite sequences of actions, a suficient supply of fresh constants can always be ensured by taking a suficiently large yet still finite inactive domain in the initial instance. We remark also that deletion of nodes can naturally be modeled in this setting by actions that move objects from the active domain to the inactive domain.
Example 4.3. Consider again our running example. Now consider the following action: ′ = ({ ↔ ∀ . 2}, {(, )})?( ⊖ ⟵ {(, 2)}) Under the substitution ()
= the shapes graph ({ ↔ ∀ . by deleting ( , of the ground complex action ⋅
′ 5. Capturing Efects of Updates , which maps the variable to
, the data graph validates 2}, {( , )}) . Hence, the ground action
′ 2). The resulting data graph satisfies
(, ) on results in a valid data graph.
can be applied to . Thus, the application In this section, we define a transformation (, ) that essentially rewrites the input shapes graph (, )
to capture all the efects of an action . This transformation can be seen as a form of regression, which incorporates the efects of a sequence of actions “backwards,” from the last one to the first one. More precisely, the transformation (, ) (, ) and an action and rewrites them into a new shapes graph ( , ), possibly in SHACL+, takes a SHACL shapes graph such that for any data graph the following holds: validates (, )
if validates ( , )
If is without preconditions, the result of applying the transformation is a shapes graph ( , ), where is a SHACL set of constraints, and is a set of target expressions( , ) (similarly as in plain SHACL), but may contain complex shape expressions in place of . Intuitively, the idea is to simply update the bodies of constraints i n and target expressions in accordingly, namely the actions replace a concept name occurring in and with ∧ (or ⊕ ⟵ (or ⊖ ⟵ ), and a property with ∪ (or ⧵ ) if the action is ⊕ ⟵ (or ∧ ¬ ) if the action is
⊖ is satisfied by , Definition 5.1. as follows: ⟵ ). Now consider the case, where the action is of the form(, +)? 1[ 2]. Then, intuitively, we create two shapes graphs: one shapes graph( 1 , 1) if the SHACL+ target + and ( 2
, 2) if the SHACL+ target + is not satisfied by , . the new SHACL+ shapes graph that is obtained from by replacing in every class or property name with the expression ′. Then, the transformation ( ) of w.r.t., is defined recursively Assume SHACL+ shapes graph and and an action . We use ← ′ to denote
( ) = ( ⟵⊕ )⋅ ( ) = ( ( ⟵⊖ )⋅ ( ) = ( ( ⟵⊕)⋅ ( ⟵⊖)⋅ ( ) = ( ( ) = ( ( )) ←∨ ( )) ←∧¬ ( )) ←∪ ( )) ←⧵ ((, +)? 1[ 2])⋅ ( ) = (¬(, +) ∨ 1⋅ ( )) ∧ ((, +) ∨ 2⋅ ( ))
Note that in the presence of conditional actions, we may obtain Boolean combinations of normal shapes graphs, whose number may be exponential in the size of the input action . However, each of the normal shapes graphs will be of polynomial size. When no conditional actions are present, then the result of the transformation on a SHACL shapes graph is a normal SHACL+ shapes graph that simply uses role diference in constraints (role union can be captured by paths) and possibly complex expressions without shape names in target expressions. Moreover, note that by proceeding as in Proposition3.3, the result of ( ) can be converted in an equivalent SHACL+ normal shapes graph ( , ).
Using similar arguments as in the proof of Theorem 4.2 in [
Theorem 5.2. Given a ground action , a data graph and a SHACL shapes graph . Then, validates if and only if validates ( ) .
This allows us to perform validation under updates leveraging standard, static validators for SHACL+. We illustrate the transformation above with an example.
Example 5.3. Consider the shapes graph (, ) and the action from our running example. Then, the transformation ((, )) of (, ) w.r.t. is the new shapes graph ( ′, ′), where: ′ = {PrjShape ↔ ( ∧ ¬
EmplShape ↔ ( ∧ ¬∀ . ′ = {( ,
PrjShape), (∃ , 2) ∨ ( ℎ ∨
2), 2) ∨ ∃ .( ∧ ¬ EmplShape)} 2)},
In this section, we consider a stronger form of reasoning about updates. We have seen that, for each input graph, validation under updates can be reduced to usual validation. Now we look at whether a sequence of actions is compatible with the constraints, independently of a concrete data graph, that is, whether the execution of a given sequence of actions always preserves the satisfaction of a given shapes graph, for every data graph.
Definition 6.1. Let be a shapes graph and let be an action. Then is a -preserving action if for every data graph that validates , it holds that validates . The static validation under updates problem is:
Given an action and a shapes graph , is -preserving?
Using the transformation from Definition 5.1, we can reduce static validation under updates to unsatisfiability of shapes graphs: an action is not -preserving if and only if there is some data graph that does not validate ∗( ) , where ∗ is obtained from by replacing each variable with a fresh constant name not occurring in the input.
Analogously to Theorem 5.2 in [
It has been shown in [
We have presented some preliminary work on formalizing updates for RDF graphs over SHACL constraints. We addressed an important question: validation under updates, which asks to verify whether a given RDF graph that validates a set of SHACL constraints, will remain valid after applying a set of updates. This allows to identify problematic updates before applying them to the graph, and thus to avoid incorrect and very costly computations on potentially huge RDF graphs. In particular, it is beneficial to know if a set of updates leads to a valid graph in case returning to the initial valid state is dificult, or that the user does not have suficient permissions in the system. To realize this form of static validation, we first identify a suitable update language, that can capture intuitive and realistic modifications on RDF graphs, covers a significant fragment of SPARQL updates and extends them to allow for conditional updates.
We also present a stronger form of static validation under updates that considers validation on every graph that validates a given SHACL shapes graph. We show that the latter problem can be reduced to (un)satisfiability of a shapes graph in SHACL +, a minor extension of SHACL, which is known to be undecidable already for plain SHACL, but feasible incoNexpTime for some expressive fragments.
SHACL+ mainly extends SHACL with singleton properties and diference of properties, which are needed to capture the efects of the proposed actions on SHACL constraints. We also allow for more complex targets. However, most of the extensions allowed in the targets in this work are “syntactic sugar” and can be incorporated into plain SHACL. We note that the SHACL Community Group is working on extending SHACL to support some of the features allowed in this work, including more expressive targets as so-called SPARQL-based targets, with ongoing review and documentation in the SHACL Advanced Features draft 1.
Toward lowering the complexity of static validation, we plan to analyze the problem for other relevant fragments of SHACL. We will also study other basic static analysis problems such as, for instance, the static type checking problem 9[], which for a given action, a source and target shapes graph, asks whether, for every data graph that validates the source shapes graph, the data graph after applying the action also validates the target shapes graph. Other interesting problems related to planning ask to check whether there exists a sequence of actions that leads a given data graph into a desired (or undesired) state where some property holds (or does not hold). An important direction for future work is to provide an implementation of the regression method. This method allows us to perform validation under updates by leveraging standard validators, provided that they can support SHACL+; this is not the case for current validators, but we believe that this extension is not hard to incorporate to existing validators, and plan to address this in our future work.
This work was supported by the Austrian Science Fund (FWF) and netidee SCIENCE project T1349-N and the FWF project P30873.
Lecture Notes in Computer Science, Springer, 2023, pp. 19–32. URL: https://doi.org/10.1007/ 978-3-031-39784-4_2. doi:10.1007/978-3-031-39784-4\_2. [8] B. Bogaerts, M. Jakubowski, J. V. den Bussche, SHACL: A description logic in disguise, in: G. Gottlob, D. Inclezan, M. Maratea (Eds.), Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR, volume 13416 ofLecture Notes in Computer Science, Springer, 2022, pp. 75–88. URL: https://doi.org/10.1007/978-3-031-15707-3_7. doi:10.1007/978-3-031-15707-3\_7. [9] I. Boneva, B. Groz, J. Hidders, F. Murlak, S. Staworko, Static analysis of graph database transformations, in: Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, ACM, 2023, pp. 251–261. URL: https://doi.org/10. 1145/3584372.3588654. doi:10.1145/3584372.3588654.