Satisfiability and Containment of Recursive SHACL

• URL: http://arxiv.org/abs/2108.13063v1
• Date: Mon, 30 Aug 2021 08:51:03 GMT
• Title: Satisfiability and Containment of Recursive SHACL
• Authors: Paolo Pareti, George Konstantinidis, Fabio Mogavero
• Abstract summary: The Shapes Constraint Language (SHACL) is the recent W3C recommendation language for validating RDF data, by verifying certain shapes on graphs. Previous work has largely focused on the validation problem and the standard decision problems of satisfiability and containment. We provide a comprehensive study of the different features of SHACL, by providing a translation to a new first-order language, called SCL, that precisely captures the semantics of SHACL. We also present MSCL, a second-order extension of SCL, which allows us to define, in a single formal logic framework, the main
• Score: 4.8986598953553555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Shapes Constraint Language (SHACL) is the recent W3C recommendation language for validating RDF data, by verifying certain shapes on graphs. Previous work has largely focused on the validation problem and the standard decision problems of satisfiability and containment, crucial for design and optimisation purposes, have only been investigated for simplified versions of SHACL. Moreover, the SHACL specification does not define the semantics of recursively-defined constraints, which led to several alternative recursive semantics being proposed in the literature. The interaction between these different semantics and important decision problems has not been investigated yet. In this article we provide a comprehensive study of the different features of SHACL, by providing a translation to a new first-order language, called SCL, that precisely captures the semantics of SHACL. We also present MSCL, a second-order extension of SCL, which allows us to define, in a single formal logic framework, the main recursive semantics of SHACL. Within this language we also provide an effective treatment of filter constraints which are often neglected in the related literature. Using this logic we provide a detailed map of (un)decidability and complexity results for the satisfiability and containment decision problems for different SHACL fragments. Notably, we prove that both problems are undecidable for the full language, but we present decidable combinations of interesting features, even in the face of recursion.

Related papers

• SHACL2FOL: An FOL Toolkit for SHACL Decision Problems [0.4895118383237099]
  We introduce SHACL2FOL, the first automatic tool that translates SHACL documents into FOL sentences. The tool computes the answer to the two static analysis problems of satisfiability and containment. It also allow to test the validity of a graph with respect to a set of constraints.
  arXiv  Detail & Related papers  (2024-06-12T09:20:25Z)
• 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)
• Spurious Feature Eraser: Stabilizing Test-Time Adaptation for Vision-Language Foundation Model [86.9619638550683]
  Vision-language foundation models have exhibited remarkable success across a multitude of downstream tasks due to their scalability on extensive image-text paired data. However, these models display significant limitations when applied to downstream tasks, such as fine-grained image classification, as a result of decision shortcuts''
  arXiv  Detail & Related papers  (2024-03-01T09:01:53Z)
• Open-Vocabulary Segmentation with Semantic-Assisted Calibration [73.39366775301382]
  We study open-vocabulary segmentation (OVS) through calibrating in-vocabulary and domain-biased embedding space with contextual prior of CLIP. We present a Semantic-assisted CAlibration Network (SCAN) to achieve state-of-the-art performance on open-vocabulary segmentation benchmarks.
  arXiv  Detail & Related papers  (2023-12-07T07:00:09Z)
• Triplet Contrastive Learning for Unsupervised Vehicle Re-identification [55.445358749042384]
  Part feature learning is a critical technology for fine semantic understanding in vehicle re-identification. We propose a novel Triplet Contrastive Learning framework (TCL) which leverages cluster features to bridge the part features and global features.
  arXiv  Detail & Related papers  (2023-01-23T15:52:12Z)
• A Review of SHACL: From Data Validation to Schema Reasoning for RDF Graphs [3.274290296343038]
  We present an introduction and a review of the Shapes Constraint Language (SHACL), the W3C recommendation language for validating RDF data. A SHACL document describes a set of constraints on RDF nodes, and a graph is valid with respect to the document if its nodes satisfy these constraints.
  arXiv  Detail & Related papers  (2021-12-02T17:28:45Z)
• Fixpoint Semantics for Recursive SHACL [10.896533521085784]
  SHACL is a W3C-proposed language for expressing structural constraints on RDF graphs. In this paper, we argue that for defining and studying semantics of SHACL, lessons can be learned from years of research in non-monotonic reasoning.
  arXiv  Detail & Related papers  (2021-09-17T01:46:09Z)
• Anti-aliasing Semantic Reconstruction for Few-Shot Semantic Segmentation [66.85202434812942]
  We reformulate few-shot segmentation as a semantic reconstruction problem. We convert base class features into a series of basis vectors which span a class-level semantic space for novel class reconstruction. Our proposed approach, referred to as anti-aliasing semantic reconstruction (ASR), provides a systematic yet interpretable solution for few-shot learning problems.
  arXiv  Detail & Related papers  (2021-06-01T02:17:36Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
  This paper explores useful modifications of the recent development in contrastive learning via novel probabilistic modeling. We derive a particular form of contrastive loss named Joint Contrastive Learning (JCL)
  arXiv  Detail & Related papers  (2020-09-30T16:24:21Z)
• 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)

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.