ProvSQL is a PostgreSQL extension that adds semiring provenance and uncertainty management to SQL queries. It is implemented as a PostgreSQL planner hook that transparently rewrites queries – no changes to the application or schema are required.

For a full introduction to the concepts and capabilities, see the Introduction in the user documentation.

A pre-built container is also published on Docker Hub as inriavalda/provsql, for a zero-install trial. See the Docker instructions in the installation guide.

Query Rewriting

When a table is registered for provenance tracking via add_provenance(), each tuple gains a provsql UUID column. ProvSQL’s planner hook intercepts every query involving such tables and rewrites it to compute a provenance circuit over those UUIDs, appending the result UUID to the SELECT list.

The rewriter handles:

  • SELECT-FROM-WHERE, inner and outer JOIN, LATERAL
  • Subqueries in FROM (including deeply nested) and outside FROM (EXISTS / NOT EXISTS, IN / NOT IN, quantified comparisons such as = ANY, scalar subqueries), correlated or not
  • GROUP BY, aggregation (including FILTER clauses), HAVING, SELECT DISTINCT
  • UNION / UNION ALL / EXCEPT / EXCEPT ALL
  • VALUES
  • Common table expressions (WITH), including WITH RECURSIVE on PostgreSQL 15+
  • UPDATE / INSERT / DELETE (when provsql.update_provenance is enabled)

See the supported-features list in the user documentation for the precise scope.

Semiring Evaluation

Once a query carries provenance, its circuit can be evaluated in any commutative (m-)semiring through a single compiled-evaluation path: Boolean provenance, tuple counting, why-, how-, and which-provenance, symbolic formulas, and the tropical, Viterbi, Łukasiewicz, and min-max / max-min semirings, among others. The same circuit also drives where-provenance – which source cells contributed to each output value – and Shapley / Banzhaf values that quantify each input tuple’s contribution to an answer, both computed in a single traversal. See the semiring documentation.

Probability Evaluation

ProvSQL is also a probabilistic database: attach a probability to each input tuple with set_prob(), and the provenance circuit becomes the lineage formula whose probability is the marginal probability of the query answer. ProvSQL computes it exactly (by independent-circuit evaluation, tree decomposition, or d-DNNF knowledge compilation through an external compiler) or approximately with (ε, δ) guarantees (Monte Carlo, Karp-Luby, stopping-rule, sieve, certified-bounds d-trees, or weighted model counting). In practice you do not pick a method: you ask for the guarantee you want – exact, or additive / relative (ε, δ) – and a cost-based chooser runs the cheapest method that meets it, escalating automatically under a budget. Because exact probability computation is #P-hard in general, an opt-in planner-side rewrite recognises tractable query classes – hierarchical conjunctive queries, a family of FD-aware extensions, and the broader inversion-free class – and evaluates them in linear time. Inputs may also be continuous random variables (Normal, Uniform, Exponential, Erlang, and mixtures), with expectations and moments computed analytically or by Monte Carlo. See the probability documentation.

Aggregation, Updates, and Time

Aggregation results carry provenance through m-semimodules: agg_token values record symbolically how a SUM, COUNT, MIN/MAX, or AVG depends on base tuples, support further arithmetic, evaluate in any m-semiring, and give exact probabilities to HAVING predicates. See the aggregation documentation. Data modifications (INSERT / UPDATE / DELETE) can themselves be provenance-tracked, enabling audit and undo; combined with the interval-union semiring, validity timestamps turn a provenance-tracked database into a temporal database, time-travel queries included.

ProvSQL Studio

ProvSQL Studio is a web UI for provenance inspection that pairs with the extension. It runs as a separate Python package (on PyPI as provsql-studio), connects to any ProvSQL-enabled PostgreSQL database, and offers three complementary modes: a Circuit view that renders the provenance DAG behind a result token with on-the-fly semiring evaluation on any pinned subnode, a Where view that highlights, on hover, the source cells that contributed to each output value, and a Notebook mode – Jupyter-style notebooks with SQL, Markdown, circuit, and evaluation cells, saved and loaded as standard .ipynb files. The tutorial and case studies of the documentation ship as runnable example notebooks.

ProvSQL Playground

The ProvSQL Playground is the whole system running in your browser: PostgreSQL with ProvSQL compiled to WebAssembly (via PGlite), with the unmodified Studio Python on top (via Pyodide) – no install, no server, nothing leaves the page. It comes pre-loaded with databases and runnable notebooks for the tutorial and the case studies.

Lean Formalization

Key parts of the algebraic framework underlying ProvSQL – m-semirings, annotated databases, relational algebra semantics, and aggregation – have been formally verified in Lean 4. See the Lean formalization page for details.

License

MIT License

ProvSQL is free, open-source software, distributed under the permissive MIT License. You are free to use, modify, and redistribute it, including in commercial and proprietary settings, as long as the copyright notice is preserved. Contributions are welcome.

Archival and Citation

DOI Archived in Software Heritage

ProvSQL is continuously archived by Software Heritage, the universal software preservation infrastructure. You can browse the archived source tree at archive.softwareheritage.org.

Every tagged release receives a persistent DOI from Zenodo. The concept DOI above resolves to the latest version; a versioned DOI is available for each release from the Zenodo record page.

To cite ProvSQL in academic work, click the Cite this repository button on the GitHub repository page, or read the CITATION.cff file directly. The canonical reference is:

Aryak Sen, Silviu Maniu, Pierre Senellart. ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data. Proc. 42nd IEEE International Conference on Data Engineering (ICDE), Montréal, Canada, May 2026. arXiv:2504.12058

Download BibTeX

See the Publications page for a full list of research papers related to ProvSQL.

Architecture

The diagram below shows the end-to-end flow of a query through ProvSQL (see the architecture chapter in the developer guide for details):

ProvSQL dataflow

Get Started