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, which is why it must be listed
in shared_preload_libraries. When a query involves a provenance-enabled
table, ProvSQL rewrites it before execution:
Identifies all relations carrying a
provsqlcolumn.Builds a provenance expression that combines the input tokens using the appropriate semiring operations (
plusfor alternative use of tuples such as in duplicate elimination,timesfor combined use of tuples such as in joins,monusfor difference).Appends the resulting provenance token to the output as an extra column.
The provsql column that * expands to over a tracked table also comes
last: in SELECT *, a + 1 AS e FROM t, after e. A whole row of a
tracked table (SELECT t FROM t, row_to_json(t), t::text, t = u,
GROUP BY t) has only its columns other than provsql.
The provenance token in each output row is a UUID that identifies 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, with multiset semanticsJoins: inner, outer and natural joins,
LATERALsubqueriesSubqueries in
FROM, and outside it (EXISTS,IN, quantified comparisons such as= ANY, scalar subqueries,ARRAY(SELECT …)), correlated or not (see Subqueries)WITHclauses, andWITH RECURSIVEon PostgreSQL 15+ (see Recursive Queries)GROUP BY, withGROUPING SETS,ROLLUPandCUBEAggregation (
SUM,COUNT,MIN,MAX,AVG,COUNT(DISTINCT …),string_agg,array_agg, …),FILTERandHAVING(see Aggregation and Grouping)Window functions: aggregates over a frame determined by values,
rank,dense_rank,row_number,ntile,percent_rank,cume_dist(see Aggregates as Window Functions)SELECT DISTINCTandDISTINCT ONORDER BY … LIMIT/FETCH/OFFSET(see ORDER BY, LIMIT and OFFSET)UNION,UNION ALL,EXCEPT,INTERSECTVALUEStables, whose rows have no provenanceEXISTS (…)in theSELECTlist, as a Boolean value (see Grouping by the value of an aggregate)CREATE TABLE … AS,CREATE MATERIALIZED VIEWandINSERT … SELECT(see below)
All of these follow SQL’s semantics for NULL values (three-valued logic in predicates, syntactic matching in set operations and grouping, NULL-skipping aggregates); the chapter on NULLs spells out the rules and their effect on provenance.
Unsupported SQL Features
A query using one of the constructs below is refused with SQLSTATE
0A000 (feature_not_supported); where only part of a query cannot
be tracked, it runs with a warning instead (see Parts Whose Provenance Is Not Tracked). Both
name their cause on a DETAIL line, which tools can rely on:
DETAIL: provsql-reason: body-set-operation; scope: gap
The scope is deliberate when the construct has no provenance to give
(EXCEPT ALL, a LIMIT without ORDER BY), gap when ProvSQL
does not compute it yet, and out-of-scope for what lies outside the
supported query fragment (random variables, where-provenance,
conditioning, row locks).
Subqueries outside
FROMwhose body uses an outer join orLIMIT/OFFSET; a scalar subquery nested in a larger expression (1 + (SELECT …)), which runs untracked with a warningRecursive CTEs before PostgreSQL 15, and where-provenance through a cycle
EXCEPT ALLandINTERSECT ALLover tracked relations: useEXCEPTorINTERSECT, orNOT IN/INAn outer join with a tracked relation on its null-padded side, beside a
LATERALitem that reads a row of the join, or whoseUSING/NATURALmerged column is read (see NULL Values)DISTINCT ONover an aggregation, a set operation, or keys that vary between possible worldsGrouping by, deduplicating on or uniting on the value of an aggregate other than
count,min,maxandchoose(see Grouping by the value of an aggregate)Window functions other than those listed above (
lag,lead,first_value,ROWSframes with an offset, …): the query runs with a warning, the window value untrackedA data-modifying
WITH(INSERT/UPDATE/DELETE … RETURNING), which runs once, untrackedA locking clause (
FOR UPDATE,FOR SHARE,FOR NO KEY UPDATE) anywhere in a query over tracked relations;FOR KEY SHARE, which foreign-key checks take, is let throughx IN (…)used as a value rather than as a condition, and an ordering row comparison against a subquery ((a, b) < ANY (…))FILTERonarray_agg(DISTINCT …)and on thejson_aggfamily withDISTINCT*over a tracked table where the number of columns must match (an arm of a set operation,INSERT INTO t SELECT *into an untracked table):*includes theprovsqlcolumn, so PostgreSQL rejects the query, with a hint from ProvSQL; list the columns instead
For unsupported correlated subqueries, LATERAL can be used as a
workaround.
To read an aggregate result as its plain value on purpose, and silence the
warning that reports it, wrap it in plain() (see Parts Whose Provenance Is Not Tracked).
Recursive Queries
WITH RECURSIVE over provenance-tracked relations is supported on
PostgreSQL 15+. With UNION, a row’s provenance combines all its
derivations: the provenance of s–t reachability is the disjunction over
the s–t paths. With UNION ALL, each derivation is a row of its own,
as in SQL.
Over cyclic data, a row has infinitely many derivations. ProvSQL records
its provenance as equations between the rows of the cycle, and the
semiring evaluating it solves them: probabilities and the Boolean,
tropical, Viterbi, temporal, why- and which-provenance and
regular-expression semirings give a value, while counting and
how-provenance raise an error, the result being infinite.
sr_formula prints the equations:
x₂ where x₁ = a ⊗ x₂, x₂ = 𝟙 ⊕ (c ⊗ x₃), x₃ = b ⊗ x₁
A product keeps the order of the query, that of the FROM clause, which
matters to the semirings whose multiplication does not commute: the regular
expressions of sr_regex and the shortest paths of
sr_tropical_paths and sr_best_path (see
Semiring Evaluation). Write the recursive relation first in the recursive
FROM clause (FROM reach r JOIN edges e) to read a path in the order
it is followed, last to read it backwards. The first two need the recursive
relation at the same place of every recursive FROM clause, and refuse a
recursion that has it between two other relations.
An exact probability of such a row expands the equations into a Boolean
circuit, of about the size of a cycle’s rows times its terms: on a large
cyclic graph (a city’s transport network), too large to build, and the
exact evaluation is then refused. The sampling methods ('monte-carlo',
'stopping-rule', and the 'additive' and 'relative' requests of
Choosing a guarantee, not a method) solve the equations in each sampled world
instead, at a cost of the order of the query’s provenance.
A UNION ALL recursion that does not end stops with an error.
Subqueries
A subquery condition gives a row the provenance of the subquery’s matching
rows (EXISTS, IN, = ANY), or of their absence (NOT EXISTS,
NOT IN, <> ALL). The body may join several relations, aggregate,
or be a set operation, and the condition may sit in a disjunction
(WHERE name = 'NY' OR EXISTS (…)). A block that reads tracked
relations only through its subqueries is tracked too, its own rows counting
as present in every possible world. The limits are listed under
Unsupported SQL Features.
ORDER BY, LIMIT and OFFSET
Over provenance-tracked relations, ORDER BY … LIMIT k is read in
every possible world: a row is kept where it is among the first k
present rows. The result has every row that may be among the first k,
each annotated with that condition:
-- every employee, with the probability of being among the three
-- best paid
SELECT name, probability_evaluate(provenance())
FROM employees
ORDER BY salary DESC
LIMIT 3;
The same holds for FETCH FIRST, OFFSET, DISTINCT ON (the first
row of each group), groups ranked on an aggregate (see
Ranking the groups of an aggregation), and in subqueries. Where the ORDER BY
leaves ties, LIMIT keeps all the tied rows, as FETCH … WITH TIES
does, and a WARNING says so. Ties are looked for among the rows of every
world, those absent from the actual data included (a null-padded row, a row
excluded by NOT EXISTS), even two rows that are never present together.
To keep the truncation of the actual result instead, for instance to look
at its first rows, write plain:
SELECT name, probability_evaluate(provenance())
FROM employees
ORDER BY salary DESC
LIMIT plain(3);
The rows kept carry their provenance in the full result. A LIMIT with
no ORDER BY, or one ProvSQL cannot read in every world, is also kept
as the truncation of the actual result, with a WARNING unless it is
written with plain().
The truncation is of the tracked result, which may hold rows that are
answers only in other worlds (a row a condition on an aggregate value
rejects in the actual data, a null-padded row): such rows take places
among the k kept. To truncate only among the rows of the actual data,
filter on present in the WHERE, at the cost of evaluating
the provenance of every row:
SELECT name, salary
FROM employees
WHERE salary > (SELECT avg(salary) FROM employees)
AND present(provenance())
ORDER BY salary DESC
LIMIT plain(3);
Parts Whose Provenance Is Not Tracked
A few constructs are not tracked: their value is computed without regard
to provenance, as if that part of the query were a constant, and ProvSQL
says which part in a WARNING:
WARNING: ProvSQL: scalar subquery nested in an expression: provenance not tracked
DETAIL: provsql-reason: sublink-nested-in-expression-frozen; scope: gap
HINT: Mark it plain() to say so.
The parts not tracked are:
a window function other than those of Aggregates as Window Functions, and a window partitioned by an aggregate result or ordered by one other than the tracked ranks (see Ranking the groups of an aggregation);
a scalar subquery nested in an expression, and a subquery ProvSQL cannot rewrite in a block with no tracked relation of its own;
a
LIMITnot read in every world (see ORDER BY, LIMIT and OFFSET), and aLIMITin a subquery;an aggregate result read as a plain value by a function or operator ProvSQL does not track (
round(avg(x)), see Aggregation and Grouping).
If that part reads a relation the rest of the statement tracks, the
warning names it; setting provsql.implicit_freeze to 'error' then refuses the query instead.
Wrapping the part in plain says that computing it without
provenance is meant, and silences the warning: plain((SELECT max(x) FROM
t)), plain(lag(v) OVER (ORDER BY d)), LIMIT plain(k). A LIMIT
in a subquery is the exception: the rows it keeps feed the rest of the
query, whose provenance does not record the cut, and the warning remains,
with plain or without. In FROM, plain(NULL::t) reads table
t without its provenance:
SELECT * FROM plain(NULL::employees);
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;
A row inserted into it later gets a token of its own, as in a table
passed to add_provenance. A CREATE MATERIALIZED VIEW over
the same query gets the provenance of its rows too, as a provsql
column that REFRESH MATERIALIZED VIEW recomputes; an aggregate is
stored there as its value.
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, not a fresh independent token.
If the target table does not have a provsql column, a warning says
that the provenance is lost; the rows inserted are those of the tracked
result (a LEFT JOIN also inserts its null-padded rows). To keep the
provenance, track the target first, or store the token explicitly with
provenance (no warning is then emitted):
CREATE TABLE archive_tokens (name VARCHAR, token UUID);
INSERT INTO archive_tokens SELECT name, provenance() FROM employees;
Selecting the provsql column of a tracked table for that purpose is
refused: use provenance().
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.
In a query that aggregates, provenance() is read where SQL evaluates
it. In the SELECT list or HAVING, outside an aggregate, it is the
provenance of the group. In WHERE, in a GROUP BY key and inside an
aggregate (its FILTER included), it is the provenance of each input row:
-- the tokens of the rows of each group, and the group's own
SELECT dept, array_agg(provenance()) AS rows, provenance() AS grp
FROM employees GROUP BY dept;