W3C has recently introduced SHACL as a new standard for integrity constraints on RDF graphs. Unfortunately, the standard defines the semantics of non-recursive constraints only, which has spurred recent research eforts into finding a suitable, mathematically crisp semantics for constraints with cyclic dependencies. To this end, Corman et al. [1] introduced a semantics related to supported models known in logic programming, while Andreşel et al. [2] presented a semantics based on stable models known in Answer Set Programming (ASP). In this paper, we argue that recursive SHACL can be naturally equipped with a semantics inspired in the well-founded semantics for (recursive) DATALOG queries with default negation. This semantics is not only intuitive, but it is also computationally tractable, unlike the previous proposals. To draw a connection with the classic definition of well-founded semantics in logic programming, we provide a simple translation of recursive SHACL under the well-founded semantics into propositional logic programs under the well-founded semantics. This translation is not only of theoretical interest: It can be eficiently implemented using the functionality of standard RDF triple stores (specifically, by issuing a small number of SPARQL queries), followed by an eficient evaluation using an existing engine for computing the well-founded model of a propositional logic program.
Graph-structured data is becoming increasingly prominent and popular, mainly because it does not require the development of rigid database schemas. This is important in emerging scenarios where data has complex structure, where it may be highly incomplete, or where its structure evolves over time, which makes the development of a fixed database schema challenging. This has spurred research into topics like Knowledge Graphs, Property Graphs, Graph Databases, RDF graphs, etc. The flexible nature of graph-structured data does not mean we are uninterested in the quality and the structural integrity of the stored data. In traditional relational databases, the so-called integrity constraints provide means to enforce a strict structure and maintain quality of stored information, and we would like to have similar tools for graph-structure data. However, this is not easy: we need to strike a good balance between the power to assert some control over the structure of data, and being relaxed enough to not negate the benefits of the graph-based data model.
To address the above challenge, W3C has recently introduced SHACL1 as a new standard
for expressing constraints on RDF graphs (we refer the reader to [
The rest of this paper is organized as follows: • We conclude this introduction with a rather detailed motivating example to illustrate the basic ideas and the challenge addressed in this paper. • In Section 2, we recall the well-founded semantics for propositional logic programs based on the notion of unfounded sets, and provide an example on how the (unique) well-founded model of a program can be computed. • In Section 3, we recall the (abstract) syntax of SHACL and recall the (2-valued) supported model semantics of SHACL. This most basic semantics is illustrated with an example that shows an undesired self-justification cycle. • In Section 4, we present our well-founded semantics for SHACL, based on a notion of unfounded sets (adapted from the notion used for logic programs). • In Section 5, we describe a transformation that allows to reduce the validation problem to the task of computing the well-founded model of a propositional logic program. This transformation can be implemented eficiently and leads to a way of performing SHACL validation under the new semantics using some of the existing deductive database engines. • In Section 6, we conclude this paper, including a discussion of some of the challenges and future directions in the research on SHACL. ./(!#0%+' *+ ( ) () () 1203*4%%
Alex ' ()%&"*+,./(!#0%+' *+ ' ()%&"*+,
!"#$%&" Blake
Cameron
Drew ' ()%&"*+,
Employee ∨ ∃hasSuperior.EmployeeShape
Example 1. Consider the example knowledge graph (KG) in Figure 1, containing some information about members of an educational institution. The KG mentions four persons called Alex, Blake, Cameron and Drew, which correspond to the four nodes of the KG. Alex is (explicitly) stated to be an employee in this institution, which is indicated by their membership in the class Employee. Cameron is a (regular) student in this institution, which is indicated by their membership in the class Student. Blake is a mentor of Cameron, which is indicated via the edge between them labeled with the property isMentorOf. Blake has Alex as a superior in this institution, captured via an edge labeled with hasSuperior. Furthermore, Cameron has Drew as another mentor. Finally, the KG has two facts that are quite questionable: Alex is a mentor of Alex, and Drew is a superior of Drew. The presence of these two facts is clearly unintended (and should be dealt with using an appropriate validation machinery).
The KG presented so far does not carry any semantic information on the expected relations between the diferent kinds of objects that are present, it contains no schema information nor integrity constraints. The SHACL standard specifies a language for expressing such information. Consider the three expressions (P), (E) and (S) in Figure 1, which intuitively correspond to three validation rules that allow to identify nodes of three types: nodes corresponding to professors, employees, and students, respectively. Each of these three types has a name (i.e., ProfessorShape , EmployeeShape , and StudentShape) that is associated to its definition using a (possibly quite complex) logicbased expression. In the DATALOG terminology, we have ProfessorShape , EmployeeShape , and StudentShape as monadic intensional predicates, while Employee, Student are unary extensional predicates, and isMentorOf, hasSuperior are binary extensional predicates. Specifically, (P) tells us that a person is considered to be a professor (has type ProfessorShape ) if they are an employee (of type EmployeeShape ) and they mentor at least one student (an object with type StudentShape). According to the rule (E), a person is an employee (has type EmployeeShape ) if that is stated explicitly (via membership in the class Employee), or the person has a superior that is in turn of type EmployeeShape . The last rule (S) tells us that an object is of type StudentShape if the object is explicitly stated to be an instance of the class Student, or the object is of type EmployeeShape but not of type ProfessorShape . Intuitively, in our example, the employees of the institution that are not professors can be seen as students who can, e.g., take courses.
As a final step, we need to specify which nodes of the graph are expected to satisfy selected types. This is done via a specification of target nodes. In the basic case, we can list pairs of nodes and the expected type (shape) names. For example, consider the following target specification: 1 = {(Blake, ProfessorShape), (Cameron, StudentShape)} Intuitively, our KG equipped with the validation rules (P), (E) and (S) validates the targets in 1. Indeed, Cameron satisfies StudentShape because they are explicitly stated as an instance of Student. Since Blake has Alex as a superior and Alex is explicitly stated to be an employee, we have that Blake satisfies EmployeeShape. Given that Blake mentors Cameron, we infer that Blake satisfies ProfessorShape. Unsurprisingly, we can have targets that we don’t expect to be validated by our KG and the above validation rules (under a reasonable validation semantics): this holds, e.g., for = {(Blake, StudentShape)} and = {(Cameron, ProfessorShape)}.
In practice, we want more succinct representations of target specifications. The SHACL standard describes the so-called class and property (domain and range) targets. E.g., with = {(Student, EmployeeShape)} we ask each instance of Student to satisfy EmployeeShape (this requirement will clearly be violated in our KG).
Let’s consider the 2-valued supported model semantics of Corman et at. [
Consider the knowledge graph obtained by dropping the node Alex, i.e., deleting the class membership and property assertions that involve Alex. Then a total shape assignment becomes possible: simply assign StudentShape to Cameron and assign ProfessorShape and EmployeeShape to Drew. In fact, this is the only assignment possible. However, this situation is questionable because the knowledge graph states that Drew supervises themselves, which in turn causes an unfounded inference: Drew is an employee because Drew is an employee. Thus this graph validates the target specification = {(Drew, ProfessorShape)} despite the absence of evidence that Drew is an employee in the organization. The two problems that were discussed in this example are addressed by the well-founded semantics for SHACL that we discuss here.
We now recall the well-founded semantics for propositional logic programs with negation [
A (3-valued) interpretation is any set of literals such that {, ¬} ̸⊆ for any . Intuitively, if is a propositional atom such that ∈ , then is true in . If ¬ ∈ , then is false in . If neither ∈ nor ¬ ∈ , then the truth value of is undefined in .
A set of propositional atoms is called an unfounded set w.r.t. an interpretation and a program , if at least one of the following holds for all rules ∈ : (i) head( ) ̸∈ , (ii) there is a positive literal ∈ body( ) such that ∈ or ¬ ∈ , or (iii) there is a negative literal ¬ ∈ body( ) such that ∈ .
For any program and interpretation , there is a unique ⊆ -maximal unfounded set w.r.t. and , which we denote (). For a program , we define a pair and of operators that map interpretations to interpretations as follows: () = {head( ) | body( ) ⊆ , ∈ } () = () ∪ {¬ | ∈ ()} Intuitively, by applying the operator on an interpretation , we augment with some new literals: (i) first we include () that contains immediate consequences of the rules in and the literals in , and then (ii) we add the negation of all atoms that can be safely assumed false according to (). The operator is monotonic, i.e., (1) ⊆ (2) holds whenever 1 ⊆ 2. Thus has the least fixpoint lfp( ) which we call the well-founded model of , and denote it by WFS ( ). In more detail, we can compute WFS ( ) by considering the sequence 0, 1, . . . with 0 = ∅ and = (− 1) for > 0. Due to the monotonicity of , this sequence reaches a such that +1 = . Then WFS ( ) = .
Example 2. Consider the program consisting of the following rules: ← , ← , ← ← ¬ ← ¬ Let us compute WFS ( ). We start with 0 = ∅. We have (0) = ∅ and (0) = {, }. Thus 1 = (0) = {¬, ¬}. To compute 2, first note that (1) = {} and (1) = {, }. Then 2 = (1) = {, ¬, ¬}. Observe that (2) = {, } and (2) = {}, and thus 3 = 2. Hence WFS ( ) = {, ¬, ¬}.
We recall the (abstract) syntax of SHACL constraints, mainly following the approach in [
::= | ∘ | ∪ | * where ∈ N±prop.
A data graph is a pair = (Δ , · ), where Δ ⊆ Nnode is a set of nodes (called domain), and · is a function that assigns to every class name ∈ Nclass some set of nodes ⊆ Δ , and to every property name ∈ Nprop some binary relation ⊆ Δ × Δ . For a property name , we let (− ) = {(′, ) | (, ′) ∈ }. Furthermore, the function · is extended to all property paths as follows: (1 ∘ 2) = (1) ∘ (2) (1 ∪ 2) = (1) ∪ (2)
(* ) = ( )* SHACL constraints. A shape expression is an expression built according to the following grammar:
::= | | ¬ | | ¬ | ∧ | ∨ | | ∃. where ∈ Nnode, ∈ Nclass, ∈ Nshape, ∈ Nvar, and is a complex path. A shape constraint is an expression of the form ← , where ∈ Nshape and is a shape expression. In the following, when considering a set of shape constraints, we always require that (a) 1 = 2 for any pair ← 1 and ← 2 of shape constraints in , and (b) for every shape name that appears in , there is such that ← ∈ . The above just says that every shape name that appears in has exactly one “definition”. Concretely, for such a constraint set and a shape name that appears in , we let () denote the unique such that ← ∈ . A shape expression is ground if it contains no variables. In what follows we only consider ground shape expressions, with a small exception in Section 5 where variables are used as an auxiliary tool to obtain a translation into logic programs. Note that the SHACL standard does not allow variables in shape expressions. We also note that the syntax above does not support property pair equality, property pair disjointness, cardinality constraints, and negation of complex expressions; these features are described in the W3C standard, but we omit them here for presentation reasons (they will be added and discussed in the extended version of this paper).
A target is a pair (ℓ, ), where ℓ ∈ Nnode ∪ Nclass ∪ N±prop and ∈ Nshape. A SHACL document
is a pair (, ), where is a set of shape constraints and is a set of targets. We will next
discuss the validation of a graph against a SHACL document (, ). For this we require that
the nodes that explicitly appear in or are also included in the domain Δ .
Supported model semantics. We present next the basic 2-valued semantics of recursive
SHACL due to Corman et al. [
Example 3. Consider a SHACL document (, ) consisting of the following: = {1 ← ∃ .¬, 2 ← ¬ 1, 3 ← ∧ ¬4, 4 ←
∧ ¬3, 5 ← ∃ .5} = {(, 1), (, 2), (, 5)} Consider a data graph with Δ = {, } and = {}
= {} = {(, )} = {(, )} It easy to see that is valid against (, ), which is witnessed, e.g., by the shape assignment such that (1) = (5) = {}, (2) = (3) = {}, (4) = ∅. This example already illustrates a drawback of the supported model semantics: is inferred to satisfy 5 because it has an -connection to a node that satisfies 5. However, has only a singe -connection to itself, i.e., we have self-justification.
Consider the targets 1 = {(, 3)}, 2 = {(, 4)}, 3 = {(, 3), (, 4)}. Observe that is valid against (, 1) and (, 2) individually, but does not validate 3 as we cannot assign both 3
⌈⌉ = { ∈ Δ | ¬() ̸∈ } ⌈¬⌉ = { ∈ Δ | () ̸∈ } [] = {} [] = { | ∈ } [¬] = { | ∈ Δ ∖ } [ 1 ∧ 2] = [ 1] ∩ [ 2] [ 1 ∨ 2] = [ 1] ∪ [ 2] [∃. ] = { | ∃′ : (, ′) ∈ ∧ ′ ∈ [ ]} and 4 to in a single shape assignment. This phenomenon could be undesired in certain situations: when a stronger notion of validation is desired, we may expect that a graph validates ′ ∪ ′′ whenever it validates ′ and ′′. The well-founded semantics introduced next has this feature.
Note that by introducing an inconsistency in , e.g., by adding the constraint 6 ← ¬ 6, we
lose the existence of a shape assignment, and thus no target gets validated, including = ∅.
This is partially resolved by considering a 3-valued supported model semantics, which does
not require determining the truth value of all shape names [
We are now ready to define a well-founded semantics for SHACL. We do this by adapting the
notion of unfounded sets and fixpoint computations from [
A shape atom is an expression of the form (), where ∈ Nshape and ∈ Nnode. A negated shape atom is an expression ¬(), where () is an atom. A (shape) literal is a possibly negated shape atom. A (3-valued) interpretation (for SHACL constraints) is any set of shape literals such that there is no () ∈ with ¬() ∈ . Intuitively, an atom () ∈ means that there is a justification that holds at , a literal ¬() ∈ means that there is no reason for to hold at , while {(), ¬()} ∩ = ∅ corresponds to the case where the the satisfaction of at is undefined . For a set of shape atoms, let ¬. = {¬() | () ∈ }.
Definition 1. For a given graph and an interpretation , we define two functions ⌊·⌋ and ⌈·⌉ that map every shape expression to a set of nodes. These functions are defined in Figure 3. Assume a data graph and a constraint ← . Suppose we “believe” a set of shape literals, i.e., we assume that all literals in are true. Then ⌊ ⌋ and ⌈ ⌉ return us the nodes of where is certainly true and where is possibly true, respectively. Thus ⌊ ⌋ can be used to infer positive shape literals: if ∈ ⌊ ⌋, then we can infer (). We can use ⌈ ⌉ to infer negative information: if ̸∈ ⌈ ⌉, then we can infer ¬(). These inferences are formalized next. Definition 2. Assume a data graph and a set of constraints. We define an operator ,(· ) that maps interpretations into interpretations as follows:
,() = {() | ← ∈ , ∈ ⌊ ⌋} We are now ready to define the notion of an unfounded set of shape atoms.
Definition 3 (Unfounded set). Assume an interpretation , a data graph , and a set of constraints. A set of shape atoms is called an unfounded set w.r.t. , and , if ̸∈ ⌈()⌉∪¬. for all () ∈ .
Assume a data graph , a set of shape atoms, and suppose we “believe” a set of shape literals. Intuitively, the atoms in form an unfounded set (and can thus be simultaneously set to false) if none of the shape atoms () ∈ can possibly be implied by the associated constraint, assuming the negation of the atoms in holds (in addition to being true).
The following property follows from the fact that 1 ∪ 2 is an unfounded set w.r.t. , and whenever 1, 2 are two unfounded sets w.r.t. , and .
Proposition 1. Assume an interpretation , a data graph , and a set of constraints. There exists a unique set such that 1. is an unfounded set w.r.t. , and , and 2. there is no ′ ⊃ that is unfounded set w.r.t. , and .
The unique set in the proposition above is called the greatest unfounded set w.r.t. , and . Assume a data graph and a set of constraints. We let , be the operator that maps every interpretation to the greatest unfounded set w.r.t. , and . Thus, ,() is the maximal set of shape atoms that we can safely set to false if we assume that the literals in are true. We can now finally define a well-founded semantics for SHACL. We define an operator , that maps interpretations into interpretations as follows: It combines the positive consequences based on the , operator and the negated atoms of the greatest unfounded set produced by the , operator. More formally, we define:
,() = ,() ∪ ¬.,() The above operator is monotone, i.e., ,(1) ⊆ ,(2) whenever 1, 2 are two interpretations with 1 ⊆ 2. Thus , has the least fixpoint, i.e., there exists such that (i) ,() = , and (ii) there is no ′ ⊂ with ,(′) = ′. We use WFS (, ) to denote the least fixpoint of ,, and call it the well-founded model of and . WFS (, ) can be obtained by constructing a sequence 0, 1, 2, . . . such that 0 = ∅ and +1 = ,() until eventually an index is reached were = +1. Then WFS (, ) = .
We can now define validation under the well-founded semantics. We say a graph is valid against a SHACL document (, ) (under the well-founded semantics), if for all (ℓ, ) ∈ we have: • if ℓ is a node ∈ Nnode, then () ∈ WFS (, ), • if ℓ is a class name , then () ∈ WFS (, ) for all ∈ , • if ℓ is a property name , then () ∈ WFS (, ) for all with (, ) ∈ , • if ℓ = − for ∈ Nprop, then () ∈ WFS (, ) for all with (, ) ∈ . Example 4. Consider the data graph and the constraint set from Example 1. It is not dififcult to check that WFS (, ) contains ProfessorShape(Blake), StudentShape(Cameron),
ProfessorShape is undetermined, which is intuitive as discussed in Example 1. For the remaining shape atoms over the signature of and , we have that WFS (, ) contains their negation. Thus is valid against (, {(Blake, ProfessorShape)}) but not valid w.r.t. (, {(Drew , ProfessorShape)}).
Assume a graph and a set of constraints. We show how to compute a propositional logic program , from and such that the well-founded model of , corresponds to the well-founded model of and . We define our target program as , = ⋃︀← ∈ , , where each , is defined as follows.
Assume a constraint ← . First, perform the following replacement in exhaustively until no further replacement is possible: find a position in where a negative shape literal ¬ occurs, and replace ¬ by a fresh variable ¬. Second, perform the following replacement in exhaustively: find a position in where a positive shape literal occurs, and replace by a fresh variable . After these steps, we have that the shape expression ′ that is produced from has a tuple of variables ⃗ = (1¬1 , . . . ,
¬ , ++11 , . . . , ). Then the program , consists of the propositional rule () ← ¬ 1(1), . . . , ¬(), +1(+1), . . . , () for every node and every node tuple ⃗ = (1, . . . , ) such that ∈ ( ′[⃗/]),∅. Here [⃗/⃗] denotes the shape ⃗ expression that is obtained from by performing the substitution of variables ⃗ by nodes ⃗. Proposition 2. If is a graph and is a constraint set, then WFS (, ) = WFS (,). The size of , is exponential in the size of and , but it is only polynomial in case the number of shape names in every constraint is bounded by a constant.
Note that, for a given ← , the relevant node tuples (, 1, . . . , ) above can be computed
by posing a single SPARQL query over , in a similar way as in [
In this paper we have defined a well-founded semantics for SHACL constraints with cyclic
dependencies. This semantics is not only intuitive and based on well-established principles
in logic programming and deductive databases, but it also has advantages over the previous
approaches (based on supported and stable models) in terms of semantic and computational
properties, i.e., it avoids unfounded justifications and is tractable. We note that our semantics
has a direct connection to the so-called cautious validation under the 3-valued stable model
semantics in [
We have also established a connection between the SHACL semantics introduced here and
the well-founded semantics for logic programs. We are currently working on an implementation
of a SHACL validator that directly exploits this connection: Given a graph and a constraint
set , it issues SPARQL queries over in order to compute a propositional logic program ,,
which can then be sent to a dedicated reasoner to compute the well-founded model of ,.
Our initial experiments using the DLV engine [
There are many research questions for future work. For instance, the computational
complexity of satisfiability and implication of SHACL constraints under the well-founded semantics
is a natural next topic for investigations. Some initial results in this area for the semantics
introduced previously were presented in [
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. It was also partially supported by the Austrian Science Fund (FWF) projects P30360 and P30873, and by the Vienna Business Agency’s project CoRec.