![]() |
ProvSQL SQL API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
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. | |
Definitions of compiled semirings.
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to levels or arrays of levels. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| settles_at | The settling level. |
| visible_at_top | Whether the tuple is visible at the top level. |
| 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).
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to purposes or arrays of purposes. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to purposes or arrays of purposes. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to purposes or arrays of purposes. |
| purpose | The purpose. |
| 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.
| token | provenance token to test |
| semiring | NULL (universal zero test), 'BOOLEAN', or 'counting' |
| mapping | optional mapping table from tokens to leaf values |
| 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.
| 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).
| 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.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_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.
| 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.
| 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.
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to levels or arrays of levels. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to purposes or arrays of purposes. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| purposes | The purposes for which the query returns the tuple. |
| unrestricted | Whether the query over the whole database returns it. |
| INT provsql.sr_counting | ( | ANYELEMENT | token, |
| REGCLASS | token2value ) |
Evaluate provenance over the counting semiring (ℕ).
| 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 𝟙.
| 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.
| token | a provenance token, an aggregate or a random variable |
| token2value | mapping table from input tokens to their names |
| max_size | the most symbols a row writes before naming sub-formulas |
| VARCHAR provsql.sr_how | ( | ANYELEMENT | token, |
| REGCLASS | token2value ) |
Evaluate provenance as how-provenance (canonical polynomial provenance ℕ[X], universal commutative-semiring provenance).
| 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.
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to ENUM values. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to ENUM values. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| 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.
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to labels or arrays of labels. |
| element_one | A value of the carrier ENUM, used only for its type (NULL::type is enough). |
| 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.
| 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.
| 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.
| VARCHAR provsql.sr_which | ( | ANYELEMENT | token, |
| REGCLASS | token2value ) |
Evaluate provenance as which-provenance (lineage: a single set of contributing labels).
| VARCHAR provsql.sr_why | ( | ANYELEMENT | token, |
| REGCLASS | token2value ) |
Evaluate provenance as why-provenance (set of witness sets).
| 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.
| ANYARRAY provsql.subset_labels | ( | bigint | mask, |
| ANYENUM | element_one ) |
The labels of the ENUM type of element_one a bitmask holds (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).
The ENUM type is that of the value column of token2value.
| ANYENUM provsql.subset_settling | ( | bigint | mask, |
| ANYENUM | element_one ) |
The settling level of a bitmask of clearance levels (internal).
| BOOLEAN provsql.true_nonzero | ( | UUID | token | ) |
Structural universal-zero test (C backend of nonzero's default mode).
| 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.
| token | Provenance token to evaluate. |
| token2value | Mapping from input gates to levels or arrays of levels. |
| level | The clearance level. |