Querying with Provenance

Once provenance is enabled on one or more tables, ProvSQL transparently rewrites every SQL query to propagate and combine provenance annotations. No changes to query syntax are required.

How It Works

ProvSQL installs a PostgreSQL planner hook (shared_preload_libraries is required for this reason). When a query involves a provenance-enabled table, the hook intercepts the query plan before execution and:

  1. Identifies all relations carrying a provsql column.

  2. Builds a provenance expression that combines the input tokens using the appropriate semiring operations (plus for alternative use of tuples such as in duplicate elimination, times for combined use of tuples such as in joins, monus for difference).

  3. Appends the resulting provenance token to the output as an extra column.

The final provenance token in each output row is a UUID that represents a gate in a provenance circuit – a DAG recording how that result was derived.

Supported SQL Features

The following SQL constructs are supported with full provenance tracking:

  • SELECT … FROM … WHERE (conjunctive queries, multiset semantics)

  • JOIN (inner joins, outer joins, natural joins)

  • LATERAL subqueries

  • Non-recursive CTEs (WITH clauses)

  • Recursive CTEs (WITH RECURSIVE) using UNION (set semantics) over provenance-tracked relations, on PostgreSQL 15+: the recursive CTE is transparently evaluated to a fixpoint and the result carries provenance like any other query (e.g. the provenance of s–t reachability is the disjunction over the s–t paths). On acyclic data this works for any semiring. On cyclic data it requires an absorptive provenance class – provsql.provenance = 'absorptive' or 'boolean' – (an absorptive setting, under which the value converges); the resulting circuit is then sound only for absorptive evaluation (probability / Boolean), not for multiplicity-counting semirings

  • Subqueries in the FROM clause (including deeply nested)

  • Subqueries outside FROM (EXISTS/NOT EXISTS, IN/NOT IN, quantified comparisons such as = ANY or <> ALL, scalar subqueries, ARRAY(SELECT …)), correlated or not: they are internally decorrelated and rewritten. The subquery body may involve a single provenance-tracked relation, or join several of them as a comma-separated FROM list; e.g., NOT IN over a joined body carries the same antijoin provenance as the equivalent EXCEPT. An aggregate body can be compared against a constant or an outer column, including through IN/NOT IN (the single-row aggregate body makes these scalar comparisons)

  • GROUP BY

  • SELECT DISTINCT (set semantics)

  • UNION and UNION ALL

  • EXCEPT and EXCEPT ALL

  • VALUES tables (treated as having no provenance)

  • Aggregation (SUM, COUNT, MIN, MAX, AVG, COUNT(DISTINCT …), string_agg, array_agg)

  • HAVING (non-matching groups receive zero provenance 𝟘 rather than being filtered out)

  • FILTER clause on aggregates

  • INSERT … SELECT (provenance propagated when target table is provenance-tracked)

Unsupported SQL Features

The following constructs are not currently supported; queries using them will either raise an error or may cause incorrect provenance tracking:

  • Subqueries outside FROM whose body uses explicit JOIN syntax (rewrite the body as a comma-separated FROM list with the join condition in WHERE) or LIMIT/OFFSET (it would pick an order-dependent subset); also, when an uncorrelated body with no WHERE clause is compared against an outer column, only non-star aggregate bodies are supported (max(x), count(x), …, including via IN/NOT IN) – a plain value body or count(*) in that position is not

  • Recursive CTEs (WITH RECURSIVE) using UNION ALL (bag semantics), over cyclic data without an absorptive provenance class, or on PostgreSQL versions before 15

  • INTERSECT

  • DISTINCT ON

  • GROUPING SETS, CUBE, ROLLUP

  • Operations on aggregate results requiring comparison or duplicate elimination: DISTINCT on aggregates, UNION/EXCEPT (non-ALL) with aggregates, ORDER BY or GROUP BY on aggregate results from a subquery

  • Window functions (ROW_NUMBER, RANK, SUM OVER, LAG, LEAD, etc.): the query still executes and each output row carries the tuple provenance of its single input row, but the windowed computation itself has no aggregate-provenance semantics (SUM(x) OVER (…) is an opaque scalar, not an aggregation over the frame). A WARNING is emitted whenever a window function appears in a provenance-tracked query

For unsupported correlated subqueries, LATERAL can be used as a workaround. For comparison or duplicate elimination on aggregate results, explicitly cast the aggregate column to its base type (e.g., cnt::bigint), which extracts the value but loses the provenance information on that column.

Provenance in Nested Queries

Subqueries in the FROM clause are supported. Each sub-result carries its own provenance, which is further combined by the outer query:

SELECT t.name, provenance()
FROM (
    SELECT name FROM employees WHERE dept = 'R&D'
) t;

CREATE TABLE … AS SELECT

You can materialise a provenance-tracked query result into a new table. The new table automatically inherits provenance from its source:

CREATE TABLE derived AS
SELECT name, dept FROM employees WHERE active;

INSERT … SELECT

When both the source and target tables are provenance-tracked, INSERT … SELECT propagates provenance from the source query to the inserted rows:

CREATE TABLE archive (name VARCHAR, city VARCHAR);
SELECT add_provenance('archive');
INSERT INTO archive SELECT name, city FROM employees WHERE dept = 'R&D';

Each inserted row receives the provenance token computed by the source SELECT, rather than a fresh independent token.

If the target table does not have a provsql column, a warning is emitted indicating that source provenance is lost.

The provenance() Function

In a SELECT list, provenance() returns the provenance UUID of the current output tuple:

SELECT name, provenance() FROM mytable;

The token can be passed to semiring evaluation functions (see Semiring Evaluation) or to probability/Shapley functions.