SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques

• URL: http://arxiv.org/abs/2507.12286v1
• Date: Wed, 16 Jul 2025 14:38:27 GMT
• Title: SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques
• Authors: Anouk Oudshoorn, Magdalena Ortiz, Mantas Simkus,
• Abstract summary: SHACL is a constraint language that treats the data as complete and must be validated under the closed-world assumption.<n>We advocate a semantics for SHACL validation in the presence of major core universal models.<n>We show that even very simple features make the problem EXPTIME-complete, and PTIME-complete in data complexity.
• Score: 6.882042556551609
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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-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.

Related papers

• KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering [64.62317305868264]
  We present textbfKBQA-R1, a framework that shifts the paradigm from text imitation to interaction optimization via Reinforcement Learning.<n>Treating KBQA as a multi-turn decision process, our model learns to navigate the knowledge base using a list of actions.<n>Experiments on WebQSP, GrailQA, and GraphQuestions demonstrate that KBQA-R1 achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-12-10T17:45:42Z)
• Subject-Event Ontology Without Global Time: Foundations and Execution Semantics [51.56484100374058]
  The formalization includes nine axioms (A1-A9), ensuring the correctness of executable: monotonicity of history (I1), acyclicity of causality (I2), traceability (I3)<n>The formalization is applicable to distributed systems, microservice architectures, DLT platforms, and multiperspectivity scenarios (conflicting facts from different subjects)<n>Special attention is given to the model-based approach (A9): event validation via schemas, actor authorization, automatic construction of causal chains (W3) without global time.
  arXiv  Detail & Related papers  (2025-10-20T19:26:44Z)
• Hierarchical Self-Supervised Representation Learning for Depression Detection from Speech [51.14752758616364]
  Speech-based depression detection (SDD) is a promising, non-invasive alternative to traditional clinical assessments.<n>We propose HAREN-CTC, a novel architecture that integrates multi-layer SSL features using cross-attention within a multitask learning framework.<n>The model achieves state-of-the-art macro F1-scores of 0.81 on DAIC-WOZ and 0.82 on MODMA, outperforming prior methods across both evaluation scenarios.
  arXiv  Detail & Related papers  (2025-10-05T09:32:12Z)
• Re:Form -- Reducing Human Priors in Scalable Formal Software Verification with RL in LLMs: A Preliminary Study on Dafny [68.00108157244952]
  Large Language Models (LLMs) trained with Reinforcement Learning (RL) face a significant challenge: their verification processes are neither reliable nor scalable.<n>A promising yet largely uncharted alternative is formal language-based reasoning.<n>Grounding LLMs in rigorous formal systems where generative models operate in formal language spaces (e.g., Dafny) enables the automatic and mathematically provable verification of their reasoning processes and outcomes.
  arXiv  Detail & Related papers  (2025-07-22T08:13:01Z)
• UniHR: Hierarchical Representation Learning for Unified Knowledge Graph Link Prediction [59.84402324458322]
  Real-world knowledge graphs (KGs) contain not only standard triple-based facts, but also more complex, heterogeneous types of facts.<n>We propose UniHR, a learning framework that unifies hyper-relational KGs, temporal KGs, and nested factual KGs into triple-based representations.<n>Experiments on 9 datasets across 5 types of KGs demonstrate the effectiveness of UniHR and highlight the strong potential of unified representations.
  arXiv  Detail & Related papers  (2024-11-11T14:22:42Z)
• LaSagnA: Language-based Segmentation Assistant for Complex Queries [39.620806493454616]
  Large Language Models for Vision (vLLMs) generate detailed perceptual outcomes, including bounding boxes and masks. In this study, we acknowledge that the main cause of these problems is the insufficient complexity of training queries. We present three novel strategies to effectively handle the challenges arising from the direct integration of the proposed format.
  arXiv  Detail & Related papers  (2024-04-12T14:40:45Z)
• WiCE: Real-World Entailment for Claims in Wikipedia [63.234352061821625]
  We propose WiCE, a new fine-grained textual entailment dataset built on natural claim and evidence pairs extracted from Wikipedia. In addition to standard claim-level entailment, WiCE provides entailment judgments over sub-sentence units of the claim. We show that real claims in our dataset involve challenging verification and retrieval problems that existing models fail to address.
  arXiv  Detail & Related papers  (2023-03-02T17:45:32Z)
• Relational Action Bases: Formalization, Effective Safety Verification, and Invariants (Extended Version) [67.99023219822564]
  We introduce the general framework of relational action bases (RABs) RABs generalize existing models by lifting both restrictions. We demonstrate the effectiveness of this approach on a benchmark of data-aware business processes.
  arXiv  Detail & Related papers  (2022-08-12T17:03:50Z)
• Label-Descriptive Patterns and their Application to Characterizing Classification Errors [31.272875287136426]
  State-of-the-art deep learning methods achieve human-like performance on many tasks, but make errors nevertheless. Characterizing these errors in easily interpretable terms gives insight into whether a model is prone to making systematic errors, but also gives a way to act and improve the model. In this paper we propose a method that allows us to do so for arbitrary classifiers by mining a small set of patterns that together succinctly describe the input data that is partitioned according to correctness of prediction.
  arXiv  Detail & Related papers  (2021-10-18T19:42:21Z)
• Exploring Decomposition for Table-based Fact Verification [18.584226291619217]
  We improve fact verification by decomposing complex statements into simpler subproblems. Our proposed approach achieves the new state-of-the-art performance, an 82.7% accuracy, on the TabFact benchmark.
  arXiv  Detail & Related papers  (2021-09-22T20:15:05Z)
• Toward the Understanding of Deep Text Matching Models for Information Retrieval [72.72380690535766]
  This paper aims at testing whether existing deep text matching methods satisfy some fundamental gradients in information retrieval. Specifically, four attributions are used in our study, i.e., term frequency constraint, term discrimination constraint, length normalization constraints, and TF-length constraint. Experimental results on LETOR 4.0 and MS Marco show that all the investigated deep text matching methods satisfy the above constraints with high probabilities in statistics.
  arXiv  Detail & Related papers  (2021-08-16T13:33:15Z)
• SHACL Satisfiability and Containment (Extended Paper) [6.308539010172308]
  The Shapes Constraint Language (SHACL) is a recent W3C recommendation language for validating RDF data. In this paper, we undertake a thorough study of different features of non-recursive SHACL by providing a translation to a new first-order language, called SCL. We study the interaction of SHACL features in this logic and provide the detailed map of decidability and complexity results of the aforementioned decision problems for different SHACL sublanguages.
  arXiv  Detail & Related papers  (2020-08-31T14:52:03Z)
• Closed-Form Expressions for Global and Local Interpretation of Tsetlin Machines with Applications to Explaining High-Dimensional Data [7.05622249909585]
  We propose closed-form expressions for understanding why a TM model makes a specific prediction (local interpretability) We also introduce expressions for measuring the importance of feature value ranges for continuous features. For both classification and regression, our evaluation show correspondence with SHAP as well as competitive prediction accuracy in comparison with XGBoost, Explainable Boosting Machines, and Neural Additive Models.
  arXiv  Detail & Related papers  (2020-07-27T21:47:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.