 |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
|
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
SQL entry points for decomposition-aligned reachability compilation over bounded-treewidth data. More...
#include "postgres.h"#include "fmgr.h"#include "funcapi.h"#include "miscadmin.h"#include "access/htup_details.h"#include "catalog/pg_type.h"#include "utils/array.h"#include "utils/builtins.h"#include "utils/uuid.h"#include "provsql_utils.h"#include "provsql_mmap.h"#include "provsql_shmem.h"#include "c_cpp_compatibility.h"#include "ReachabilityCompiler.h"#include "CertifiedDDMaterialize.h"#include "provsql_utils_cpp.h"#include <map>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>
Go to the source code of this file.
Functions | |
| Datum | reachability_evaluate (PG_FUNCTION_ARGS) |
| PostgreSQL-callable entry point: exact reachability probability. | |
| Datum | reachability_compile_stats (PG_FUNCTION_ARGS) |
| PostgreSQL-callable entry point: probability plus compilation statistics. | |
| Datum | reachability_materialize (PG_FUNCTION_ARGS) |
| PostgreSQL-callable entry point: all-targets compilation and materialisation. | |
| Datum | reachability_materialize_hops (PG_FUNCTION_ARGS) |
| PostgreSQL-callable entry point: bounded-hop all-targets compilation and materialisation. | |
| Datum | reachability_materialize_any (PG_FUNCTION_ARGS) |
| PostgreSQL-callable entry point: per-group "some member
reachable" compilation and materialisation. | |
| Datum | reachability_materialize_cover (PG_FUNCTION_ARGS) |
| PostgreSQL-callable entry point: "every member vertex
reachable" (k-terminal / coverage) compilation and materialisation. | |
SQL entry points for decomposition-aligned reachability compilation over bounded-treewidth data.
Exposes ReachabilityCompiler (see ReachabilityCompiler.h) to SQL:
reachability_evaluate(): exact probability that the target vertex is reachable from the source vertex (two-terminal network reliability), in time linear in the number of edges for data of bounded treewidth;reachability_compile_stats(): same compilation, returning the probability together with structural statistics (data treewidth, number of bags, maximum DP state count, d-D size) that substantiate the linear-size claim in tests and benchmarks.Both take the edge relation in columnar form (parallel arrays of source vertices, target vertices, provenance tokens, and probabilities); the user-facing wrappers in provsql.sql gather those arrays from an arbitrary provenance-tracked edge relation. Vertices are dense integer IDs (the wrappers map arbitrary vertex values onto them).
Definition in file reachability_evaluate.cpp.
| Datum reachability_compile_stats | ( | PG_FUNCTION_ARGS | ) |
PostgreSQL-callable entry point: probability plus compilation statistics.
Arguments: see compileFromArgs(). Returns: composite (probability, data_treewidth, nb_bags, max_states, nb_gates, nb_variables).
Definition at line 257 of file reachability_evaluate.cpp.
| Datum reachability_evaluate | ( | PG_FUNCTION_ARGS | ) |
PostgreSQL-callable entry point: exact reachability probability.
Arguments: see compileFromArgs(). Returns: the probability that target is reachable from source.
Definition at line 236 of file reachability_evaluate.cpp.
| Datum reachability_materialize | ( | PG_FUNCTION_ARGS | ) |
PostgreSQL-callable entry point: all-targets compilation and materialisation.
Arguments: srcs int[], dsts int[], tokens uuid[], probs float8[], block_keys uuid[] (nil = independent tuple; otherwise the BID key variable grouping mutually exclusive alternatives) and block_indices int[], source_vertices int[], source_tokens uuid[] (the nil UUID marking a certain source), source_probs float8[], directed boolean. Returns: one (vertex, token) row per vertex reachable in the all-edges-present world, token being the materialised certified provenance circuit of "some present source reaches the vertex", wrapped in the 'absorptive' assumption marker (see wrapAssumedAbsorptive). This is the engine behind the rewriter's recursive-reachability route.
Definition at line 302 of file reachability_evaluate.cpp.
| Datum reachability_materialize_any | ( | PG_FUNCTION_ARGS | ) |
PostgreSQL-callable entry point: per-group "some member reachable" compilation and materialisation.
Arguments 0..9 as reachability_materialize, then two parallel arrays flattening the groups: group_ids int[] and member_vertices int[] (dense vertex IDs). For each distinct group, compiles the certified circuit of "some member vertex is
reachable from a present source" (compileAnyReach: the set-reachability bit folded through the decomposition DP, so the disjunction over the group's correlated per-vertex events is deterministic by construction) and materialises it; returns one (group_id, token) row per group, each token wrapped in the 'absorptive' assumption marker. The caller plants each token under the canonical address of the group's per-vertex reach tokens, keeping cross-vertex aggregations ("is some vertex of this region
reachable") on the linear certified route.
Definition at line 521 of file reachability_evaluate.cpp.
| Datum reachability_materialize_cover | ( | PG_FUNCTION_ARGS | ) |
PostgreSQL-callable entry point: "every member vertex reachable" (k-terminal / coverage) compilation and materialisation.
Arguments 0..9 as reachability_materialize, then member_vertices int[] (dense vertex IDs). Compiles the certified circuit of "every member vertex is reachable from a
present source" (compileCoverReach: the pending rescuer-set antichain folded through the decomposition DP, so the conjunction over the members' correlated per-vertex events is deterministic by construction), materialises it, and returns its token, wrapped in the 'absorptive' assumption marker. The caller plants the token under the times-canonical address of the members' per-vertex reach tokens, keeping reachability self-join conjunctions ("are
these k vertices all reachable") on the linear certified route – with the joint-worlds semantics: under nonnegative min-plus the token evaluates to the cost of the cheapest covering subgraph (directed Steiner cost), shared edges paid once.
Definition at line 627 of file reachability_evaluate.cpp.
| Datum reachability_materialize_hops | ( | PG_FUNCTION_ARGS | ) |
PostgreSQL-callable entry point: bounded-hop all-targets compilation and materialisation.
Arguments 0..9 as reachability_materialize, then hop_bound int (maximum walk length) and hop_seed int (the recursive CTE's base-arm hop constant, added to the reported lengths). Returns: one (vertex, hops, token) row per (vertex, walk length) pair achievable in the all-edges-present world – matching the rows the generic fixpoint derives for the hop-counting CTE shape, with token the materialised certified circuit of "some present source
reaches the vertex by a walk of exactly this many edges", wrapped in the 'absorptive' assumption marker.
Additionally pre-creates, for every vertex with at least two length rows, the gate a hop-discarding query's deduplication will mint – uuid5('plus{sorted tokens}') over the vertex's length tokens (multiset, as provenance_plus aggregates them) – as a certified single-child plus over the DP's native within-bound root, which computes the same Boolean function as that OR but deterministically by construction. The natural "is the vertex within k hops" query thus evaluates through the linear certified route instead of falling back to generic knowledge compilation over correlated per-length tokens; the pre-created gate is content-addressed, so the rewriter's later create_gate of the same UUID is an idempotent no-op.
Definition at line 394 of file reachability_evaluate.cpp.
