SHACL Satisfiability and Containment (Extended Paper)

• URL: http://arxiv.org/abs/2009.09806v2
• Date: Thu, 5 Nov 2020 10:55:19 GMT
• Title: SHACL Satisfiability and Containment (Extended Paper)
• Authors: Paolo Pareti and George Konstantinidis and Fabio Mogavero and Timothy J. Norman
• Abstract summary: 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.
• Score: 6.308539010172308
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Shapes Constraint Language (SHACL) is a recent W3C recommendation language for validating RDF data. Specifically, SHACL documents are collections of constraints that enforce particular shapes on an RDF graph. Previous work on the topic has provided theoretical and practical results for the validation problem, but did not consider the standard decision problems of satisfiability and containment, which are crucial for verifying the feasibility of the constraints and important for design and optimization purposes. 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, that precisely captures the semantics of SHACL w.r.t. satisfiability and containment. 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. Notably, we prove that both problems are undecidable for the full language, but we present decidable combinations of interesting features.

Related papers

• Benchmarking Complex Instruction-Following with Multiple Constraints Composition [72.82640456309821]
  How to evaluate the ability of complex instruction-following of large language models (LLMs) has become a critical research problem. Existing benchmarks mainly focus on modeling different types of constraints in human instructions while neglecting the composition of different constraints. We propose ComplexBench, a benchmark for comprehensively evaluating the ability of LLMs to follow complex instructions composed of multiple constraints.
  arXiv  Detail & Related papers  (2024-07-04T14:50:45Z)
• C-LLM: Learn to Check Chinese Spelling Errors Character by Character [61.53865964535705]
  We propose C-LLM, a Large Language Model-based Chinese Spell Checking method that learns to check errors Character by Character. C-LLM achieves an average improvement of 10% over existing methods.
  arXiv  Detail & Related papers  (2024-06-24T11:16:31Z)
• 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)
• 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)
• Satisfiability and Containment of Recursive SHACL [4.8986598953553555]
  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
  arXiv  Detail & Related papers  (2021-08-30T08:51:03Z)
• 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)
• The Curse of Performance Instability in Analysis Datasets: Consequences, Source, and Suggestions [93.62888099134028]
  We find that the performance of state-of-the-art models on Natural Language Inference (NLI) and Reading (RC) analysis/stress sets can be highly unstable. This raises three questions: (1) How will the instability affect the reliability of the conclusions drawn based on these analysis sets? We give both theoretical explanations and empirical evidence regarding the source of the instability.
  arXiv  Detail & Related papers  (2020-04-28T15:41:12Z)

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.