{ "nbformat": 4, "nbformat_minor": 5, "metadata": { "kernelspec": { "name": "provsql-studio", "display_name": "ProvSQL (SQL)", "language": "sql" }, "language_info": { "name": "sql" }, "provsql": { "scheme": "semiring", "database": "cs5", "generated_from": "doc/source/user/casestudy5.rst" } }, "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Case Study: Wildlife Photo Archive\n", "\n", "This case study, loosely inspired by a ProvSQL demonstration at EDBT 2025, applies ProvSQL to a database of wildlife photographs annotated by a species-detection model. It demonstrates the `VALUES` clause, [`repair_key`](https://provsql.org/doxygen-sql/html/group__table__management.html#gacfbe67438895e5f153b01bb9352cbc54) and the `mulinput` gate, ranking by probability versus thresholding, `EXCEPT`, common table expressions, [`expected`](https://provsql.org/doxygen-sql/html/group__probability.html#ga7124b41224adc29ff5405d5ad6db277e) aggregates, and the [`choose`](https://provsql.org/doxygen-sql/html/group__choose__aggregate.html#ga97d3c5ea62acf16a07b53fbb31546b0e) aggregate.\n", "\n", "## The Scenario\n", "\n", "A naturalist organisation maintains a database of wildlife photographs taken at four field stations in the Scottish Highlands. Each photo has been processed by a species-detection model that draws one or more *bounding boxes* around things it thinks are animals, and for each box reports a list of candidate species with a confidence score. A box can therefore appear with several species candidates (e.g., a partly-occluded shape might score 0.40 as red deer and 0.30 as roe deer); a photo can contain several boxes of the same species (e.g., three deer in a meadow shot).\n", "\n", "Your tasks:\n", "\n", "- find photos that contain specific combinations of species,\n", "- rank results by the probability that the combination is truly present,\n", "- compare probabilistic ranking against naive confidence thresholding,\n", "- exclude photos that contain unwanted species,\n", "- compute expected species counts per photo,\n", "- read the label of each bounding box as a distribution.\n", "\n", "## Setup" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*The following cells set up the database with all the content this notebook requires; run them first, ideally on a fresh database.*" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "DROP TABLE IF EXISTS photo CASCADE;\n", "CREATE TABLE photo (\n", " id integer PRIMARY KEY,\n", " station text NOT NULL,\n", " date date NOT NULL,\n", " filename text NOT NULL\n", ");" ], "outputs": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "DROP TABLE IF EXISTS species CASCADE;\n", "CREATE TABLE species (\n", " id integer PRIMARY KEY,\n", " name text NOT NULL,\n", " category text NOT NULL -- 'mammal', 'bird', 'reptile'\n", ");" ], "outputs": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "DROP TABLE IF EXISTS detection CASCADE;\n", "CREATE TABLE detection (\n", " photo_id integer NOT NULL,\n", " bbox_id integer NOT NULL,\n", " species_id integer, -- NULL: animal detected, species unidentified\n", " confidence double precision NOT NULL\n", ");" ], "outputs": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "TRUNCATE photo;\n", "COPY photo (id, station, date, filename) FROM stdin;\n", "1\tLoch Torridon\t2024-06-15\tLT-20240615-0001.jpg\n", "2\tLoch Torridon\t2024-06-15\tLT-20240615-0002.jpg\n", "3\tLoch Torridon\t2024-07-02\tLT-20240702-0001.jpg\n", "4\tLoch Torridon\t2024-07-15\tLT-20240715-0001.jpg\n", "5\tLoch Torridon\t2024-08-03\tLT-20240803-0001.jpg\n", "6\tLoch Torridon\t2024-08-12\tLT-20240812-0001.jpg\n", "7\tLoch Torridon\t2024-08-20\tLT-20240820-0001.jpg\n", "8\tLoch Torridon\t2024-09-01\tLT-20240901-0001.jpg\n", "9\tGlen Affric\t2024-06-20\tGA-20240620-0001.jpg\n", "10\tGlen Affric\t2024-07-04\tGA-20240704-0001.jpg\n", "11\tGlen Affric\t2024-07-15\tGA-20240715-0001.jpg\n", "12\tGlen Affric\t2024-08-08\tGA-20240808-0001.jpg\n", "13\tGlen Affric\t2024-08-25\tGA-20240825-0001.jpg\n", "14\tGlen Affric\t2024-09-10\tGA-20240910-0001.jpg\n", "15\tGlen Affric\t2024-09-22\tGA-20240922-0001.jpg\n", "16\tRannoch Moor\t2024-06-10\tRM-20240610-0001.jpg\n", "17\tRannoch Moor\t2024-06-25\tRM-20240625-0001.jpg\n", "18\tRannoch Moor\t2024-07-12\tRM-20240712-0001.jpg\n", "19\tRannoch Moor\t2024-07-30\tRM-20240730-0001.jpg\n", "20\tRannoch Moor\t2024-08-15\tRM-20240815-0001.jpg\n", "21\tRannoch Moor\t2024-09-02\tRM-20240902-0001.jpg\n", "22\tRannoch Moor\t2024-09-15\tRM-20240915-0001.jpg\n", "23\tCairngorms\t2024-06-18\tCG-20240618-0001.jpg\n", "24\tCairngorms\t2024-07-01\tCG-20240701-0001.jpg\n", "25\tCairngorms\t2024-07-20\tCG-20240720-0001.jpg\n", "26\tCairngorms\t2024-08-05\tCG-20240805-0001.jpg\n", "27\tCairngorms\t2024-08-22\tCG-20240822-0001.jpg\n", "28\tCairngorms\t2024-09-08\tCG-20240908-0001.jpg\n", "29\tCairngorms\t2024-09-20\tCG-20240920-0001.jpg\n", "30\tCairngorms\t2024-10-01\tCG-20241001-0001.jpg\n", "\\." ], "outputs": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "TRUNCATE species;\n", "COPY species (id, name, category) FROM stdin;\n", "1\tRed Deer\tmammal\n", "2\tRoe Deer\tmammal\n", "3\tRed Fox\tmammal\n", "4\tMountain Hare\tmammal\n", "5\tPine Marten\tmammal\n", "6\tRed Squirrel\tmammal\n", "7\tGolden Eagle\tbird\n", "8\tOsprey\tbird\n", "9\tCapercaillie\tbird\n", "10\tAdder\treptile\n", "11\tCommon Lizard\treptile\n", "12\tWildcat\tmammal\n", "13\tDomestic Dog\tmammal\n", "\\." ], "outputs": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "-- Detections. Each row is one (bounding-box, species) candidate produced\n", "-- by the classifier; multiple rows for the same (photo_id, bbox_id) pair\n", "-- represent alternative species hypotheses for that single bounding box.\n", "-- Photo 5: low confidences across multiple bboxes, with one ambiguous box\n", "-- (deer or roe deer); motivates probabilistic ranking in Step 7.\n", "-- Photo 9: deer + high-confidence dog (excluded from \"deer, no dogs\").\n", "-- Photo 14: deer + low-confidence near-miss dog (interesting EXCEPT case).\n", "-- Photo 22: ambiguous box plus several clear ones (mixed herd at Rannoch).\n", "-- Photos 5 and 9 each also have one *unidentified* detection (species_id\n", "-- NULL): the classifier saw an animal but assigned no species.\n", "-- These drive the NULL-semantics comparison of Step 12.\n", "TRUNCATE detection;\n", "COPY detection (photo_id, bbox_id, species_id, confidence) FROM stdin;\n", "1\t1\t1\t0.78\n", "1\t2\t1\t0.65\n", "1\t3\t1\t0.71\n", "2\t1\t1\t0.85\n", "2\t2\t3\t0.72\n", "3\t1\t3\t0.68\n", "3\t2\t6\t0.55\n", "4\t1\t5\t0.81\n", "5\t1\t1\t0.40\n", "5\t1\t2\t0.30\n", "5\t2\t1\t0.42\n", "5\t3\t1\t0.38\n", "5\t4\t3\t0.43\n", "5\t5\t3\t0.48\n", "5\t6\t\\N\t0.60\n", "6\t1\t7\t0.91\n", "7\t1\t1\t0.76\n", "7\t2\t1\t0.62\n", "7\t3\t1\t0.59\n", "7\t4\t2\t0.58\n", "8\t1\t9\t0.83\n", "9\t1\t1\t0.79\n", "9\t2\t13\t0.92\n", "9\t3\t\\N\t0.50\n", "10\t1\t1\t0.73\n", "10\t2\t3\t0.66\n", "11\t1\t5\t0.74\n", "11\t2\t6\t0.62\n", "12\t1\t3\t0.81\n", "12\t2\t4\t0.55\n", "13\t1\t12\t0.71\n", "14\t1\t1\t0.84\n", "14\t2\t13\t0.18\n", "15\t1\t7\t0.86\n", "15\t2\t8\t0.79\n", "16\t1\t10\t0.62\n", "16\t2\t11\t0.58\n", "17\t1\t3\t0.74\n", "17\t2\t4\t0.66\n", "18\t1\t1\t0.61\n", "18\t2\t3\t0.55\n", "19\t1\t9\t0.78\n", "20\t1\t7\t0.89\n", "21\t1\t11\t0.53\n", "21\t2\t10\t0.49\n", "22\t1\t1\t0.82\n", "22\t2\t1\t0.71\n", "22\t3\t3\t0.77\n", "22\t3\t1\t0.20\n", "22\t4\t3\t0.64\n", "22\t5\t2\t0.69\n", "22\t6\t2\t0.55\n", "23\t1\t5\t0.71\n", "23\t2\t6\t0.68\n", "24\t1\t1\t0.74\n", "24\t2\t4\t0.62\n", "25\t1\t7\t0.88\n", "25\t2\t9\t0.74\n", "26\t1\t12\t0.65\n", "27\t1\t8\t0.83\n", "28\t1\t1\t0.76\n", "28\t2\t3\t0.69\n", "29\t1\t5\t0.79\n", "30\t1\t6\t0.71\n", "30\t2\t4\t0.59\n", "\\." ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This creates three tables:\n", "\n", "- `photo` – 30 wildlife photographs, each tagged with a station name (Loch Torridon, Glen Affric, Rannoch Moor, or Cairngorms) and a date\n", "- `species` – 13 species across mammals, birds, and reptiles\n", "- `detection` – about 60 model-produced (bounding-box, species) candidate rows, each linking a photo and a bounding-box index to a candidate species with a confidence score; multiple rows for the same (`photo_id`, `bbox_id`) pair represent the classifier’s alternative species hypotheses for that single bounding box\n", "\n", "## Step 1: Explore the Database\n", "\n", "Inspect the tables. `detection` is *not* keyed on (`photo_id`, `bbox_id`): a single bounding box can appear in several rows, one per candidate species the classifier considered." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT * FROM photo ORDER BY id LIMIT 5;\n", "SELECT * FROM species ORDER BY id;\n", "SELECT photo_id, bbox_id, species_id, confidence\n", "FROM detection\n", "WHERE photo_id IN (5, 9, 14, 22)\n", "ORDER BY photo_id, bbox_id, confidence DESC;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 2: Enable Provenance and Create a Name Mapping\n", "\n", "Enable provenance tracking on `detection`. Each row receives a UUID circuit token that propagates through any downstream query." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT add_provenance('detection');" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To get readable formulas, we want to associate each detection’s provenance token with its species name. A *provenance mapping* in ProvSQL is a regular table with two columns named `value` and `provenance` (plus, for performance, an index on `provenance`). [`create_provenance_mapping`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga3a351113a8b4687b0acc678f7715cf1b) builds such a table from one column of a provenance-enabled relation; here we construct it by hand:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "DROP TABLE IF EXISTS species_mapping;\n", "CREATE TABLE species_mapping AS\n", " SELECT s.name AS value, d.provsql AS provenance\n", " FROM detection d JOIN species s ON s.id = d.species_id;\n", "\n", "SELECT remove_provenance('species_mapping');\n", "CREATE INDEX ON species_mapping(provenance);" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `CREATE TABLE AS` query inherits a `provsql` column from `detection`; [`remove_provenance`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga91ced31ffd25c227390042e5089cb200) strips it so only the `(value, provenance)` pair remains. A mapping can be populated from any expression – combine columns, filter rows, derive computed values – and any semiring-evaluation function (`sr_formula`, `sr_why`…) accepts the result. Such a table is a snapshot, though: rows inserted into `detection` later are not added to it, and a row whose input token [`replace_input`](https://provsql.org/doxygen-sql/html/group__gate__manipulation.html#ga416b70eb6e5156b435a90a695f3cc564) replaces keeps its value under the old token. A mapping built by [`create_provenance_mapping`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga3a351113a8b4687b0acc678f7715cf1b) follows a replaced token, and, created with `maintained => true`, new rows too.\n", "\n", "## Step 3: Inline Lookup with `VALUES`\n", "\n", "A `VALUES` clause defines an inline relation directly inside a query. ProvSQL treats it like any other source: its rows have no provenance of their own, and a join with them inherits provenance from the provenance-enabled rows.\n", "\n", "Here we use `VALUES` to define a small ad-hoc watchlist: a couple of species we want to look up by hand together with a human-readable label, instead of pulling them from the `species` table. Suppose we are interested in Red Deer (`species_id` 1, the dominant grazer whose density we want to track) and Red Fox (`species_id` 3, a generalist predator), and we want to tag the rows accordingly:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT v.label, p.id, p.station, p.date,\n", " sr_formula(provenance(), 'species_mapping') AS formula\n", "FROM (VALUES (1, 'mammal of interest'),\n", " (3, 'predator of interest')) AS v(species_id, label),\n", " detection d, photo p\n", "WHERE d.species_id = v.species_id AND d.photo_id = p.id\n", "ORDER BY p.id, v.label;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each output row carries the provenance of the underlying `detection` row alone: the formula is a single species token, even though the row also references `photo` and `VALUES`. Tables without provenance – including the `VALUES` rows – contribute no tokens.\n", "\n", "## Step 4: Conjunctive Query (Naive)\n", "\n", "Find photos that contain both Red Deer (`species_id` 1) and Red Fox (`species_id` 3) using a self-join on `detection`:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT p.id, p.station, p.date,\n", " sr_formula(provenance(), 'species_mapping') AS formula\n", "FROM detection d1\n", "JOIN detection d2 ON d1.photo_id = d2.photo_id\n", "JOIN photo p ON p.id = d1.photo_id\n", "WHERE d1.species_id = 1 AND d2.species_id = 3\n", "GROUP BY p.id, p.station, p.date\n", "ORDER BY p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Look at photo 5: the classifier produced three Red Deer candidate rows (in bounding boxes 1, 2 and 3) and two Red Fox candidate rows (in boxes 4 and 5). Its formula is the ⊕-sum of all six (deer, fox) pair products – every candidate row is an independent input. For these five boxes, that is right; but in box 1, the classifier also proposed a Roe Deer. A bounding box shows *at most one real animal*, so its Red Deer and Roe Deer rows cannot both be right: candidate rows that share a `(photo_id, bbox_id)` pair should be mutually exclusive rather than independent. Nothing in the schema says so, and the provenance treats them as independent.\n", "\n", "## Step 5: Mutually Exclusive Candidates with `repair_key`\n", "\n", "[`repair_key`](https://provsql.org/doxygen-sql/html/group__table__management.html#gacfbe67438895e5f153b01bb9352cbc54) rewrites the provenance so that rows sharing a key become alternatives under a single `mulinput` (multivalued input) gate, i.e., *at most one* of them is true (none, with what probability the candidates leave). Applied with the key `(photo_id, bbox_id)`, every bounding box becomes one mulinput variable whose values are the candidate species the classifier considered for that box.\n", "\n", "The key is given as a comma-separated list of columns. `repair_key` reinstalls the `provsql` column itself, so also drop the old mapping (whose tokens are about to become stale):" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "DROP TABLE species_mapping;\n", "SELECT remove_provenance('detection');\n", "\n", "SELECT repair_key('detection', 'photo_id,bbox_id');\n", "\n", "DROP TABLE IF EXISTS species_mapping;\n", "CREATE TABLE species_mapping AS\n", " SELECT s.name AS value, d.provsql AS provenance\n", " FROM detection d JOIN species s ON s.id = d.species_id;\n", "SELECT remove_provenance('species_mapping');\n", "CREATE INDEX ON species_mapping(provenance);" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Re-run the conjunctive query from Step 4, with [`sr_formula`](https://provsql.org/doxygen-sql/html/group__compiled__semirings.html#gae49f63c94b0094be6756f2f42d4caecd) and with [`sr_boolexpr`](https://provsql.org/doxygen-sql/html/group__compiled__semirings.html#ga41016a3000b008b59848687485b79425), which renders the underlying Boolean formula; the mapping labels each candidate by its species in both:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT p.id,\n", " sr_formula(provenance(), 'species_mapping') AS formula,\n", " sr_boolexpr(provenance(), 'species_mapping') AS bexpr\n", "FROM detection d1\n", "JOIN detection d2 ON d1.photo_id = d2.photo_id\n", "JOIN photo p ON p.id = d1.photo_id\n", "WHERE d1.species_id = 1 AND d2.species_id = 3 AND p.id IN (2, 5)\n", "GROUP BY p.id\n", "ORDER BY p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the Boolean expression, each candidate is now the value of a multivalued variable: `{i=v}[p]` reads “variable `i` takes value `v`, with probability `p`”, and the candidates of one bounding box are values of the same variable, at most one of which holds. The formula shows the candidates by their labels only: mutual exclusion concerns the probabilities of the candidates, which a semiring does not see. In this query every variable happens to have a single value, so the mutually exclusive structure is not visible yet. We will see a genuine multi-valued variable in the next step, where the deer/roe-deer candidates of one bounding box compose under the mutex constraint. [`view_circuit`](https://provsql.org/doxygen-sql/html/group__provenance__output.html#ga1c6caf1bb91c0cfdfc56c33666d41897) draws the same structure: each candidate a leaf with its label, wired to the variable it is a value of (`⋮`).\n", "\n", "## Step 6: Assign Probabilities and Verify Mutual Exclusion\n", "\n", "Each candidate row’s confidence becomes the probability that that classifier candidate is the true species for its bounding box:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT set_prob(provenance(), confidence) FROM detection;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To see that `repair_key` made a numerical difference, ask: *what is the probability that bounding box 1 of photo 5 corresponds to a deer-like animal* (`species_id` 1 = Red Deer or 2 = Roe Deer)? In the data, that bounding box has both candidate species recorded with confidences 0.40 and 0.30:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT photo_id, bbox_id,\n", " sr_boolexpr(provenance(), 'species_mapping') AS bexpr,\n", " ROUND(probability_evaluate(provenance(), 'tree-decomposition')::numeric, 4) AS p\n", "FROM detection\n", "WHERE photo_id = 5 AND bbox_id = 1 AND species_id IN (1, 2)\n", "GROUP BY photo_id, bbox_id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Boolean expression is now `{0=Red Deer}[0.400000] ∨ {0=Roe Deer}[0.300000]`: a single multivalued variable (variable 0) with two mutually exclusive values, Red Deer with probability 0.40 and Roe Deer with probability 0.30. Probability evaluation gives `0.7000`, the sum of the two confidences, since combining mutually exclusive events with ⊕ is just addition. Had we kept the original [`add_provenance`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga00f0d0b04b2b693c974e72aaf095cb3b) setup with each row as an independent input, the same query would have given `1 - (1 - 0.40) × (1 - 0.30) = 0.58` instead. The 0.12 gap is the practical effect of telling the engine “these candidates cannot both be true at once”.\n", "\n", "## Step 7: Probabilistic Ranking vs. Threshold Filtering\n", "\n", "Run the conjunctive query under two ranking strategies. First, by probability that *both* species are truly present:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT p.id, p.station, p.date,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM detection d1\n", "JOIN detection d2 ON d1.photo_id = d2.photo_id\n", "JOIN photo p ON p.id = d1.photo_id\n", "WHERE d1.species_id = 1 AND d2.species_id = 3\n", "GROUP BY p.id, p.station, p.date\n", "ORDER BY prob DESC, p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Second, by raw confidence threshold (every contributing detection must score at least 0.5):" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT DISTINCT p.id, p.station, p.date\n", "FROM detection d1\n", "JOIN detection d2 ON d1.photo_id = d2.photo_id\n", "JOIN photo p ON p.id = d1.photo_id\n", "WHERE d1.species_id = 1 AND d2.species_id = 3\n", " AND d1.confidence >= 0.5 AND d2.confidence >= 0.5\n", "ORDER BY p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Photo 5 is missed by thresholding (every individual candidate there scores below 0.5) but ranks reasonably under [`probability_evaluate`](https://provsql.org/doxygen-sql/html/group__probability.html#gabffa40fef0e37a75d39d4c39c4a1ec0f), because the weak deer candidates in several boxes plus the weak fox candidates combine into a non-trivial probability that *some* deer and *some* fox are truly there. Conversely, a photo whose top candidates only barely cross 0.5 passes the threshold but ends up low in the probability ranking.\n", "\n", "## Step 8: Absence Constraint with `EXCEPT`\n", "\n", "Find photos that contain a Red Deer but no Domestic Dog (`species_id` 13). ProvSQL represents `EXCEPT` with the ⊖ (monus) operator:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT p.id, p.station, p.date,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT photo_id FROM detection WHERE species_id = 1\n", " EXCEPT\n", " SELECT photo_id FROM detection WHERE species_id = 13\n", ") t\n", "JOIN photo p ON p.id = t.photo_id\n", "GROUP BY p.id, p.station, p.date\n", "ORDER BY prob DESC, p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Photos that contain a dog still appear in the output – `EXCEPT` is *not* a hard filter. Photo 9, with a high-confidence dog detection, ranks lower because the monus discounts strongly. Photo 14, where the dog detection has very low confidence, ranks higher: it is *probably* in the result, but not certainly. ProvSQL preserves both possibilities in the circuit and lets [`probability_evaluate`](https://provsql.org/doxygen-sql/html/group__probability.html#gabffa40fef0e37a75d39d4c39c4a1ec0f) weigh them.\n", "\n", "## Step 9: Multi-Condition Query via a CTE\n", "\n", "Combine Steps 7 and 8: photos with both Red Deer and Red Fox, with no Domestic Dog, ranked by probability. The query has three logical layers (co-occurrence, absence, ranking) and reads naturally as a CTE:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "WITH deer_and_fox AS (\n", " SELECT d1.photo_id\n", " FROM detection d1\n", " JOIN detection d2 ON d1.photo_id = d2.photo_id\n", " WHERE d1.species_id = 1 AND d2.species_id = 3\n", " GROUP BY d1.photo_id\n", "),\n", "no_dogs AS (\n", " SELECT photo_id FROM deer_and_fox\n", " EXCEPT\n", " SELECT photo_id FROM detection WHERE species_id = 13\n", ")\n", "SELECT p.id, p.station, p.date,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM no_dogs t\n", "JOIN photo p ON p.id = t.photo_id\n", "ORDER BY prob DESC, p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Provenance propagates through CTEs transparently; the same answer can be written with nested subqueries.\n", "\n", "Step 10: Expected Species Counts with [`expected`](https://provsql.org/doxygen-sql/html/group__probability.html#ga7124b41224adc29ff5405d5ad6db277e) ———————————————————–\n", "\n", "How many distinct species do we *expect* to really be in each photo? `COUNT(DISTINCT species_id)` answers it, next to `COUNT(*)`, which counts detections:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT p.id, p.station,\n", " ROUND(expected(COUNT(DISTINCT d.species_id))::numeric, 4) AS exp_species,\n", " ROUND(expected(COUNT(*))::numeric, 4) AS exp_detections\n", "FROM detection d\n", "JOIN photo p ON p.id = d.photo_id\n", "GROUP BY p.id, p.station\n", "ORDER BY exp_species DESC, p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A group’s row is there only in the worlds where one of its detections is, and the expectation is over those: `expected(COUNT(*))` is $\\sum_i P(\\text{detection}_i \\text{ is true})$ divided by the probability that the photo keeps a detection at all. `expected(COUNT(DISTINCT d.species_id))` sums, over the species instead, the probability that *at least one* detection of that species is true, with the same division. The two differ as soon as a species is detected in several bounding boxes: photo 1 has three Red Deer boxes, so about 2.19 expected detections but exactly one species, whichever boxes are real. As in SQL, `COUNT(DISTINCT …)` ignores `NULL`: the unidentified animal of photo 9 (more on it in Step 12) counts as a detection, not as a species.\n", "\n", "The same holds of `SUM` aggregates: the expected total confidence mass per photo:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT p.id, p.station,\n", " ROUND(expected(SUM(d.confidence))::numeric, 4) AS exp_total_conf\n", "FROM detection d\n", "JOIN photo p ON p.id = d.photo_id\n", "GROUP BY p.id, p.station\n", "ORDER BY exp_total_conf DESC, p.id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These queries use ProvSQL’s [`expected`](https://provsql.org/doxygen-sql/html/group__probability.html#ga7124b41224adc29ff5405d5ad6db277e) operator, which computes the expected value of a SQL aggregate over the probabilistic database defined by the per-row probabilities set in Step 6. Photo 22, with six bounding boxes and three species among them, ranks highest on every metric.\n", "\n", "## Step 11: Materialising a Subset with `INSERT … SELECT`\n", "\n", "Copying provenance-tracked rows into another **provenance-tracked** table preserves their lineage: the inserted rows keep their source tokens rather than getting fresh ones. Collect the high-confidence detections into a `confident_detections` table – enable provenance on the target *first*, then populate it with `INSERT … SELECT`:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "CREATE TABLE confident_detections (\n", " photo_id integer,\n", " bbox_id integer,\n", " species_id integer,\n", " confidence double precision);\n", "SELECT add_provenance('confident_detections');\n", "\n", "INSERT INTO confident_detections (photo_id, bbox_id, species_id, confidence)\n", "SELECT photo_id, bbox_id, species_id, confidence\n", "FROM detection\n", "WHERE confidence >= 0.9;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each inserted row inherits the provenance token of the `detection` row it came from, so a probability computed over `confident_detections` matches the one over the original row – the lineage followed the data:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT photo_id, species_id, confidence,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM confident_detections\n", "ORDER BY photo_id, species_id;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Note:**\n", "\n", "> The target table must be provenance-tracked before the insert. Inserting provenance-tracked rows into an *untracked* table drops the lineage, with a warning; use [`add_provenance`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga00f0d0b04b2b693c974e72aaf095cb3b) on the target first (or `CREATE TABLE … AS SELECT`, which carries provenance through directly).\n", "\n", "## Step 12: Unidentified Detections – Four Kinds of “Not”\n", "\n", "Two detections in the archive have **no species assignment**: the classifier saw an animal but could not identify it, and `species_id` is NULL (photo 5 at Loch Torridon, confidence 0.60, and photo 9 at Glen Affric, confidence 0.50). NULLs make the natural ways of asking “species detected at Loch Torridon but *not* at Glen Affric” genuinely different questions – in SQL itself, and therefore in the provenance and probabilities ProvSQL computes. Station names live in the *untracked* `photo` table; joining it in restricts to a station without touching the provenance (an untracked join partner contributes the neutral 1, as in Step 3).\n", "\n", "First, `EXCEPT`. SQL set difference matches tuples *syntactically*: two NULLs count as the same value, so Loch Torridon’s unidentified sighting is discounted by Glen Affric’s:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT species_id,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT species_id FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Loch Torridon'\n", " EXCEPT\n", " SELECT species_id FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Glen Affric'\n", ") t\n", "ORDER BY species_id NULLS LAST;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The NULL row comes out at probability $0.60 \\times (1 - 0.50) = 0.30$: an unidentified animal was seen at Loch Torridon *and* the Glen Affric unidentified detection is a false positive.\n", "\n", "Second, `NOT IN`. Under SQL’s three-valued logic, `x NOT IN Q` is *unknown* – and therefore not an answer – as soon as `Q` contains a NULL, whatever `x` is. A single unidentified sighting at Glen Affric poisons the certification of **every** species:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT species_id,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT DISTINCT species_id\n", " FROM (SELECT d.species_id FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Loch Torridon'\n", " AND d.species_id NOT IN (SELECT d2.species_id FROM detection d2\n", " JOIN photo p2 ON d2.photo_id = p2.id\n", " WHERE p2.station = 'Glen Affric')) lt\n", ") t\n", "ORDER BY species_id NULLS LAST;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Every probability is exactly half its `NOT EXISTS` counterpart below: each answer now carries the extra factor “the Glen Affric unidentified detection is a false positive” (probability 0.50). The NULL row itself drops to essentially 0 – a NULL can only pass `NOT IN` against an empty set, i.e., in the worlds where *no* Glen Affric detection at all is a true positive.\n", "\n", "Third, `NOT EXISTS` with an explicit equality. `d2.species_id = d.species_id` is never *true* when either side is NULL, so the unidentified sightings are simply ignored: Glen Affric’s removes nothing, and Loch Torridon’s own NULL row survives at its full detection probability (0.60):" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT species_id,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT DISTINCT species_id\n", " FROM (SELECT d.species_id FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Loch Torridon'\n", " AND NOT EXISTS (SELECT 1 FROM detection d2\n", " JOIN photo p2 ON d2.photo_id = p2.id\n", " WHERE p2.station = 'Glen Affric'\n", " AND d2.species_id = d.species_id)) lt\n", ") t\n", "ORDER BY species_id NULLS LAST;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Fourth, an outer join. Keeping the Loch Torridon sightings that find no Glen Affric partner (`LEFT JOIN` … `IS NULL`) is the same question as `NOT EXISTS`: the join condition is an equality, which never matches a NULL. The padded rows carry the provenance of the *absence* of a match, and the probabilities are those of `NOT EXISTS`, row for row:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT species_id,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT DISTINCT d.species_id\n", " FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " LEFT JOIN (SELECT d2.species_id FROM detection d2\n", " JOIN photo p2 ON d2.photo_id = p2.id\n", " WHERE p2.station = 'Glen Affric') g\n", " ON g.species_id = d.species_id\n", " WHERE p.station = 'Loch Torridon' AND g.species_id IS NULL\n", ") t\n", "ORDER BY species_id NULLS LAST;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Four idioms, three different answers – matching what vanilla SQL returns on each query, with possible-worlds-correct probabilities on top. The general rules behind this behaviour (which comparisons treat NULLs as unknown, where SQL switches to syntactic matching, and what that means for provenance circuits) are spelled out in [the NULL semantics chapter](https://provsql.org/docs/user/nulls.html).\n", "\n", "## Step 13: Species Seen at Both Stations\n", "\n", "The positive question – species detected at *both* Loch Torridon and Glen Affric – has the same two readings. `INTERSECT` matches tuples syntactically, NULL included:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT species_id,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT species_id FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Loch Torridon'\n", " INTERSECT\n", " SELECT species_id FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Glen Affric'\n", ") t\n", "ORDER BY species_id NULLS LAST;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The unidentified row comes out at $0.60 \\times 0.50 = 0.30$: both unidentified sightings are true positives. A quantified comparison, `= ANY`, compares values instead, and a NULL equals nothing:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT species_id,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT DISTINCT d.species_id\n", " FROM detection d\n", " JOIN photo p ON d.photo_id = p.id\n", " WHERE p.station = 'Loch Torridon'\n", " AND d.species_id = ANY (SELECT d2.species_id FROM detection d2\n", " JOIN photo p2 ON d2.photo_id = p2.id\n", " WHERE p2.station = 'Glen Affric')\n", ") t\n", "ORDER BY species_id NULLS LAST;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The species rows are the same, and the unidentified row is gone. The probabilities are consistent across queries: a species seen at Loch Torridon is seen either at both stations or only there, so its `INTERSECT` probability here and its `EXCEPT` probability in Step 12 add up to the probability that it is seen at Loch Torridon at all – for the Red Deer, 0.9909 + 0.0091 = 1, and for the unidentified row, 0.30 + 0.30 = 0.60.\n", "\n", "## Step 14: The Label of Each Bounding Box\n", "\n", "Since Step 5, the candidates of a bounding box are mutually exclusive: in each world, the label of the box is the candidate present, if any, with the probabilities of Step 6. Suppose instead that each candidate came from a detector of its own, one per species, so that both deer could be detected on box 1 of photo 5 at once. Copy the detections, each row an independent input:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "CREATE TABLE detection_indep AS\n", " SELECT photo_id, bbox_id, species_id, confidence FROM detection;\n", "SELECT remove_provenance('detection_indep');\n", "SELECT add_provenance('detection_indep');\n", "SELECT set_prob(provenance(), confidence) FROM detection_indep;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The copy inherits the `provsql` column of `detection`, with its mutually exclusive tokens: [`remove_provenance`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga91ced31ffd25c227390042e5089cb200) drops it, and [`add_provenance`](https://provsql.org/doxygen-sql/html/group__table__management.html#ga00f0d0b04b2b693c974e72aaf095cb3b) gives every row a token of its own.\n", "\n", "To report one label per box, take the most confident candidate detected. The [`choose`](https://provsql.org/doxygen-sql/html/group__choose__aggregate.html#ga97d3c5ea62acf16a07b53fbb31546b0e) aggregate picks one value of its group, in each world the first in its `ORDER BY` among the rows present. Grouping by that value turns it into a distribution over labels:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "provsql": {} }, "source": [ "SELECT photo_id, bbox_id, label,\n", " ROUND(probability_evaluate(provenance())::numeric, 4) AS prob\n", "FROM (\n", " SELECT d.photo_id, d.bbox_id,\n", " choose(s.name ORDER BY d.confidence DESC) AS label\n", " FROM detection_indep d JOIN species s ON s.id = d.species_id\n", " WHERE d.photo_id = 5\n", " GROUP BY d.photo_id, d.bbox_id\n", ") t\n", "GROUP BY photo_id, bbox_id, label\n", "ORDER BY photo_id, bbox_id, label;" ], "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Red Deer, the more confident candidate of box 1, is its label whenever it is detected, with probability 0.40. Roe Deer is the label only when detected without Red Deer, with probability 0.60 × 0.30 = 0.18, and in the remaining worlds no candidate is detected and the box has no label. `ORDER BY d.confidence` would instead give Roe Deer 0.30 and Red Deer 0.70 × 0.40 = 0.28: when several candidates are present, the `ORDER BY` of [`choose`](https://provsql.org/doxygen-sql/html/group__choose__aggregate.html#ga97d3c5ea62acf16a07b53fbb31546b0e) decides the label. On `detection`, whose candidates are mutually exclusive, the same query returns the confidences of Step 6 whatever the order, as at most one candidate is ever present. Boxes 2 to 5 have a single candidate, and box 6, whose only candidate is unidentified, has no species to join and no row." ] } ] }