Non-Monotonic Data Provenance via Query Rewriting

16 concepts6 papers1 proposal

Data provenance—the ability to track the origin, history, and derivation path of a piece of data—is crucial for debugging queries, verifying data reliability, and explaining complex database outputs. However, implementing provenance tracking in real-world systems faces two severe hurdles:

  1. The Architectural Hurdle: Modifying the internal kernel of an existing database engine to track data lineage is highly invasive, making it impractical for production environments and difficult to port across different database systems.
  2. The Mathematical Hurdle: Traditional mathematical frameworks for provenance assume queries are monotonic (i.e., adding more source data can only increase the output). They break down completely when encountering non-monotonic operators like negation, set difference, or optional joins, where adding source data can cause existing results to disappear.

A powerful research direction addresses both challenges simultaneously. By combining middleware-based query rewriting with extended algebraic semirings, researchers have developed engine-agnostic systems capable of tracking mathematically rigorous provenance for complex, non-monotonic queries on top of completely unmodified, standard database engines.


Decoupling Tracking from the Engine via Query Rewriting

To avoid modifying database kernels, the core architectural insight of this field is to intercept and transform queries before they ever hit the database engine.

Instead of changing how an engine executes a query, a middleware layer rewrites the user's high-level query into an expanded version. This rewritten query is designed to simultaneously compute the primary data results and synthesize the metadata required to reconstruct their origin. Because the output of the rewriting process is just standard query code (such as SQL or SPARQL), it can be executed natively by any off-the-shelf database engine.

[User Query] ──> [ Middleware / Query Rewriter ] ──> [ Expanded Query ]
                                                            │
                                                            ▼
[Provenance Polynomials] <── [ Unmodified DB Engine ] <─────┘

In the relational database world, Bahareh Sadat Arab et al. demonstrated the viability of this non-invasive approach with the GProM middleware in GProM - A Swiss Army Knife for Your Provenance Needs. The authors showed that complex database transactions and even "why-not" questions (explaining why a result is missing) can be answered by translating metadata requirements into standard relational queries.

Similarly, Yann Ramusat et al. developed ProvSQL (ProvSQL: Provenance and Probability Management in PostgreSQL), which integrates provenance tracking into PostgreSQL via standard, non-invasive extension hooks. By avoiding kernel modifications, these systems achieve production-scale performance while remaining fully compatible with evolving database versions.


The Mathematical Breakdown of Negation

While query rewriting solves the deployment problem, non-monotonic operators introduce a deeper mathematical challenge.

In standard provenance frameworks, data lineage is represented using provenance semirings, where query operations are mapped to polynomial expressions:

  • Addition ($+$) represents alternative derivation paths (such as a UNION or multiple distinct graph patterns yielding the same result).
  • Multiplication ($\times$) represents conjunctive derivation paths (such as a JOIN where multiple pieces of data must coexist to produce an output).

For this algebraic representation to remain consistent, the operations must obey the distributive law:

$$a \times (b + c) = (a \times b) + (a \times c)$$

This framework works perfectly for monotonic queries. However, when a query includes non-monotonic operators—such as SQL's EXCEPT or SPARQL's MINUS and OPTIONAL—the system must model the absence or negation of data.

If one attempts to use standard algebraic subtraction to represent data removal, the mathematical framework collapses. Standard subtraction does not distribute over addition in a way that preserves the discrete tracking of execution paths. Without a sound algebraic foundation, a rewritten query cannot accurately compute how a result was derived if its existence depended on the exclusion of other data.


Extending Semirings for Non-Monotonic Logic

To resolve this mathematical bottleneck, researchers extended traditional semirings to handle the logic of data absence without losing algebraic consistency.

In Algebraic Structures for Capturing the Provenance of SPARQL Queries, Floris Geerts et al. introduced a novel algebraic structure known as spm-semirings. This framework bridges standard semirings with a boolean algebra. While the semiring tracks positive query components, the boolean algebra manages the logic of negation and difference by mapping semiring elements to boolean values that represent data presence or absence.

To make these concepts concrete during query execution, Daniel Hernández 0002 et al. utilized an algebraic extension featuring a specialized monus operator ($\dot{-}$) in Computing How-Provenance for SPARQL Queries via Query Rewriting. The monus operator correctly models operations where adding source data deletes an output, ensuring that the provenance tracking remains mathematically sound where standard subtraction fails.

By embedding these advanced algebraic structures directly into the query rewriting layer, middleware tools can generate polynomials that account for both data presence and absence. For example, Anas Katim et al. implemented these specialized semirings in the SPARQLprov system (Visualizing How-Provenance Explanations for SPARQL Queries), allowing users to extract and visualize "how-provenance" explanations as polynomial expressions directly from standard, unmodified graph endpoints.


Achieving Native, High-Performance Execution

The ultimate realization of this research direction is fully native integration. Rather than relying on slow, external post-processing steps to reconstruct data lineage, the rewritten query embeds the spm-semiring mathematics directly into the execution plan of the database engine.

As demonstrated by Zubaria Asma et al. with the NPCS framework (NPCS: Native Provenance Computation for SPARQL), integrating provenance computation directly into the native query execution path significantly outperforms external methods. Because the underlying engine optimizes and executes the rewritten query as a single unit, it can efficiently handle highly complex, non-monotonic operators like OPTIONAL and MINUS on standard, deployed database infrastructure.

By pairing the practical flexibility of query rewriting with the mathematical rigor of extended semirings, this paradigm proves that comprehensive, non-monotonic data tracking does not require specialized database engines—it can be achieved entirely through the clever manipulation of the queries themselves.

Key Foundational Work

Algebraic Structures for Capturing the Provenance of SPARQL Queries (2016) — contributed 4 concept elements to this direction.
GProM - A Swiss Army Knife for Your Provenance Needs (2018) — contributed 2 concept elements to this direction.
ProvSQL: Provenance and Probability Management in PostgreSQL (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_engine_agnostic_provenance_tracking_1d93e212,
  title = {engine-agnostic provenance tracking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/engine-agnostic-provenance-tracking/rdr_1d93e21284484c298236201285208f04},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_engine_agnostic_provenance_tracking_1d93e212_v1,
  title = {engine-agnostic provenance tracking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/engine-agnostic-provenance-tracking/rdr_1d93e21284484c298236201285208f04/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake