Managing Time in Atemporal Labeled Property Graph Engines: Trade-offs in Representation Strategies

Abstract

We investigate the data management of temporal property graphs on atemporal Labeled Property Graph (LPG) engines. While existing frameworks define temporal semantics, practitioners lack systematic empirical guidance on mapping these models to concrete representations in the absence of native engine support. We formalize two fundamental representation strategies implemented on top of standard LPG systems: a Versioning strategy that materializes temporal states via topological expansion, and a Property Lists strategy that encapsulates evolution through property-level compression. For each strategy, we define query translations for temporal evolution operators and analytical aggregations, and evaluate them across two heterogeneous real-world datasets. Our evaluation reveals a fundamental trade-off between topological selectivity and historical compactness: Versioning excels at high-throughput ingestion and short-window workloads but suffers from traversal amplification in dense graphs over long horizons, while Property Lists amortizes scan costs for read-heavy, multi-window analytics but incurs higher ingestion overhead and cannot support time-varying labels. We identify workload-dependent crossover points, showing how dataset density and structural volatility determine the superior strategy.