SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques
Anouk Oudshoorn, Magdalena Ortiz, Mantas Šimkus · 2025
Read SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques by Anouk Oudshoorn, Magdalena Ortiz, Mantas Šimkus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12286.txt.
Introduction
Anouk Oudshoorn, Magdalena Ortiz, and Mantas Šimkus study what happens when two web data standards with opposite instincts are forced to work together. SHACL checks data against constraints, treating the record as complete. OWL instead infers new facts from incomplete data, assuming the world stays open. Combining them is appealing but semantically treacherous.
The authors ground validation in core universal models of the ontology. They give a construction for such models in a rich but tractable description logic. A finite stand-in for the model then powers a rewriting trick: validation with an ontology becomes ordinary validation. Complexity results close the paper. Even simple ontologies push the problem to exponential time in general, though it stays polynomial in the data itself. The work gives the combined standards a firm footing.
Catalog record
| CREATOR | Anouk Oudshoorn, Magdalena Ortiz, Mantas Šimkus |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 153 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-12286
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques Anouk Oudshoorn, Magdalena Ortiz, Mantas Šimkus Abstract SHACL and OWL are two prominent W3C standards for managing RDF data. These languages share many features, but they have one fundamental difference: OWL, designed for inferring facts from incomplete data, makes the open-world assumption , whereas SHACL is a constraint language that treats the data as complete and must be validated under the closed-world assumption . The combination of both formalisms is very appealing and has been called for, but their semantic gap is a major challenge, semantically and computationally. In this paper, we advocate a semantics for SHACL validation in the presence of ontologies based on core universal models . We provide a technique for constructing these models for ontologies in the rich data-tractable description logic Horn- 𝒜 ℒ 𝒞 ℋ ℐ 𝒬 \mathcal{ALCHIQ} . Furthermore, we use a finite representation of this model to develop a rewriting technique that reduces SHACL validation in the presence of ontologies to standard validation. Finally, we study the complexity of SHACL validation in the presence of ontologies, and show that even very simple ontologies make the problem ExpTime -complete, and PTime -complete in data complexity. Keywords SHACL, OWL, Horn- \mathcal{ALCHIQ} , Validation, Rewriting, Complexity † † ©2025. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0 1 Introduction The Shape Constraint Language (SHACL) shacl and Web Ontology Language (OWL) owl are two prominent W3C standards for managing RDF data, the graph-based data model of the Web rdf . These standards are based on fundamentally different assumptions and designed to be complementary. OWL was standardised shortly after RDF, with the key aim of enhancing RDF datasets with domain knowledge that enables the inference of missing facts from potentially incomplete data graphs. OWL and its profiles are based on Description Logics (DLs) DBLP:books/daglib/0041477 and, like other classical logics, make the open-world assumption (OWA) , which intuitively means that the data only presents an incomplete description of the domain of interest: it asserts facts that are known to be true, but does not rule out that additional facts may also be true, as long as they are consistent with the current world description. OWL has been adopted in a wide range of applications over the years, and thousands of OWL ontologies have been developed. SHACL, in contrast, was created for a different purpose: to describe and validate constraints on datasets. The main task of interest is validation of a given a set of constraints paired with a selection of target nodes or concepts from a given graph. Unlike OWL, SHACL operates under the closed-world assumption (CWA): it assumes that the given data graph is complete, and validators evaluate the constraints over the input graph as is. A natural question is how to do validation in the presence of both OWL ontologies and SHACL constraints. That is, if we have a possibly incomplete graph and ontological knowledge that implies additional facts, can we validate given SHACL constraints over graphs containing the implied facts? Consider as an example a toy database of pet owners containing the facts \mathit{hasPetBird}(\mathit{linda},\mathit{blu}),\mathit{hasPet}(\mathit{john},\mathit{ace}) ; the simple constraint \mathit{petOwnerShape}\leftarrow\exists\mathit{hasPet.\top} , which says that everyone that has a pet is a pet owner; and the target pet owners \mathit{linda} and \mathit{john} . Clearly, we would like to leverage the knowledge that all pet birds are pets , written as \mathit{hasPetBird}\sqsubseteq\mathit{hasPet} in description logics, which allows us to validate both targets. This type of validation is very natural, even more so in the light of the huge amount of ontologies that are already being used for describing data on the web. It is in fact envisioned in the W3C SHACL specification, which calls for graph validation in the presence of OWL entailment ( shacl , Section 1.5) , but unfortunately, does not provide guidance on how to realise this. The first major challenge we must face is that the semantics of SHACL constraints in the presence of ontologies is not obvious, as we must simultaneously account for the open-world semantics of description logics and for the closed-world view of SHACL. The knowledge in the ontology implies additional facts, which can be added to the data graph so that it satisfies all the ontological axioms. All such possible completions are models that must be taken into account according to the traditional OWL/description logics semantics. However, SHACL allows for negation, which makes this certain answer semantics too weak, and quickly results in non validation. Update for example the toy database of pet owners we considered before to \mathit{hasPet}(\mathit{john},\mathit{ace}),\mathit{Hamster}(\mathit{ace}) , but with the constraint \mathit{petOwnerShape}\leftarrow\exists\mathit{hasPet}.\top\land\forall\mathit{hasPet}.\lnot\mathit{Dangerous} . For \mathit{john} to validate the \mathit{petOwnerShape} , it is not enough to make explicit in the ontology that hamsters are not dangerous animals; it should also be enforced that any possible pet \mathit{john} might have cannot be dangerous. For lightweight DLs, fragments of classical Horn logics that cannot express disjunctive information, a universal model can be obtained using standard, database-inspired chase procedures . These models can be used for evaluating conjunctive, navigational and graph queries in the presence of ontologies, see DBLP:conf/rweb/BienvenuO15 ; DBLP:journals/semweb/CalvaneseCKKLRR17 ; DBLP:journals/semweb/CalvaneseGLLPRRRS11 ; DBLP:conf/aaai/EiterOSTX12 ; DBLP:conf/ijcai/OrtizRS11 ; DBLP:journals/japll/Perez-UrbinaMH10 and their references. One of these options, using minimal models of the Skolemnisation of the DL ontology, has been advocated for in the case of integrity constraints DBLP:conf/www/MotikHS07 ; DBLP:conf/esws/SavkovicKL19 . But even such models give very weak semantics in formalisms with negation such as SHACL. Let us for example consider again another version of the toy database containing pet owners: assume it contains the facts \mathit{hasPet}(\mathit{john},\mathit{ace}),\mathit{PetOwner}(\mathit{john}),\mathit{Hamster}(\mathit{ace}) . It is conceivable to find an axiom like \mathit{PetOwner}\sqsubseteq\exists\mathit{hasPet}.\top in the accompanying ontology. Now let the \mathit{onlyHamsterShape} be given by the constraint \mathit{onlyHamsterShape}\leftarrow\forall\mathit{hasPet}.\mathit{Hamster} , which we want to validate for \mathit{john} . This is clearly the case for the original database. It is also true that the given database is already satisfying all given ontology axioms, so it seems there is no reason to change the validation result. However, the minimal model under the Skolem semantics adds a fresh node as a \mathit{hasPet} -child of \mathit{john} , without the label \mathit{Hamster} , changing the validation result to negative. To obtain stronger and more intuitive semantics, and to avoid the problems presented in the previous example, we advocated in ecai2023 for an austere canonical model in which axioms are satisfied minimally, introducing as few successors as possible without losing universality. We showed that for ontologies in DL-Lite R —the logic underlying OWL 2 QL DBLP:conf/rweb/Krotzsch12 —such a model can be represented by a so-called immediate successor function that describes the minimal set of facts that need to be added to satisfy the axioms at a given point of the model construction. The model itself can then be obtained in a deterministic, step-by-step fashion. We extend this construction in Section 3 to the significantly more expressive Horn- \mathcal{ALCHIQ} , one of the largest fragments of OWL that is still contained in Horn logic. Crucially, we show that the resulting model is a core in the traditional database sense. This provides strong evidence in favour of our chosen semantics, since cores are often advocated as the adequate choice