ProvSQL SQL API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Semiring operations

Functions that build provenance circuit gates for semiring operations. More...

Functions

UUID provsql.provenance_times (UUID[] tokens)
 Create a times (product) gate from multiple provenance tokens.
UUID provsql.provenance_monus (UUID token1, UUID token2)
 Create a monus (difference) gate from two provenance tokens.
UUID provsql.provenance_project (UUID token, INT[] positions)
 Create a project gate for where-provenance tracking.
UUID provsql.provenance_eq (UUID token, INT pos1, INT pos2)
 Create an equijoin gate for where-provenance tracking.
UUID provsql.provenance_plus (UUID[] tokens)
 Create a plus (sum) gate from an array of provenance tokens.
VOID provsql.planted_scope (TEXT work_name)
 Declare the working table of a recursive CTE, just (re)created (internal).
UUID provsql.plant_canonical (TEXT work_name, TEXT kind, UUID[] tokens, UUID target, INT info1, INT info2=0)
 Plant a certified gate in place of a sum or a product (internal).
UUID provsql.fixpoint_token (UUID sys, INT i)
 Address of the fixpoint gate reading component i of the equation system sys (internal).
UUID[] provsql.resolve_fix_system (UUID sys)
 The token of each tuple of the equation system sys (internal).
VOID provsql.eval_recursive_system (TEXT body_sql, TEXT work_name, TEXT colnames, TEXT coldef)
 Driver for provenance over recursive queries (WITH RECURSIVE), as an equation system (internal).
VOID provsql.eval_recursive_all (TEXT q0_sql, TEXT q1_sql, TEXT work_name, TEXT all_name, TEXT colnames, TEXT coldef, INT max_iter=1000)
 Drive a UNION ALL recursion, one round per bag of derivations.
UUID provsql.provenance_cmp (UUID left_token, OID comparison_op, UUID right_token)
 Create a comparison gate for HAVING clause provenance.
UUID[] provsql.cmp_surviving_factors (UUID[] tokens, UUID cmp)
 The factors of a row annotation an aggregate comparison does not subsume.
UUID provsql.provenance_cmp_times (UUID cmp, UUID[] tokens)
 Combine a lifted aggregate comparison with the row annotation it supersedes only part of.
UUID provsql.provenance_arith (INTEGER op, UUID[] children)
 Create an arithmetic gate over scalar-valued provenance children.
UUID provsql.provenance_case (UUID[] children)
 Create a guarded-selection gate over scalar (RV) children.

Detailed Description

Functions that build provenance circuit gates for semiring operations.

These are called internally by the query rewriter.

They are declared IMMUTABLE: each derives its gate UUID deterministically from its arguments (a uuid5 content address) and the create_gate write at that address is idempotent, so the token a call returns is a pure function of its inputs. The marking matters for parallelism: PL/pgSQL runs a non-volatile function's inner SPI read-only, so the per-row builders the rewriter injects into a scan do not call CommandCounterIncrement – which would raise "cannot start commands during a parallel operation" once the enclosing statement has gone parallel. A VOLATILE builder both blocks that parallel plan and loses the query-wide speed-up.

Function Documentation

◆ cmp_surviving_factors()

UUID[] provsql.cmp_surviving_factors ( UUID[] tokens,
UUID cmp )

The factors of a row annotation an aggregate comparison does not subsume.

A lifted comparison entails the existence of the group it ranges over, so it supersedes that group's gate_delta instead of multiplying with it. This reports which factors of tokens survive that supersede: a bare δ over the compared group disappears, a times keeps its other factors, and anything else – an earlier comparison on the same group, an input – is kept whole.

Source code
provsql.sql line 2035

◆ eval_recursive_all()

VOID provsql.eval_recursive_all ( TEXT q0_sql,
TEXT q1_sql,
TEXT work_name,
TEXT all_name,
TEXT colnames,
TEXT coldef,
INT max_iter = 1000 )

Drive a UNION ALL recursion, one round per bag of derivations.

The bag recursion is not a fixpoint over a set: its rounds are M0 = q0 and M(i+1) = q1 over Mi – the PREVIOUS round, not what has been derived so far – and its answer is the bag union of every round, which ends when a round derives nothing. Each tuple of it is one derivation, annotated by the product along that derivation, and two derivations of the same tuple are two rows and are not merged: that is what distinguishes it from UNION, whose driver (eval_recursive_system) sums the derivations of a tuple into one row.

work_name holds the previous round, which the recursive term reads by the name of the CTE; all_name accumulates the answer and is what the query reads. Ending on an empty round is SQL's own rule, so a recursion PostgreSQL runs to completion ends here too, and one it does not is caught by max_iter as before.

Parameters
q0_sqlthe non-recursive term, as SQL
q1_sqlthe recursive term, reading work_name
work_nametemp table of the previous round (the CTE's name)
all_nametemp table accumulating the rounds
colnamescomma-separated user column names
coldefcolumn definitions ("name type, ...")
max_itersafety bound on the number of rounds
Source code
provsql.sql line 1938

◆ eval_recursive_system()

VOID provsql.eval_recursive_system ( TEXT body_sql,
TEXT work_name,
TEXT colnames,
TEXT coldef )

Driver for provenance over recursive queries (WITH RECURSIVE), as an equation system (internal).

Invoked by the planner hook (lower_recursive_cte in provsql.c) when it lowers a recursive CTE with UNION whose body touches provenance-tracked relations; the hook deparses the CTE body to SQL and scans, in place of the CTE, the table this function fills. Instead of unrolling the fixpoint round after round, it records the recursion as one equation per derived tuple, x_t = f_t(x), and leaves the value of the tuples derived through themselves to evaluation time, where the semiring is known:

  1. the derived tuples are computed by PostgreSQL's own recursion, with provenance tracking off;
  2. the working table is loaded with them, each carrying a fresh unknown (a fixvar gate) as its token;
  3. the CTE body is run once over that table, through ProvSQL's normal rewriting: the token it gives a tuple is the right-hand side f_t of its equation, an ordinary circuit over the input tokens and the unknowns. A row this round derives that plain recursion did not – absent from the database as it is, present in other worlds, as the null-padded row of an outer join – is a tuple of the recursion too: it is added with an unknown of its own, and the round run again, until it derives no new row;
  4. a fixsystem gate gathers the unknowns and the right-hand sides, and resolve_fix_system gives each tuple its token: the ordinary circuit a fixpoint iteration would reach, for a tuple derived through no cycle; a fixpoint gate over its cyclic component's own system otherwise.

The recursion thus costs plain SQL's rounds plus one, and the circuit one round of derivations, whatever the data's cycles; whether a cyclic component has a value is decided by the semiring evaluating it (see GenericCircuit::solveFixSystem): every absorptive semiring, and those with a star (counting with an infinite count, min-plus with negative cycles, why- and which-provenance); sr_formula renders the equations.

This function has no SET search_path on purpose: body_sql is the caller's deparsed query and must resolve relation names in the caller's path.

Parameters
body_sqlthe recursive CTE body, e.g. 'SELECT 1 UNION SELECT e.dst FROM edge e JOIN reach r ON e.src=r.node'
work_namethe working relation name body_sql references
colnamescomma-separated user columns
coldefcolumn definitions for the working table
Source code
provsql.sql line 1794

◆ fixpoint_token()

UUID provsql.fixpoint_token ( UUID sys,
INT i )

Address of the fixpoint gate reading component i of the equation system sys (internal).

Content-addressed like every other gate, from the system and the index, so that evaluation, having solved a system, can name each of its components (see provenance_evaluate_compiled's solution cache).

Source code
provsql.sql line 1725

◆ plant_canonical()

UUID provsql.plant_canonical ( TEXT work_name,
TEXT kind,
UUID[] tokens,
UUID target,
INT info1,
INT info2 = 0 )

Plant a certified gate in place of a sum or a product (internal).

Creates a kind gate with the single child target at the canonical address of the multiset tokens – the v5 UUID of 'plus-canonical{sorted tokens}' or 'times-canonical{…}', a recipe under which nothing else creates gates – and remembers the address in this session: while the working table work_name exists, provenance_plus / provenance_times given that very multiset return the planted gate. The tokens are row tokens of the working table, a temporary table, so the sum or product is computed by the session that planted, never by a parallel worker; the store is not consulted, and sessions that planted nothing pay nothing.

Parameters
work_nameworking table the tokens belong to
kind'plus' or 'times'
tokensthe multiset the planted gate stands for
targetroot of the certified circuit
info1first info of the planted gate
info2second info of the planted gate
Returns
the address of the planted gate
Source code
provsql.sql line 1711

◆ planted_scope()

VOID provsql.planted_scope ( TEXT work_name)

Declare the working table of a recursive CTE, just (re)created (internal).

Gates planted from now on belong to it; those planted for the table of the same name it replaces, and for working tables that no longer exist, are forgotten.

Parameters
work_namename of the temporary working table
Source code
provsql.sql line 1685

◆ provenance_arith()

UUID provsql.provenance_arith ( INTEGER op,
UUID[] children )

Create an arithmetic gate over scalar-valued provenance children.

Builds a deterministic gate_arith from an operator tag and an ordered list of children. The tag is one of the provsql_arith_op ENUM values declared in src/provsql_utils.h (PLUS=0, TIMES=1, MINUS=2, DIV=3, NEG=4) and is stored in the gate's info1 field. Children must be UUIDs of scalar-producing gates (gate_rv, gate_value, or another gate_arith). The token UUID is derived deterministically from op and children so identical sub-expressions share their gate.

Parameters
opOperator tag (provsql_arith_op).
childrenOrdered list of child gate UUIDs.
Returns
UUID of the (possibly pre-existing) gate_arith.

Implemented in C (gate_builders.c): the gate is created together with what it records, in one unanswered message.

Source code
provsql.sql line 2080

◆ provenance_case()

UUID provsql.provenance_case ( UUID[] children)

Create a guarded-selection gate over scalar (RV) children.

Builds a deterministic gate_case from the flattened wire list [guard_1, value_1, ..., guard_k, value_k, default] (odd length): the value of the first guard event that holds, else the default (first-match semantics). Each guard is a Boolean event token (a gate_cmp or Boolean combination); each value and the default are scalar-producing gates (gate_rv, gate_value, gate_arith, another gate_case, ...). The token UUID is derived deterministically from children so identical CASE expressions share their gate.

Parameters
childrenFlattened guard/value wires ending with the default (array_length must be odd and >= 1).
Returns
UUID of the (possibly pre-existing) gate_case.
Source code
provsql.sql line 2103

◆ provenance_cmp()

UUID provsql.provenance_cmp ( UUID left_token,
OID comparison_op,
UUID right_token )

Create a comparison gate for HAVING clause provenance.

Parameters
left_tokenprovenance token for the left operand
comparison_opOID of the comparison operator
right_tokenprovenance token for the right operand

Implemented in C (gate_builders.c), with the declared cost of the PL/pgSQL function it was, so that plans stay the same.

Source code
provsql.sql line 2017

◆ provenance_cmp_times()

UUID provsql.provenance_cmp_times ( UUID cmp,
UUID[] tokens )

Combine a lifted aggregate comparison with the row annotation it supersedes only part of.

Parameters
cmpGate of the lifted comparison.
tokensRow-annotation factors at the level owning the comparison.
Returns
cmp multiplied with whatever of tokens it does not subsume.
Source code
provsql.sql line 2047

◆ provenance_eq()

UUID provsql.provenance_eq ( UUID token,
INT pos1,
INT pos2 )

Create an equijoin gate for where-provenance tracking.

Parameters
tokenchild provenance token
pos1attribute index in the first relation
pos2attribute index in the second relation

Implemented in C (gate_builders.c): the gate is created together with what it records, in one unanswered message.

Source code
provsql.sql line 1653

◆ provenance_monus()

UUID provsql.provenance_monus ( UUID token1,
UUID token2 )

Create a monus (difference) gate from two provenance tokens.

Implements m-semiring monus. Returns token1 if token2 is NULL (used for LEFT OUTER JOIN semantics in the EXCEPT rewriting).

Implemented in C (gate_builders.c), with the declared cost of the PL/pgSQL function it was, so that plans stay the same.

Source code
provsql.sql line 1624

◆ provenance_plus()

UUID provsql.provenance_plus ( UUID[] tokens)

Create a plus (sum) gate from an array of provenance tokens.

Filters out NULL and zero-gates; returns gate_zero() if all tokens are trivial, or a single token if only one remains. When the multiset is one for which this session planted a certified gate computing the same sum (see plant_canonical), that gate is returned. This is how the bounded-hop reachability route keeps the natural hop-discarding query on the linear evaluation route: it plants, for a vertex's per-length tokens, a certified gate over its native within-bound circuit. Otherwise the ordinary order-dependent recipe is used, so ordinary plus gates (and their formula rendering) are untouched.

Source code
provsql.sql line 1671

◆ provenance_project()

UUID provsql.provenance_project ( UUID token,
INT[] positions )

Create a project gate for where-provenance tracking.

Records the mapping between input and output attribute positions.

Parameters
tokenchild provenance token
positionsarray encoding attribute position mappings

Implemented in C (gate_builders.c): the gate is created together with what it records, in one unanswered message.

Source code
provsql.sql line 1639

◆ provenance_times()

UUID provsql.provenance_times ( UUID[] tokens)

Create a times (product) gate from multiple provenance tokens.

Filters out NULL and one-gates; returns gate_one() if all tokens are trivial, or a single token if only one remains.

When the surviving multiset is one for which this session planted a certified equivalent (see plant_canonical; the reachability rewriter does so for self-join conjunctions of reachability tokens, see plant_reach_cover), the planted gate is returned. The ordinary order-dependent recipe is used otherwise, so ordinary times gates (and their formula rendering) are untouched.

Implemented in C (gate_builders.c). The cost is declared as that of a PL/pgSQL function, which this function was: the planner then keeps evaluating it after the cheaper conditions, and the plans of rewritten queries, on which the order of the children of a ⊕ depends, stay the same.

Source code
provsql.sql line 1611

◆ resolve_fix_system()

UUID[] provsql.resolve_fix_system ( UUID sys)

The token of each tuple of the equation system sys (internal).

Tuples outside every cycle of the system get their right-hand side rebuilt over the tokens of the tuples they read, as a fixpoint iteration would build it; the tuples of each cyclic component a fixpoint gate over a system of their own. See fix_system.cpp.

Parameters
sysa fixsystem gate, with one unknown and one right-hand side per tuple
Returns
the token of each tuple, in the order of the unknowns
Source code
provsql.sql line 1743