Transforming Shape Schemas with Composable Property-Graph Queries (Extended Version)

Philipp Seifer, Daniel Hernández, Ralf Lämmel, Steffen StaabarXiv 2026 · arXiv

TL;DR

This paper introduces a method for statically inferring the schema (or "shape") of a property graph after it has been transformed by a query, without needing to run the query on actual data. By mapping property graphs, schemas, and queries into an intermediate RDF/SHACL/SPARQL layer, the authors leverage powerful Description Logic reasoners to automatically deduce valid output schemas. This provides a foundational tool for building type systems and optimization pipelines in modern graph databases.

What Problem Does This Paper Address?

Graph databases increasingly rely on schema or "shape" languages (like ProGS or PG-Schema) to ensure data quality and establish a strict contract between data providers and consumers. However, when a database executes a graph-to-graph query, the structure of the data changes. Determining the schema of the resulting graph is a major challenge.

While this problem has been solved for RDF graphs using SPARQL queries, doing the same for Property Graphs (PGs) is significantly harder. PGs feature first-class edges with their own identities, labels, and key-value property annotations. Standard reasoning frameworks, such as Description Logics (DL), lack the native constructs to represent these features directly. The authors address this gap by creating an instance-independent reasoning procedure that takes an input schema and a transforming query, and outputs a guaranteed valid schema for any resulting graph.

Methods

Instead of inventing a completely new description logic to handle property graphs, the authors introduce a clever intermediate mapping layer. They translate the property graph problem down to a well-studied RDF/SHACL infrastructure, solve the inference problem there, and map the results back.

Schematic overview of the proposed solution mapping the PG layer to an intermediate RDF layer for reasoning.

As shown in Figure 3, the method relies on three core mappings:

  1. PG-to-RDF Data Mapping: Reifies first-class edges and properties into standard RDF triples using special meta-relations (m:nte for node-to-edge and m:etn for edge-to-node).
  2. sProGS-to-SHACL Shape Mapping: Translates property graph schemas (sProGS) into SHACL shapes, which are internally represented as $\mathcal{ALCHOI}$ Description Logic axioms.
  3. SGCQ-to-ECCQ Query Mapping: Converts a subset of G-CORE queries (Simple G-CORE Queries) into Extended Conjunctive CONSTRUCT Queries (ECCQ) in SPARQL. This is highly non-trivial because G-CORE queries preserve labels and properties by default, whereas SPARQL requires everything to be explicitly constructed. The authors handle this by introducing generic copy patterns and filters.

Once mapped, they extend an existing shape inference algorithm to handle these generic patterns and use the off-the-shelf HermiT DL reasoner to compute the final output schema.

Datasets

Because standard benchmarks for property graph schema inference do not yet exist, the authors evaluated their implementation using synthetically generated data. They created a validation framework that produced 100,000 random problem instances (pairs of input shapes and queries), categorized into four structural scenarios:

  • small: Minimal shapes and straightforward query patterns.
  • deep: Deeply nested shape constraints.
  • wide: Shapes containing complex logical conjunctions and disjunctions.
  • large: A high total number of input shapes to test scalability.

Key Insights and Ideas

  • Decoupling Reification from Reasoning: Trying to bake property-graph semantics directly into a reasoner makes the logic overly complex and inefficient. Moving the complexity to an intermediate RDF reification layer allows the framework to utilize highly optimized, standard DL reasoners.
  • The "Default Persistence" Challenge: In SPARQL CONSTRUCT, you only get the triples you explicitly define in the template. In G-CORE, graph properties persist by default unless explicitly removed. Bridging this semantic gap required a sophisticated query mapping that dynamically generates "copy patterns" for unknown properties.
  • Instance-Independent Guarantees: Because the inference happens purely at the schema and query level, the computed output schema applies to all potential graphs originating from any valid input graph. This makes it highly resilient to frequent database updates.

Key Results

  • 100% Correctness: Across all 100,000 randomly generated test cases, the framework achieved zero validation failures, empirically validating the soundness of their metatheory.
  • Feasible Runtime Performance: Despite the overhead of reifying edges and running description logic reasoning, the median inference times per sample on commodity hardware (Ryzen 7 9700X) were remarkably low:
  • Small: 11.00 ms
  • Deep: 25.00 ms
  • Wide: 29.50 ms
  • Large: 36.00 ms

Limitations and Future Work

  • Query Language Restrictions: The current approach is limited to a conjunctive subset of G-CORE. It does not yet support non-conjunctive operators like UNION or optional matches.
  • Type-Level Constraints: While the system supports specific generic copy patterns, arbitrary constraints on type-level variables (variables that bind to concepts or labels themselves) cannot be easily encoded in Description Logics.
  • Execution Efficiency vs. Formal Ease: The mapping favors formal ease of use and mathematical proof over raw database execution efficiency. If these SPARQL mappings were actually executed on an RDF triple store rather than being used for static analysis, the reification layer would likely introduce significant performance penalties.

Summary updated

Abstract

Property graphs may be constrained by schemas that inform both query engines and human users about the shape of valid data, enforcing a contract between data provider and consumer. Composable property-graph queries transform input graphs into output graphs. Then, the question arises of which schema can be expected after one (or several) transformation steps. We investigate how schema constraints can be inferred given an input schema and a transforming query. Specifically, we propose a reasoning procedure that, given an input schema in ProGS and a query in G-CORE infers an output schema. Since graph updates will happen frequently, our inference procedure does not rely on graph instances, such that the computed output schema applies to all graphs originating from any input graph complying with the input schema. Related work has addressed this problem for SPARQL CONSTRUCT queries, encoding it in Description Logics (DLs) so that the output schema is entailed by axioms inferred from input schema and queries. Property graphs and their queries, however, complicate the matter, as property graphs feature label and property annotations as well as first-class edges. Thus, reification has to be used in one way or another, though available DLs lack the means to encode such features directly. We approach this novel challenge via a family of mappings for i) property graphs reified in RDF, aligned with ii) a mapping from ProGS to SHACL and iii) a mapping from G-CORE to SPARQL CONSTRUCT queries. In this manner, schema inference for property graphs becomes manageable, as we break apart the problem through the extra mapping layer and utilize efficient DL reasoners. We develop the metatheory regarding the soundness of inferred schema constraints and the semantic equivalence of mapped schemas and queries.
BibTeX
@misc{seifer2026transforming,
  author = {Philipp Seifer and Daniel Hernández and Ralf Lämmel and Steffen Staab},
  title = {{Transforming Shape Schemas with Composable Property-Graph Queries (Extended Version)}},
  year = {2026},
  eprint = {2606.14309},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.14309},
}

Loading related content...

Figure