Computing Why-Provenance for Property Graph Queries

Abstract

Labeled Property Graphs (LPGs) have gained widespread adoption, supported by the ongoing standardization of the Graph Query Language (GQL). As LPGs are frequently constructed through the integration of heterogeneous data sources, inconsistencies and errors may propagate into query results. To explain and validate such results, it is essential to determine which parts of the input graph contributed to a given answer - an aspect captured by data provenance. In this paper, we present a formal definition of why-provenance tailored specifically to GQL, characterizing the fine-grained subgraph that contribute to a query answer. Building on the Core-GQL algebraic foundation, we further propose an efficient query-rewriting-based algorithm for computing provenance, leveraging the native execution capabilities of existing GQL-compliant graph database systems. Our extensive experimental evaluation demonstrates the feasibility and scalability of our approach, showing that provenance can be computed with moderate overhead that scales effectively with graph size.