Inferring SHACL Constraints for Results of Composable Graph Queries (Extended Abstract)

Philipp Seifer, Daniel Hernández, Ralf Lämmel, Steffen StaabDescription Logics 2024 · OpenReview

Introduction

In the ecosystem of Knowledge Graphs, particularly those based on RDF, SPARQL CONSTRUCT queries are essential for transforming data between different schemas. To maintain data quality, developers rely on SHACL (Shapes Constraint Language) to define structural requirements. However, when these queries are chained into complex pipelines, the original constraints often become invalid or insufficient for the resulting graph. Manually determining the output shapes for each transformation is a tedious and error-prone task. This paper, presented at the 37th International Workshop on Description Logics (DL 2024), introduces a formal algorithm to automatically infer SHACL constraints for the results of composable graph queries.

Methodology: Reasoning over the Extended Graph

The authors propose a static inference method that translates both SHACL shapes and SPARQL queries into Description Logic (DL) axioms, specifically within the $\mathcal{ALCHOI}$ fragment. The central innovation is the construction of an Extended Graph ($G_{ext}$).

Decomposition of the Extended Graph ($G_{ext}$) into input ($G_{in}$), intermediate ($\dot{G}_{med}$), variable ($G_V$), and output ($\ddot{G}_{out}$) components.

As shown in Figure 5, the extended graph unifies the input data, intermediate variable bindings, and the final output into a single "virtual" structure. This allows a DL reasoner to track the "flow" of properties through the query. The method employs a specific "dot" notation to distinguish between stages:

  • Input ($A$): Original concepts and roles.
  • Intermediate ($\dot{A}$): Concepts filtered or modified by query variables.
  • Output ($\ddot{A}$): The final structure produced by the CONSTRUCT template.

By reasoning over this unified model, the algorithm can identify mappings between input and output parts, inferring whether a constraint like "every Person must have an email" persists or is modified after the transformation.

Key Insights

Unlike dynamic tools that infer shapes from data instances, this approach is static. It operates solely on the query and the schema, allowing for verification before any data is processed. Furthermore, the authors leverage the Closed World Assumption (CWA) inherent in SPARQL queries. Since a query only returns what is explicitly defined in its graph patterns, the algorithm can infer precise definitions for output concepts as intersections of input concepts and query variables.

The algorithm prioritizes soundness over completeness. While it may not capture every possible constraint, every inferred shape is mathematically guaranteed to be correct according to the logic of the transformation.

Results and Future Directions

The paper provides a rigorous formalization of the OutputShapes problem and proves that reasoning over the Extended Graph is logically equivalent to separate reasoning over input and output. The resulting framework successfully splits the inference task into two sub-problems: verifying if a specific shape must exist in the output and generating candidate shapes for testing.

Current limitations include the computational complexity of $\mathcal{ALCHOI}$ reasoning and the focus on a subset of SHACL. Future work aims to expand coverage to more complex features like property paths and non-recursive shapes, as well as optimizing performance for large-scale industrial queries.

Summary updated

BibTeX
@inproceedings{seifer2024inferring,
  author = {Philipp Seifer and Daniel Hernández and Ralf Lämmel and Steffen Staab},
  title = {{Inferring SHACL Constraints for Results of Composable Graph Queries (Extended Abstract)}},
  booktitle = {Description Logics},
  year = {2024},
  url = {https://openreview.net/forum?id=UVwBmlzzvK},
}
Figure