PaperlayerView exact revision on arXiv

Source-linked AI summary

Transformations for Evolving Property Graph Schemas

Gauvain Devillez, Stefania Dumbrava, Angela Bonifati

arXiv:2609.34789v3cs.DB

TL;DR

Property graph schema transformations are often manually specified and difficult to reuse, and systematic support for navigating their large search space remains limited. GRAFT derives reusable, order-constrained meta-transformations and explores a finite meta-graph of schemas. Greedy and naive exploration reach similarity 1.0 across the reported settings, though naive search times out for IBench-Huge at eight candidate schemas.

  • Problem

    Property graph schema transformations are commonly manual and application-specific, while systematic reuse and efficient exploration of the resulting large search space remain limited.

    Source: §1 · pp. 1–2

  • Method

    GRAFT abstracts schema changes into reusable, order-constrained meta-transformations and explores a meta-graph whose vertices are schemas and edges are grounded transformations.

    Source: §1 · p. 2, §6 · p. 12

  • Results

    Greedy and naive exploration reach similarity 1.0 across all reported settings, while naive times out at 8 candidate schemas for IBench-Huge.

    Source: §5.1.2 · p. 10

  • Takeaways & Limitations

    Without pruning, GRAFT is complete; under pruning, its greedy heuristic reaches the target for T-monotone transformation sets.

    Source: §6 · p. 12

    Greedy search can become trapped at a local optimum when a self-loop is favored and the resulting schema cannot be refined under the default semantics.

    Source: §5.2 · p. 12

Abstract

from arXiv · show

Property graph databases are widely used to represent complex and evolving data, yet systematic support for property graph schema evolution remains limited. In practice, schema transformations are typically defined manually, coupled to specific application contexts, and difficult to reuse across schemas or evolution scenarios. We present GRAFT, a logic-based framework that models property graph schema evolution as reusable, order-constrained meta-transformations derived from atomic edits. Schema evolution is formulated as the exploration of a finite meta-graph with schemas as nodes and grounded meta-transformations as edges. To ensure tractability, GRAFT combines similarity-guided search and pruning, guaranteeing duplication-freeness, termination, and correctness. An experimental evaluation on four benchmark and real-world property graph schema evolution scenarios shows that GRAFT efficiently computes high-quality schema transformation sequences. Using greedy exploration, GRAFT reaches the exact target schema on most datasets, producing stable transformation sequences while keeping runtimes low. A qualitative study on both real-world and synthetic large-scale datasets further shows the quality and robustness of the obtained reusable meta-transformations.

Stefania Dumbrava ENSIIE, INRIA, IRIF, SAMOVAR

The reference lists the authors and publication details for “Transformations for Evolving Property Graph Schemas”; the source code and artifacts are available in the GRAFT repository.

Stefania Dumbrava ENSIIE, INRIA, IRIF, SAMOVAR

1 INTRODUCTION

Property graph schema changes are often manually specified and difficult to reuse, while their coupled structure and typing make coordinated edits important. The introduction presents GRAFT as a framework for representing and composing reusable transformations and efficiently exploring candidate schemas.

1 INTRODUCTION

  • Property graph schema transformations are often manually specified, application-specific, and costly to maintain.The introduction motivates systematic reuse as schemas evolve across applications and graph data integration settings.Source: §1 · p. 1
  • Because property graph schemas couple structure and typing, seemingly simple changes can require coordinated edits to avoid inconsistencies.Schemas may also be descriptive or partial, with only some instances conforming and evolving as needed.Source: §1 · p. 1
  • The paper asks whether recurring transformation patterns can be identified, abstracted, and reused to automate property graph schema evolution.The stated aims include reducing manual effort and supporting scalable graph data integration.Source: §1 · p. 2
  • Given source schema S, target schema T, and fixed transformations, the problem is to reach T or otherwise produce a schema T′ maximizing similarity to T.Source: §1 · p. 2
  • GRAFT abstracts concrete changes into reusable meta-transformations with variable substitution and explicit ordering constraints.The patterns can be composed across schemas and evolution scenarios.Source: §1 · p. 2
  • GRAFT models evolution as exploration of candidate schemas and presents algorithms for grounding and enumerating transformations with duplication-freeness and termination guarantees.The paper also analyzes worst-case search and evaluates four iBench scenarios, a Paradise Papers scenario, and a generated large schema; its qualitative study reports stable, reusable meta-transformations.Source: §1 · p. 2

2 RELATED WORK

Prior work addresses mappings, transformations, and schema evolution in relational settings, as well as graph transformations and matching. The paper distinguishes GRAFT by focusing on reusable, ordered transformation patterns over typed property-graph schemas.

2 RELATED WORK

  • Relational model-management work supports mapping creation, compilation, and reuse, but these approaches target relational data or generic meta-models.Meta-mappings were developed to reuse mappings across contexts, including in GAIA.Source: §2 · p. 2
  • Relational schema operators evolve tables and can drop a column independently, whereas property-graph edits must account for typed edge endpoints.For example, redirecting hasModerator must precede removing Moderator; GRAFT encodes such ordering with Start∗/Next∗ relations.Source: §2 · p. 2
  • Instance-driven and learning-based approaches infer mappings, while schema matchers find correspondences rather than ordered executable edit sequences [13, 35].GRAFT could compose and validate candidate correspondences from matchers into reusable transformations.Source: §2 · p. 3
  • Existing graph schema and view approaches support flexible or query-based evolution but do not address systematic reuse or composition of transformations over time.The passage also notes community efforts toward property-graph schema standards, including PG-Schema [5] and PG-Keys.Source: §2 · p. 3
  • GRAFT is presented as the first system to address property graph schema evolution through meta-transformations, with automatic generation and guarantees including termination and correctness.The paper describes its paths as minimal and contrasts its guarantees with prior probabilistic or heuristic-based work.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define property graphs and a core property-graph schema, then specify when graph instances conform to that schema. The treatment uses a finite PG-Schema fragment with functional typing.

3 PRELIMINARIES

  • A property graph is represented as finite vertex and edge sets, an endpoint function, label sets, and property sets.The example is inspired by the LDBC Social Network Benchmark schema [4].Source: §3 · p. 3
  • The paper considers a finite PG-Schema fragment with only node and edge types, endpoint typing, and exactly one schema type per node or edge.Supporting schema constraints is left to future work because it would require extra validity predicates and edit operations.Source: §3 · p. 3
  • A base type pairs a finite label set with a finite record of property keys and data types.An object conforms when its labels match and it has values of the specified types for the record’s properties.Source: §3 · p. 3
  • A core property-graph schema comprises finite node and edge base-type sets and a function assigning each edge type its source and target node types.A graph conforms when every object conforms to exactly one base type and edge endpoints conform to the types specified by the schema.Source: §3 · p. 3

4 PROPERTY GRAPH SCHEMA EVOLUTION

This section presents GRAFT’s finite schema meta-graph and reusable, order-constrained transformations for modeling property-graph schema evolution. It explains how transformations are defined and applied, and how the graph is explored incrementally using target similarity and pruning, including conditions for reachability and guarantees.

4.1 Edit Operations and Meta-Edit Operations

  • Meta-transformations replace schema-specific constants with variables, enabling structural transformation patterns to be grounded and reused across schemas.Grounding assigns variables to source- or target-schema elements subject to operation-specific validity constraints.Source: §4.1 · p. 4

4.2.1 Transformations and Meta-transformations.

  • Start∗ and Next∗ encode admissible starting edits and successor relationships, preserving operation order and ensuring grounded sequences are valid.The ordering rules address cases where edits would otherwise reference symbols already removed or renamed.Source: §4.2.1 · p. 4

4.2.2 Deriving Meta-Transformations.

  • Algorithm 1 enumerates exactly the duplication-free transformation sequences allowed by Start and Next, and terminates with finitely many sequences for finite input schemas.Clique compression groups compatible edits and reduces worst-case derivation complexity from O(n!) to O(2^n).Source: §4.2.2 · p. 6

4.2.3 Transformation generation and execution.

  • A generic validity check models each edit through removed, inserted, and preserved schema elements, testing their disjointness and membership conditions before application.With n distinct grounded edits, clique compression bounds generation and application at O(2^n · n).Source: §4.2.3 · p. 6

4.3 The Meta-Graph Search Space

  • The meta-graph search space is finite but can grow exponentially, making exhaustive exploration infeasible and motivating guided search.Its vertices are schemas and its edges are transformation applications.Source: §4.3 · p. 6

4.3.1 Meta-Graph Construction.

  • The meta-graph connects schemas whenever a grounded meta-transformation produces one from another, and is finite for finite source schemas and transformation sets.Meta-transformations are schema-agnostic when a schema satisfies their instantiation constraints.Source: §4.3.1 · pp. 6–7

4.3.1 Meta-Graph Construction

  • Because grounded edits cannot introduce fresh symbols, the meta-graph is finite; with n distinct edit operations, it has at most 2^n vertices and |M∗| · 2^n edges.Source: §4.3.1 · p. 7

4.3.2 Reaching the target schema

  • An exact transformation exists when the target is reachable through grounded meta-transformations; otherwise, the framework seeks an approximate target whose closeness depends on their expressive power.Source: §4.3.2 · p. 7

4.3.3 Removing duplicated schemas

  • A canonical signature formed from sorted node and edge keys uniquely identifies schemas, preventing duplicate schemas without general graph-isomorphism testing.Node keys include names, labels, and properties; edge keys also incorporate endpoint names.Source: §4.3.3 · p. 7

4.3.4 Evaluating closeness to the target schema

  • Feature-based Jaccard similarity is exact for schema equality, avoids exact graph edit distance’s NP-hardness, and can be weighted to reduce bias from combinatorial features.Features encode names and structural context; MinHash provides an efficient probabilistic estimate for large sets, exact in the limit of large samples.Source: §4.3.4 · pp. 7–8

4.3.5 Guided Search and Space Reduction

  • GRAFT explores incrementally, selecting schemas by random, greedy, weighted-distance, or exhaustive breadth-first strategies, while similarity thresholds and top-k pruning control search growth.The exhaustive strategy reaches any reachable target and finds a shortest sequence but can generate exponentially many schemas; non-exhaustive strategies use beam width β.Source: §4.3.5 · p. 8

4.3.6 An a posteriori cost model for transformations

  • Transformation costs can sum the fractions of graph elements affected by each edit, but predicting per-edit cost statically is difficult because prior edits can change what later edits affect.A cost-aware ordering could combine cost and target similarity, with Dijkstra’s algorithm extracting a minimum-cost path to the approximate target.Source: §4.3.6 · p. 8

4.4 The GRAFT Algorithm

  • GRAFT terminates and returns reachable transformations; without pruning, naive search yields a minimal edit sequence, while greedy search with pruning is optimal for T-monotone transformations.If the target is reachable, the latter returns an exact transformation; returned transformations are lossless when every grounded meta-transformation is lossless.Source: §4.4 · p. 9

5 EXPERIMENTAL EVALUATION

The evaluation tests GRAFT’s search strategies, pruning and beam-width sensitivity, operation reuse, and transformation quality on benchmark, real-world, and large-scale scenarios. Greedy reaches the exact target across tested settings, while qualitative studies examine local-optimum behavior and data-level costs.

5.1.1 Experimental Setup.

  • The quantitative study used four iBench-derived scenarios and IBench-Huge; experiments generally retained the eight most similar schemas per round and used exact Jaccard similarity.Search stopped when best similarity improved by less than 0.01 over five consecutive steps or after six hours.Source: §5 · p. 9, §5.1.1 · p. 10

5.1.2 Experimental Results.

  • Greedy and naive reached normalized similarity 1.0 across settings, but naive timed out with 8 candidates on IBench-Huge.Similarity 1.0 means the resulting schema is identical to the target.Source: §5.1.2 · p. 10, Figure 5 · p. 11
  • Greedy and naive selected stable paths across widths; similarity precision had little impact except that weighted Jaccard penalized missing properties more, while runtime generally grew with candidate count.Naive’s runtime grew most steeply; greedy and naive produced transformations of constant size across pruning and beam widths.Source: §5.1.2 · p. 10, Figure 5 · p. 11, Figure 6 · p. 11
  • Greedy and naive always achieved the best similarity; random and weighted_distance did comparatively better on two already-closer schema pairs, while naive runtime was most branching-sensitive.Naive explores all newly produced schemas at each step; the other strategies select one schema per step.Source: §5.1.2 · pp. 10–11, Figure 6 · p. 11
  • Greedy reused 100% of original edit operations and produced shortest paths; random and weighted_distance achieved only partial reuse.Reuse measures how well the resulting path recovers the original mapping.Source: §5.1.2 · p. 11

5.2 Qualitative Study

  • On ICIJ, naive rule application reached 73% similarity in 1.57 seconds over 10 steps; a greedy local optimum was overcome with node-insertion idempotency, reaching 100% in 8.9 seconds over 32 steps.The local optimum involved a self-loop transformation that could not be refined under default semantics.Source: §5.2 · p. 12
  • On a 42.14M-node instance, runtime and affected elements grew linearly with database size; both also grew moderately with transformation similarity.Affected-element counts are cumulative and can revisit nodes for separate edit operations.Source: §5.2 · p. 12

6 CONCLUSIONS AND PERSPECTIVES

GRAFT models schema evolution as reusable grounded transformations, with pruning that preserves accuracy under stated conditions. The conclusion identifies practical uses and future extensions; appendices document supporting results and contrast graph evolution with relational edits.

6 CONCLUSIONS AND PERSPECTIVES

  • GRAFT represents schemas as meta-graph vertices and grounded meta-transformations as edges, deriving mappings from source schemas to a target.The resulting sequences can be consumed by migration tools and provide alignments for ontology and knowledge-graph integration.Source: §6 · p. 12
  • Pruning preserves accuracy, and greedy exploration reaches the target for T-monotone transformation sets when each non-optimal schema admits a similarity-improving step.Without pruning, GRAFT is complete; properties preserved by every transformation are inherited by the composed mapping, ensuring consistency.Source: §6 · p. 12
  • Future work includes semantic similarity, value-rewriting edits, richer schema-validity conditions, and a dynamic cost model that predicts data-level transformation cost.The proposed cost-aware search could rank candidate schemas by target similarity and predicted cost.Source: §6 · p. 12

APPENDIX

  • The appendices collect proofs of exact Jaccard similarity, transformation termination and greedy optimality, plus additional operation-cost, scalability, real-world, and runtime-breakdown experiments.They also establish completeness for unpruned GRAFT.Source: APPENDIX · p. 14

A RELATIONAL VS. PROPERTY GRAPH SCHEMA EVOLUTION

  • Relational edits can often evolve independently, but graph edits interact because node and edge typing constraints are coupled, imposing ordering constraints on transformations.For the motivating example, updating an edge endpoint must precede removing its node type; Start* and Next* capture such ordering constraints.Source: A RELATIONAL VS. PROPERTY GRAPH SCHEMA… · p. 14

B EXACTNESS OF JACCARD SIMILARITY

The appendix establishes that the extracted-feature Jaccard measure distinguishes any two different property graph schemas. It also describes how GRAFT validates generated transformation sequences and proves that this process terminates with finite output.

B EXACTNESS OF JACCARD SIMILARITY

  • For any two property graph schemas, Jaccard similarity on the extracted features equals 1 exactly when the schemas are equal.The proof distinguishes differences in vocabulary, property or label assignments, and edge endpoints.Source: B EXACTNESS OF JACCARD SIMILARITY · pp. 14–15
  • The feature extractor separates names, type-property and type-label incidences, and edge endpoint incidences, so structural features refine scores below 1 without affecting exactness.Separate namespaces prevent vertex, edge, property, and label names from colliding.Source: B EXACTNESS OF JACCARD SIMILARITY · p. 14

C GRAFT’S TRANSFORMATION GENERATION AND EXECUTION

  • Algorithm 3 grounds Start and Next, derives valid transformations, applies edits incrementally with validity checks, and outputs only fully valid sequences.For finite input schemas, it terminates and produces a finite set of transformation-schema pairs.Source: C GRAFT’S TRANSFORMATION GENERATION… · p. 15

D GRAFT’S OPTIMALITY UNDER PRUNING

Under a T-monotone set of meta-transformations, greedy search with pruning reaches the most-similar reachable schema. If the exact target is reachable and similarity is exact, the returned schema is the target.

D GRAFT’S OPTIMALITY UNDER PRUNING

  • When the exact target is reachable and the similarity measure is exact, the most-similar reachable schema equals the target.The theorem gives this consequence for the returned best schema.Source: D GRAFT’S OPTIMALITY UNDER PRUNING · p. 15
  • With T-monotone meta-transformations, greedy exploration under pruning reaches an optimal most-similar reachable schema after finitely many iterations.T-monotonicity requires a similarity-improving step at every reachable non-optimal schema; each improvement resets the no-improvement counter.Source: D GRAFT’S OPTIMALITY UNDER PRUNING · p. 15
  • The current best schema remains in the frontier until expanded; if it is non-optimal, T-monotonicity ensures its expansion produces a more similar schema that re-enters the frontier.The greedy heuristic selects that best frontier schema when its parameter β is at least 1.Source: D GRAFT’S OPTIMALITY UNDER PRUNING · p. 15

E GRAFT’S EDIT OPERATION PERFORMANCE

Edit operations affect differing amounts of the graph and have differing runtimes when translated into Cypher. Their costs depend on the operation and its context, limiting static cost prediction.

E GRAFT’S EDIT OPERATION PERFORMANCE

  • Figure 9 reports average impacted elements per edit operation and average runtime; node insertion has the largest impact, while node deletion can remove an incident edge.Each operation affects only a small fraction of the graph on average.Source: E GRAFT’S EDIT OPERATION PERFORMANCE · pp. 15–16, Figure 9 · p. 16
  • The three deletion operations are fastest in Cypher, while other operations take longer because they match elements by id; node deletion also removes incident edges.Node deletion is slower than property deletion for that reason.Source: E GRAFT’S EDIT OPERATION PERFORMANCE · p. 16
  • Edit-operation costs cannot be predicted statically because they vary with the number of affected elements and preceding edits, though coarse preferences can guide search.For example, deleting the first endpoint of an edge costs more than deleting the second because the first deletion removes the shared edge.Source: E GRAFT’S EDIT OPERATION PERFORMANCE · p. 16

F GRAFT’S SCALABILITY

Greedy exploration maintains high-quality similarity results with substantially lower runtimes than naive exploration as schemas grow, though Flight-Hotel exposes a local-optimum limitation. The tolerance parameter also trades runtime for quality.

F GRAFT’S SCALABILITY

  • The scalability comparison augments both schemas with identical nodes and reports normalized similarity improvement alongside runtime.Figure 10b reports similarity improvement and Figure 10c reports runtime.Source: F GRAFT’S SCALABILITY · p. 16
  • For most datasets, greedy and naive achieve optimal or near-optimal similarity, while greedy keeps runtimes substantially lower as schema size increases.Naive exploration times out on Person-Data and Flight-Hotel.Source: F GRAFT’S SCALABILITY · p. 16
  • On Flight-Hotel, one-edit meta-transformations create a fine-grained search where local improvements can block access to larger, non-monotonic gains.Greedy may become trapped in local optima and fail to reach optimal similarity as schema size increases.Source: F GRAFT’S SCALABILITY · p. 16
  • Higher θ trades runtime for quality; for dblp_to_amalgam1, the algorithm stops at θ = 0.5 because the source is already 63% similar to the target.Plateaus arise when θ exceeds the gap to the lowest-similarity schema whose distance from the target is below θ.Source: F GRAFT’S SCALABILITY · p. 16

G TRANSFORMING THE ICIJ DATABASE

On the skewed ICIJ Paradise Papers dataset, enabling idempotency raises similarity to the target from 73% to 100%. Transformation rules vary in their similarity gains and runtimes, with total runtime remaining under two minutes.

G TRANSFORMING THE ICIJ DATABASE

  • ICIJ has 5 nodes, 5 edges, and 2.02M database nodes, with more than 78% of nodes shared between two types.The transformations are derived from the rules in.Source: G TRANSFORMING THE ICIJ DATABASE · p. 16
  • With idempotency, GRAFT reaches 100% similarity to the ICIJ target, compared with 73% without idempotency.Without idempotency, rules 1, 2, 14, and 15 are used; with it, rules 1, 6, 9, 10, and 14 are used.Source: G TRANSFORMING THE ICIJ DATABASE · p. 16
  • R10 yields the largest similarity increase and longest runtime, while R9 ranks fourth in similarity increase but second in runtime.Overall runtime is higher than on the iBench large-scale schema but remains within two minutes.Source: G TRANSFORMING THE ICIJ DATABASE · p. 16

H GRAFT’S RUNTIME BREAKDOWN

With pruning on DBLP-Amalgam1, greedy performs best among the compared heuristics. Runtime analysis identifies similarity computation as the main bottleneck, while the appendix establishes completeness without pruning and outlines further technical results.

H GRAFT’S RUNTIME BREAKDOWN

  • The runtime breakdown instruments five stages, from edit-operation generation through similarity computation and meta-graph construction.Meta-graph construction inserts non-pruned schemas and uses signatures to avoid duplicates; this step is dominated by database I/O.Source: H GRAFT’S RUNTIME BREAKDOWN · pp. 16–17
  • Similarity computation dominates runtime, followed by schema generation and meta-graph construction; edit-operation and transformation generation are negligible.Figure 12 reports cumulative times; for smaller schemas, database I/O overhead overtakes the other timings.Source: H GRAFT’S RUNTIME BREAKDOWN · p. 17, Figure 12 · p. 17

I COMPLETENESS OF UNPRUNED GRAFT

  • Without pruning, GRAFT is complete for target-schema reachability: if the target is reachable from the source, the algorithm returns a valid transformation.The result assumes a finite set of meta-transformations and sets k = ∞ and θ = 0.Source: I COMPLETENESS OF UNPRUNED GRAFT · p. 17

J PERFORMANCE OF GRAFT’S HEURISTICS WITH PRUNING ON DBLP-AMALGAM1

K TECHNICAL DETAILS

  • The appendix complements Section 4 with details on meta-transformation generation and complexity, meta-graph size bounds, and GRAFT’s formal properties.Source: K TECHNICAL DETAILS · pp. 17–18

K.1 Meta-Transformation Generation

GRAFT derives ordered, duplication-free transformations and compresses compatible edit operations through cliques. Its technical analysis bounds the induced meta-graph and establishes termination and runtime bounds for schema search.

K.1 Meta-Transformation Generation

  • Maximal cliques group mutually compatible edit operations that can be applied in arbitrary order, enabling permutation-equivalent operations to be contracted during generation.A compatibility graph connects grounded operations that may follow one another and share the same predecessor context.Source: §K.1 · p. 18
  • Algorithm 1 enumerates exact duplication-free transformation sequences that start with a Start operation and respect the Next relation.With n distinct edit operations, generation is O(n!) in the worst case and O(2^n) with clique compression.Source: §K.1 · p. 18

K.2 Meta-Graph Schema Search Space

  • With n distinct edit operations, the meta-graph has at most 2^n reachable schemas and at most |M*| · 2^n edges.The bound follows because permutations of the same edits either yield the same schema or an invalid sequence.Source: §K.2 · p. 19

K.3 GRAFT Theoretical Properties

  • GRAFT terminates because only finitely many distinct schemas can be generated, and each schema is inserted at most once.Grounded transformations use only elements from the finite input schemas, so they cannot introduce fresh symbols.Source: §K.3 · p. 19
  • Without pruning, Algorithm 2 runs in O(b^d · C); with pruning of width k, its runtime is O(k^d · b · (C + log k)).Here d is the minimum number of transformation steps from S to T, b the branching factor, and C the cost of Algorithm 3.Source: §K.3 · p. 19
Loading 2609.34789v3…