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

Definitions of compiled semirings. More...

Functions

VARCHAR provsql.sr_formula (ANYELEMENT token, REGCLASS token2value=NULL)
 Evaluate provenance as a symbolic formula (e.g., "a ⊗ b ⊕ c").
TABLE provsql.sr_formula_rows (ANYELEMENT token, REGCLASS token2value=NULL, INT max_size=50)
 The formula of a token as rows of bounded size.
INT provsql.sr_counting (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance over the counting semiring (ℕ).
VARCHAR provsql.sr_why (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance as why-provenance (set of witness sets).
VARCHAR provsql.sr_how (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance as how-provenance (canonical polynomial provenance ℕ[X], universal commutative-semiring provenance).
VARCHAR provsql.sr_which (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance as which-provenance (lineage: a single set of contributing labels).
VARCHAR provsql.sr_boolexpr (ANYELEMENT token, REGCLASS token2value=NULL)
 Evaluate provenance as a Boolean expression.
BOOLEAN provsql.sr_boolean (ANYELEMENT token, REGCLASS token2value=NULL)
 Evaluate provenance over the Boolean semiring (true/false).
BOOLEAN provsql.plain_truth (UUID token)
 Whether a token holds in the database as it is (internal).
BOOLEAN provsql.true_nonzero (UUID token)
 Structural universal-zero test (C backend of nonzero's default mode).
BOOLEAN provsql.nonzero (UUID token, TEXT semiring=NULL, REGCLASS mapping=NULL)
 Test whether a provenance annotation is nonzero.
BOOLEAN provsql.present (UUID token)
 Presence in the vanilla SQL answer on this instance.
FLOAT provsql.sr_tropical (ANYELEMENT token, REGCLASS token2value, BOOLEAN nonnegative=false)
 Evaluate provenance over the tropical (min-plus) m-semiring.
VARCHAR provsql.sr_regex (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance as a regular expression over the input labels.
VOID provsql.provenance_evaluate_tropical_paths (UUID token, REGCLASS costs, REGCLASS labels, OUT FLOAT cost, OUT TEXT paths)
 C implementation of sr_tropical_paths.
VOID provsql.sr_tropical_paths (ANYELEMENT token, REGCLASS costs, REGCLASS labels, OUT FLOAT cost, OUT TEXT paths)
 Evaluate provenance as the least cost of a derivation, with the derivations of that cost.
VOID provsql.provenance_evaluate_best_path (UUID token, REGCLASS costs, REGCLASS labels, OUT FLOAT cost, TEXT[] &path)
 C implementation of sr_best_path.
VOID provsql.sr_best_path (ANYELEMENT token, REGCLASS costs, REGCLASS labels, OUT FLOAT cost, TEXT[] &path)
 Evaluate provenance as one least-cost derivation, its cost and its labels.
FLOAT provsql.sr_viterbi (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance over the Viterbi (max-times) m-semiring.
FLOAT provsql.sr_lukasiewicz (ANYELEMENT token, REGCLASS token2value)
 Evaluate provenance over the Łukasiewicz fuzzy m-semiring.
ANYENUM provsql.sr_minmax (UUID token, REGCLASS token2value, ANYENUM element_one)
 Evaluate provenance over the min-max m-semiring on a user ENUM.
ANYENUM provsql.sr_maxmin (UUID token, REGCLASS token2value, ANYENUM element_one)
 Evaluate provenance over the max-min m-semiring on a user ENUM.
bigint provsql.subset_evaluate (UUID token, REGCLASS token2value, TEXT semiring, ANYENUM element_one)
 Evaluate provenance over a subset semiring, as a bitmask (internal).
ANYARRAY provsql.subset_labels (bigint mask, ANYENUM element_one)
 The labels of the ENUM type of element_one a bitmask holds (internal).
ANYENUM provsql.subset_settling (bigint mask, ANYENUM element_one)
 The settling level of a bitmask of clearance levels (internal).
BOOLEAN provsql.subset_member (UUID token, REGCLASS token2value, TEXT semiring, TEXT label)
 Membership of a label, given as TEXT, in a subset annotation (internal).
ANYARRAY provsql.sr_subset (UUID token, REGCLASS token2value, ANYENUM element_one)
 Evaluate provenance over the subsets of the labels of a user ENUM.
ANYARRAY provsql.sr_clearance (UUID token, REGCLASS token2value, ANYENUM element_one)
 Evaluate provenance as the set of clearance levels a tuple is visible at.
BOOLEAN provsql.visible_at (UUID token, REGCLASS token2value, TEXT level)
 Whether a tuple is visible at a clearance level.
VOID provsql.clearance_settling (UUID token, REGCLASS token2value, ANYENUM element_one, OUT ANYENUM settles_at, OUT BOOLEAN visible_at_top)
 The level from which the visibility of a tuple no longer changes.
VOID provsql.sr_consent (UUID token, REGCLASS token2value, ANYENUM element_one, OUT ANYARRAY purposes, OUT BOOLEAN unrestricted)
 Evaluate provenance over consented purposes.
BOOLEAN provsql.consented_for (UUID token, REGCLASS token2value, TEXT purpose)
 Whether a tuple may be used for a purpose.
ANYARRAY provsql.consent_purposes (UUID token, REGCLASS token2value, ANYENUM element_one)
 The purposes a tuple may be used for.
ANYARRAY provsql.consent_conflicts (UUID token, REGCLASS token2value, ANYENUM element_one)
 The purposes for which consent changes the answer.

Detailed Description

Definitions of compiled semirings.

Function Documentation

◆ clearance_settling()

VOID provsql.clearance_settling ( UUID token,
REGCLASS token2value,
ANYENUM element_one,
OUT ANYENUM settles_at,
OUT BOOLEAN visible_at_top )

The level from which the visibility of a tuple no longer changes.

The lowest clearance level settles_at such that the tuple is visible at every level from it to the top, or at none of them; visible_at_top says which. Meaningful for hierarchical levels.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to levels or arrays of levels.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
settles_atThe settling level.
visible_at_topWhether the tuple is visible at the top level.
Source code
provsql.sql line 12455

◆ consent_conflicts()

ANYARRAY provsql.consent_conflicts ( UUID token,
REGCLASS token2value,
ANYENUM element_one )

The purposes for which consent changes the answer.

The purposes whose consented tuples give a different answer about the tuple than the whole database: the tuple is returned for the purpose but not over the whole database (only possible through a negation reading a tuple the purpose was not consented for), or the reverse (the purpose lacks consent for a tuple the answer needs).

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to purposes or arrays of purposes.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
Source code
provsql.sql line 12539

◆ consent_purposes()

ANYARRAY provsql.consent_purposes ( UUID token,
REGCLASS token2value,
ANYENUM element_one )

The purposes a tuple may be used for.

The purposes for which :sqlfunc:consented_for holds: empty when the query over the whole database does not return the tuple.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to purposes or arrays of purposes.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
Source code
provsql.sql line 12516

◆ consented_for()

BOOLEAN provsql.consented_for ( UUID token,
REGCLASS token2value,
TEXT purpose )

Whether a tuple may be used for a purpose.

True when the query returns the tuple both over the whole database and over the tuples consented for purpose, given as TEXT, of the ENUM type of the value column of the mapping.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to purposes or arrays of purposes.
purposeThe purpose.
Source code
provsql.sql line 12499

◆ nonzero()

BOOLEAN provsql.nonzero ( UUID token,
TEXT semiring = NULL,
REGCLASS mapping = NULL )

Test whether a provenance annotation is nonzero.

Returns false only on a proof that the annotation is zero; true otherwise, so filtering with WHERE nonzero(provenance()) never discards a row whose annotation could be nonzero.

The default mode (semiring NULL) tests universal zero-ness: zero in every (m-)semiring under every leaf valuation, decided by sound structural rules (zero propagation through the gates; a comparison gate whose satisfying-world set is empty). Filtering on it can never contradict any downstream semiring evaluation.

A named semiring evaluates the circuit there and tests against that semiring's zero: 'BOOLEAN' is presence in the vanilla SQL answer on this instance (the mode that filters, e.g., the null-padded arm of a difference), 'counting' is bag multiplicity. An absent mapping reads every leaf as the semiring's one (true / 1); with a mapping, leaves take their mapped values.

A NULL token reads as the neutral 1 (an untracked row): true.

Parameters
tokenprovenance token to test
semiringNULL (universal zero test), 'BOOLEAN', or 'counting'
mappingoptional mapping table from tokens to leaf values
Source code
provsql.sql line 12095

◆ plain_truth()

BOOLEAN provsql.plain_truth ( UUID token)

Whether a token holds in the database as it is (internal).

sr_boolean(token) without a mapping, with a fast path for leaves. The rewriter filters by it the rows a displayed aggregate value reads, so that the value is the one plain SQL computes on the same data.

Source code
provsql.sql line 12060

◆ present()

BOOLEAN provsql.present ( UUID token)

Presence in the vanilla SQL answer on this instance.

WHERE present(provenance()) restores the result set the query has without provenance tracking, filtering the zero-annotated extras (antijoin arms, failed HAVING groups, unknown comparisons) that the rewriting keeps visible.

Shorthand for nonzero(token, 'BOOLEAN') with every leaf true, which reads that truth off the gates (plain_truth).

Source code
provsql.sql line 12137

◆ provenance_evaluate_best_path()

VOID provsql.provenance_evaluate_best_path ( UUID token,
REGCLASS costs,
REGCLASS labels,
OUT FLOAT cost,
TEXT[] & path )

C implementation of sr_best_path.

Source code
provsql.sql line 12222

◆ provenance_evaluate_tropical_paths()

VOID provsql.provenance_evaluate_tropical_paths ( UUID token,
REGCLASS costs,
REGCLASS labels,
OUT FLOAT cost,
OUT TEXT paths )

C implementation of sr_tropical_paths.

Source code
provsql.sql line 12196

◆ sr_best_path()

VOID provsql.sr_best_path ( ANYELEMENT token,
REGCLASS costs,
REGCLASS labels,
OUT FLOAT cost,
TEXT[] & path )

Evaluate provenance as one least-cost derivation, its cost and its labels.

Inputs are read as nonnegative float8 costs from costs (0 if absent) and as labels from labels (no label if absent). Returns the least cost, as sr_tropical over nonnegative costs, and the labels of one derivation of that cost, in the order of the query: on a path query, a shortest path. Among the derivations of least cost, the one returned has the fewest labels, and comes first in lexicographic order of its labels among those. With no derivation, the cost is infinite and the path NULL.

Source code
provsql.sql line 12240

◆ sr_boolean()

BOOLEAN provsql.sr_boolean ( ANYELEMENT token,
REGCLASS token2value = NULL )

Evaluate provenance over the Boolean semiring (true/false).

The optional token2value mapping gives the Boolean value of the leaves; a leaf it does not map, and every leaf when it is omitted, is true. Without a mapping, the result is whether the token holds in the database as it is, every input tuple present.

Source code
provsql.sql line 12037

◆ sr_boolexpr()

VARCHAR provsql.sr_boolexpr ( ANYELEMENT token,
REGCLASS token2value = NULL )

Evaluate provenance as a Boolean expression.

The optional token2value mapping labels the leaves of the formula: when omitted, leaves are rendered as bare x<id> placeholders.

Source code
provsql.sql line 12014

◆ sr_clearance()

ANYARRAY provsql.sr_clearance ( UUID token,
REGCLASS token2value,
ANYENUM element_one )

Evaluate provenance as the set of clearance levels a tuple is visible at.

The labels of the ENUM are clearance levels, in increasing order. A single level in the mapping makes a tuple visible at that level and every one above it; an array is an arbitrary set of levels (compartments). The result is the set of levels at which the query, run over the tuples visible at that level, returns the tuple: unlike :sqlfunc:sr_minmax, negation is exact, so a tuple can be visible at a level and not at a higher one.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to levels or arrays of levels.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
Source code
provsql.sql line 12416

◆ sr_consent()

VOID provsql.sr_consent ( UUID token,
REGCLASS token2value,
ANYENUM element_one,
OUT ANYARRAY purposes,
OUT BOOLEAN unrestricted )

Evaluate provenance over consented purposes.

The labels of the ENUM are purposes; the mapping gives the purposes each tuple is consented for (a purpose or an array of purposes). The result gives the purposes for which the query, run over the tuples consented for that purpose, returns the tuple, and whether the query over the whole database (unrestricted) returns it.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to purposes or arrays of purposes.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
purposesThe purposes for which the query returns the tuple.
unrestrictedWhether the query over the whole database returns it.
Source code
provsql.sql line 12480

◆ sr_counting()

INT provsql.sr_counting ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance over the counting semiring (ℕ).

Source code
provsql.sql line 11953

◆ sr_formula()

VARCHAR provsql.sr_formula ( ANYELEMENT token,
REGCLASS token2value = NULL )

Evaluate provenance as a symbolic formula (e.g., "a ⊗ b ⊕ c").

The mapping is optional (as for sr_boolexpr): formula renders whatever circuit it is given, and the measure-carrier circuits it is most useful on (random variables, arithmetic, mixtures) have no leaf mapping at all. Without one, input leaves render as the semiring's 𝟙.

◆ sr_formula_rows()

TABLE provsql.sr_formula_rows ( ANYELEMENT token,
REGCLASS token2value = NULL,
INT max_size = 50 )

The formula of a token as rows of bounded size.

The formula sr_formula writes, cut into rows: a sub-formula of more than max_size symbols (each leaf, operator or constant counting for one) is named (#2, #3…) and given a row of its own, where the rows that use it read its name. A sum, product or aggregate whose row would still be more than four times that long is written #k.1+…+#k.n (n terms), with its own operator, and each term #k.i has a row. The first row, #1, is the formula of the token. Rows are produced one at a time, each loading from the circuit store only what it writes, so a formula too large for sr_formula can be read in part: called in the select list, a LIMIT stops it early.

Parameters
tokena provenance token, an aggregate or a random variable
token2valuemapping table from input tokens to their names
max_sizethe most symbols a row writes before naming sub-formulas
Source code
provsql.sql line 11947

◆ sr_how()

VARCHAR provsql.sr_how ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance as how-provenance (canonical polynomial provenance ℕ[X], universal commutative-semiring provenance).

Source code
provsql.sql line 11981

◆ sr_lukasiewicz()

FLOAT provsql.sr_lukasiewicz ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance over the Łukasiewicz fuzzy m-semiring.

Inputs are read as float8 graded-truth values in \([0,1]\). Addition is \(\max\); multiplication is the Łukasiewicz t-norm \(\max(a + b - 1, 0)\), which preserves crisp truth and avoids the near-zero collapse of long product chains.

Source code
provsql.sql line 12273

◆ sr_maxmin()

ANYENUM provsql.sr_maxmin ( UUID token,
REGCLASS token2value,
ANYENUM element_one )

Evaluate provenance over the max-min m-semiring on a user ENUM.

Dual of :sqlfunc:sr_minmax: addition is ENUM-max, multiplication is ENUM-min. The fuzzy / availability / trust shape: alternatives combine to the most permissive label, joins combine to the strictest label. The third argument is a value of the carrier ENUM, used only for type inference; its value is ignored, so NULL::type is enough.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to ENUM values.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
Source code
provsql.sql line 12331

◆ sr_minmax()

ANYENUM provsql.sr_minmax ( UUID token,
REGCLASS token2value,
ANYENUM element_one )

Evaluate provenance over the min-max m-semiring on a user ENUM.

Inputs are read as values of a user-defined ENUM carrier; addition is ENUM-min, multiplication is ENUM-max. Bottom and top of the ENUM are derived from pg_enum.enumsortorder. The third argument is a value of the carrier ENUM, used only for type inference; its value is ignored, so NULL::type is enough.

The security shape: alternative derivations combine to the least sensitive label, joins combine to the most sensitive label.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to ENUM values.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
Source code
provsql.sql line 12302

◆ sr_regex()

VARCHAR provsql.sr_regex ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance as a regular expression over the input labels.

Inputs are read as labels (an empty label is the empty word); a derivation is the word of its labels, in the order of the query (that of the FROM clause for a join), and a tuple's value is the language of its derivations: | for union, · for concatenation, * for the Kleene star, ε and ∅ for the empty word and language.

Concatenation does not commute. A recursion on cyclic data has the regular expression of its derivations as exact value, provided every recursive FROM clause has the recursive relation at the same place (first, or last); otherwise it is refused.

Source code
provsql.sql line 12182

◆ sr_subset()

ANYARRAY provsql.sr_subset ( UUID token,
REGCLASS token2value,
ANYENUM element_one )

Evaluate provenance over the subsets of the labels of a user ENUM.

The powerset Boolean algebra: alternatives combine by union, joins by intersection, negation (EXCEPT, NOT EXISTS) by difference. A mapping value is a set of labels (an array of the ENUM), or a single label standing for itself. The result is the set of labels whose world contains the tuple. The third argument is a value of the ENUM, used only for type inference (NULL::type is enough). At most 63 labels.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to labels or arrays of labels.
element_oneA value of the carrier ENUM, used only for its type (NULL::type is enough).
Source code
provsql.sql line 12391

◆ sr_tropical()

FLOAT provsql.sr_tropical ( ANYELEMENT token,
REGCLASS token2value,
BOOLEAN nonnegative = false )

Evaluate provenance over the tropical (min-plus) m-semiring.

Inputs are read as float8 cost values; the additive identity is 'Infinity'::float8 and the multiplicative identity is 0. Returns the cost of the cheapest derivation.

With nonnegative, input costs are checked nonnegative and the semiring is absorptive: evaluation then also accepts circuits carrying the 'absorptive' assumption marker – notably the reachability circuits of the bounded-treewidth route, giving exact min-cost reachability on cyclic data.

Source code
provsql.sql line 12155

◆ sr_tropical_paths()

VOID provsql.sr_tropical_paths ( ANYELEMENT token,
REGCLASS costs,
REGCLASS labels,
OUT FLOAT cost,
OUT TEXT paths )

Evaluate provenance as the least cost of a derivation, with the derivations of that cost.

Inputs are read as float8 costs from costs (0 if absent) and as labels from labels (the empty word if absent). Returns the least cost, as sr_tropical over nonnegative costs, and the derivations of that cost as a regular expression over the labels, as sr_regex: on a path query, the shortest paths. A cycle of cost zero can be followed any number of times on a shortest path, and appears under a star; one of negative cost is refused.

Source code
provsql.sql line 12213

◆ sr_viterbi()

FLOAT provsql.sr_viterbi ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance over the Viterbi (max-times) m-semiring.

Inputs are read as float8 probability values in \([0,1]\). Returns the probability of the most likely derivation.

Source code
provsql.sql line 12253

◆ sr_which()

VARCHAR provsql.sr_which ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance as which-provenance (lineage: a single set of contributing labels).

Source code
provsql.sql line 11995

◆ sr_why()

VARCHAR provsql.sr_why ( ANYELEMENT token,
REGCLASS token2value )

Evaluate provenance as why-provenance (set of witness sets).

Source code
provsql.sql line 11967

◆ subset_evaluate()

bigint provsql.subset_evaluate ( UUID token,
REGCLASS token2value,
TEXT semiring,
ANYENUM element_one )

Evaluate provenance over a subset semiring, as a bitmask (internal).

Bit \(i\) stands for the label of rank \(i\) of the ENUM type of element_one; bit 63 for the unrestricted element of consent. semiring is subset, clearance or consent.

Source code
provsql.sql line 12353

◆ subset_labels()

ANYARRAY provsql.subset_labels ( bigint mask,
ANYENUM element_one )

The labels of the ENUM type of element_one a bitmask holds (internal).

Source code
provsql.sql line 12359

◆ subset_member()

BOOLEAN provsql.subset_member ( UUID token,
REGCLASS token2value,
TEXT semiring,
TEXT label )

Membership of a label, given as TEXT, in a subset annotation (internal).

The ENUM type is that of the value column of token2value.

Source code
provsql.sql line 12372

◆ subset_settling()

ANYENUM provsql.subset_settling ( bigint mask,
ANYENUM element_one )

The settling level of a bitmask of clearance levels (internal).

Source code
provsql.sql line 12364

◆ true_nonzero()

BOOLEAN provsql.true_nonzero ( UUID token)

Structural universal-zero test (C backend of nonzero's default mode).

Source code
provsql.sql line 12065

◆ visible_at()

BOOLEAN provsql.visible_at ( UUID token,
REGCLASS token2value,
TEXT level )

Whether a tuple is visible at a clearance level.

Membership of level in :sqlfunc:sr_clearance; the level is given as TEXT, of the ENUM type of the value column of the mapping.

Parameters
tokenProvenance token to evaluate.
token2valueMapping from input gates to levels or arrays of levels.
levelThe clearance level.
Source code
provsql.sql line 12435