A DBMS-Independent Approach for Capturing Provenance Polynomials Through Query Rewriting

Data provenance provides fine-grained information about the origin and derivation of query results, directly supporting traceability, transparency, explainability and reproducibility in modern data-intensive environments. Provenance polynomials offer a formal framework for modelling these derivations, but despite their strong theoretical foundations, practical implementations remain limited, particularly with respect to full aggregation support and DBMS portability. This paper presents a query rewriting-based approach for annotating Structured Query Language (SQL) queries with provenance polynomials. The proposed methods are DBMS-independent and support Selection, Projection, Join, Union and Aggregation (SPJUA) operations, as well as nested queries through recursive propagation of provenance annotations. We implemented our proposals in the DataProv middle-ware, the first complete implementation of semiring-based theory for provenance polynomials extended with semimodule structures. It requires no modifications to the underlying data management and storage systems. DataProv is evaluated using distinct configurations of the TPC-H benchmark, comparing its capabilities and execution time with those of comparable systems. DataProv successfully captured data provenance for approximately 93% of the queries, while Perm, GProM, and ProvSQL successfully captured data provenance for approximately 86%, 50%, and 14%, respectively. DataProv also largely outperformed other tools in terms of execution time, achieving the best performance in 91% of the queries.