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.
As shown in Figure 3, the method relies on three core mappings:
- PG-to-RDF Data Mapping: Reifies first-class edges and properties into standard RDF triples using special meta-relations (
m:ntefor node-to-edge andm:etnfor edge-to-node). - sProGS-to-SHACL Shape Mapping: Translates property graph schemas (sProGS) into SHACL shapes, which are internally represented as $\mathcal{ALCHOI}$ Description Logic axioms.
- 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
UNIONor 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