Case Studies: Overview

The tutorial is the gentle first contact with ProvSQL: it walks through the core workflow – add provenance to a table, run a query, evaluate the result in a semiring – on a single small example. The case studies that follow are longer, self-contained worked examples, each built around a realistic dataset and centred on a different facet of the system. They go well beyond the tutorial in both the breadth of SQL they exercise and the depth to which they push a particular capability.

Each case study is independent: most ship a single self-contained setup.sql to download and load; case study 3 instead gives instructions for fetching the large Île-de-France GTFS dataset (not bundled, due to its size), and case study 4 loads bundled data files from the source tree under doc/casestudy4/data/. Each states its scenario and tasks up front and can be read on its own. Read the one whose theme matches what you want to learn; the coverage matrix at the end of this page is the quickest way to find which study demonstrates a given feature.

Tip

No install required. Every case study here except case study 3 (whose GTFS dataset is too large to bundle) runs in the ProvSQL Playground, the browser build of ProvSQL Studio, on a ready-made database – and all but case studies 3 and 4 also ship as runnable notebooks; each chapter links straight to what it has. The Playground bundles no external tools, so steps that explicitly call an external knowledge compiler (d4, c2d…) or graph-easy do not run there, but the built-in methods and everything else do. See the Playground note.

What each case study covers

Case study 1 – Intelligence Agency

The broadest tour of provenance evaluation: a security-classification scenario over seven agents drives a custom min-clearance semiring, where-provenance, circuit export, and the full probability-method line-up side by side (possible-worlds, Monte-Carlo, tree-decomposition, and knowledge compilation through d4 / c2d / dsharp / minic2d). Start here for a panoramic view.

Case study 2 – Open Science Database

Evidence synthesis over a fictional biomedical corpus – single-source vs. replicated claims, contradictions, strength-of-evidence ranking. The home of Shapley and Banzhaf values, attributing a result to the studies behind it.

Case study 3 – Île-de-France Public Transit

Boolean provenance at real-world scale. On the STIF GTFS dataset (hundreds of routes, tens of thousands of stops) a result token is true iff every record along the path carries the accessibility flag – which stops are reachable from Bagneux by a fully wheelchair-accessible journey?

Case study 4 – Government Ministers Over Time

The temporal extension and data-modification tracking. Over French and Singaporean ministers every fact carries a validity interval; the study time-travels, takes history and timeslices, and rolls back an INSERT / DELETE round-trip with undo.

Case study 5 – Wildlife Photo Archive

Uncertainty from a machine-learning detector: block-correlated alternatives via repair_key and the mulinput gate, with candidate species per bounding box. It contrasts probabilistic ranking against naive confidence thresholding and computes expected species counts with expected.

Case study 6 – City Air-Quality Sensor Network

The continuous-distribution surface end to end: random_variable columns (Normal / Uniform / Exponential / Erlang / categorical / mixture), arithmetic and comparison on them, analytic moments with Monte-Carlo fallback, and conditional inference. The first study driven primarily through ProvSQL Studio.

Case study 7 – Peer-Review Assignment and Knowledge Compilation

How a query’s shape, the schema’s keys, and the structure of the data decide which probability method is cheap and which needs a compiler. A peer-reviewing scenario organised by where tractability comes from: the query is safe (the four Dalvi-Suciu routes, including the Möbius-cancellation witness ), the query is -hard (the knowledge-compilation pipeline), or the data is well-structured (the joint-width compiler and recursive network reliability).

Case study 8 – ProvSQL as a Probability Calculator

ProvSQL as an exact, correlation-aware probability calculator driven in SQL: five textbook problems – base-rate fallacy, correlation breaking the independence formula, the method portfolio and its cost chooser, a continuous posterior by truncation, the conditional expectation of an aggregate – each a one-line query with the | (“given”) operator throughout. A compact, notebook-first tour of the probability surface.

Feature coverage matrix

The tables below cross-reference every user-facing feature documented under the User Guide against the tutorial and the eight case studies.

Columns:

• T – Tutorial (Who Killed Daphine?)

• 1 – Case study 1 (Intelligence Agency)

• 2 – Case study 2 (Open Science Database)

• 3 – Case study 3 (Île-de-France Public Transit)

• 4 – Case study 4 (Government Ministers Over Time)

• 5 – Case study 5 (Wildlife Photo Archive)

• 6 – Case study 6 (City Air-Quality Sensor Network)

• 7 – Case study 7 (Peer-Review Assignment and Knowledge Compilation)

• 8 – Case study 8 (ProvSQL as a Probability Calculator)

Cells: ✓ the feature is exercised; (✓) it is mentioned in passing but not actually executed; empty means it is not covered.

Setup and basics

Feature	T	1	2	3	4	5	6	7	8
add_provenance	✓	✓	✓	✓	✓	✓	✓	✓	✓
remove_provenance						✓
provenance() (SELECT-list)	✓	✓	✓	✓	✓	✓	✓	✓	✓
create_provenance_mapping (table)	✓	✓	✓	✓				✓
create_provenance_mapping_view					✓
Hand-built mapping table						✓
setup_search_path	(✓)
provsql.active GUC
gate_one / gate_zero (semiring constants)

Supported SQL constructs

Feature	T	1	2	3	4	5	6	7	8
SELECT-FROM-WHERE / inner JOIN	✓	✓	✓	✓	✓	✓	✓	✓
Self-join	✓	✓		✓		✓		✓
Subqueries in FROM / nested		✓	✓			✓
GROUP BY		✓	✓	✓	✓	✓	✓	✓	✓
SELECT DISTINCT	✓	✓		✓		✓		✓
EXCEPT (monus)	✓	✓				✓
UNION / UNION ALL							✓	✓
HAVING			✓				✓	✓
VALUES		✓				✓
CTE (WITH)						✓		✓	✓
WITH RECURSIVE								✓
LATERAL							✓
Window functions
FILTER clause on aggregates
CREATE TABLE AS SELECT	✓			✓	✓	✓			✓
Provenance-bearing VIEW			✓		✓
INSERT … SELECT (provenance propagation)

Aggregation

Feature	T	1	2	3	4	5	6	7	8
COUNT / SUM / MIN / MAX / AVG			✓	✓		✓		✓	✓
sum / avg / product over random_variable							✓
string_agg / array_agg
COUNT(DISTINCT …)
Arithmetic / cast on aggregate result			✓
Provenance-preserving agg_token arithmetic (+ - * /, agg-vs-agg, in HAVING)
agg_token_value_text / provsql.aggtoken_text_as_uuid GUC
choose aggregate
explode_table (agg_token column to rows)

Circuit inspection

Feature	T	1	2	3	4	5	6	7	8
get_gate_type		✓					✓
get_children		✓
identify_token		✓
get_nb_gates		✓
get_infos							✓
get_extra							✓
circuit_subgraph / resolve_input (Studio circuit mode)							✓	✓
simplified_circuit_subgraph							(✓)	✓

Knowledge compilation and safe queries

Feature	T	1	2	3	4	5	6	7	8
provsql.provenance = 'boolean'								✓
provsql.provenance = 'absorptive' (cyclic recursion)								✓
Bounded-treewidth network reliability (recursive reachability)								✓
provsql.classify_top_level GUC (TID/BID pills)								✓
Safe-query rewriter (hierarchical / read-once)								✓
Joint-width UCQ compiler (bounded joint treewidth)								✓
Möbius-inversion route (safe-by-cancellation UCQ)								✓
Tseytin CNF export (DIMACS)								✓
tseytin_cnf / tseytin_cnf_mapping								✓
ddnnf_stats								✓
compile_to_ddnnf / compile_to_ddnnf_dot								✓
tree_decomposition_dot								✓
tool_available (compiler-picker filter)								✓
HAVING Poisson-binomial pre-pass								✓
Inversion-free certificate (annotate / inversion_free_key / Studio IF badge)								✓
External-tool registry (provsql.tools, register_tool, set_tool_preference)								(✓)
provsql.fallback_compiler GUC
provsql.tool_search_path GUC
provsql.kcmcp_server GUC (managed KCMCP server)

Semiring evaluation

Feature	T	1	2	3	4	5	6	7	8
sr_boolean				✓
sr_boolexpr		✓				✓
sr_formula	✓	✓	✓	✓		✓		✓
sr_counting	✓		✓
sr_why			✓					(✓)
sr_how								(✓)
sr_which
sr_tropical
sr_viterbi
sr_lukasiewicz
sr_minmax / sr_maxmin		✓
sr_temporal / sr_interval_num / sr_interval_int					✓
Custom semiring via provenance_evaluate			✓
aggregation_evaluate

Probabilities

Feature	T	1	2	3	4	5	6	7	8
set_prob	✓	✓	✓			✓		✓	✓
get_prob							✓	✓
probability_evaluate (default fallback)		✓	✓			✓		✓	✓
Conditioning operator | / cond / given									✓
P(A | B) conditional probability									✓
expected(X | C) / variance(X | C) (conditional moments)									✓
'independent' method							✓	✓	✓
'possible-worlds' method	✓	✓							✓
'monte-carlo' method	(✓)	✓					✓	✓	✓
'tree-decomposition' method	(✓)	✓				✓	✓	✓
'compilation' (d4 / c2d / dsharp / minic2d)	(✓)	✓						✓
'inversion-free' method								✓
'wmc' counters								✓
'd-tree' method (certified anytime bounds)
'sieve' method (inclusion-exclusion)
'karp-luby' method (relative FPRAS)
'stopping-rule' method (additive FPRAS)
Guarantee request ('relative' / 'additive', cost-based chooser)
probability_bounds (cheap lower / upper marginals)
Studio benchmark panel								✓
expected(COUNT/SUM/MIN/MAX)						✓	✓		✓
repair_key (block-independent, mulinput)						✓		✓	✓
provsql.monte_carlo_seed GUC							✓
provsql.rv_mc_samples GUC							✓		✓
provsql.simplify_on_load GUC							✓

Continuous random variables

Feature	T	1	2	3	4	5	6	7	8
random_variable type / provsql.normal							✓		✓
provsql.uniform / provsql.exponential							✓
provsql.erlang / provsql.categorical							✓
provsql.mixture (Bernoulli and ad-hoc overloads)							✓
provsql.as_random and implicit numeric→rv casts							✓
Arithmetic on random_variable (+ - * /, unary -)							✓
Comparison < <= = <> >= > (planner-hook rewrite)							✓		✓
expected(random_variable) (unconditional)							✓		✓
variance(random_variable)							✓		✓
moment / central_moment / support over rv							✓		✓
Conditional inference via provenance() argument							✓		(✓)
rv_sample / rv_histogram							✓
rv_analytical_curves (PDF/CDF overlay)							✓

Shapley and Banzhaf values

Feature	T	1	2	3	4	5	6	7	8
shapley			✓
shapley_all_vars			✓
banzhaf			✓
banzhaf_all_vars			✓

Where-provenance

Feature	T	1	2	3	4	5	6	7	8
provsql.provenance = 'where'		✓	✓
where_provenance(col)		✓	✓

Data-modification tracking

Feature	T	1	2	3	4	5	6	7	8
provsql.update_provenance GUC					✓
INSERT / UPDATE / DELETE tracked					✓
update_provenance log table					✓
undo					✓

Temporal features

Feature	T	1	2	3	4	5	6	7	8
union_tstzintervals					✓
timeslice					✓
timetravel					✓
history					✓
time_validity_view extension					✓
get_valid_time

Export and visualisation

Feature	T	1	2	3	4	5	6	7	8
to_provxml		✓
view_circuit (graph-easy)		✓
provsql.verbose_level								(✓)
ProvSQL Studio (Circuit mode + Where mode)							✓	✓
ProvSQL Studio (Contributions mode)			✓