.. nb:name: cs7 .. nb:database: cs7 Case Study: Peer-Review Assignment and Knowledge Compilation ============================================================ A program chair has a database of uncertain facts about a conference -- who bid on what, who is expert in what, which papers are assigned -- and keeps asking *probability* questions of it: how likely is it that every paper is competently covered? that this reviewer is conflicted? Each question is a SQL query whose answer carries a probability. The same kind of question can be easy or :math:`\#P`-hard **depending on its exact shape, the schema's keys, and the data**, and ProvSQL routes each to a different mechanism. This case study walks that landscape over one reviewing dataset, driven through :doc:`ProvSQL Studio `, organised by *where the tractability comes from*: * **Part A -- the query is safe.** Some questions are tractable whatever the data, because the query (with the schema's keys) is *safe*. Four steps cover the four ways that happens. * **Part B -- the query is hard.** When no query-side route applies, computing the probability is genuinely :math:`\#P`-hard, and ProvSQL hands the provenance to a knowledge compiler. * **Part C -- the data is well-structured.** A hard *query* can still be easy on *this* data, because ProvSQL compiles along the structure of the data itself. The data -------- Several relations carry per-tuple probabilities. Three drive the coverage questions: * ``bid(reviewer, paper)`` -- a reviewer offered to review a paper; the probability is how firm the bid is. * ``expertise(reviewer, topic)`` -- the reviewer's area of competence. * ``topic_of(paper, topic)`` -- the paper is about a topic. The instance has 14 reviewers, 4 topics and 7 papers. **One modelling choice matters throughout:** ``expertise`` has a **primary key on** ``reviewer`` -- each reviewer has exactly one area (the functional dependency ``reviewer`` :math:`\to` ``topic``). Several reviewers share each area on purpose (five do databases), so a paper's coverage is genuinely entangled: the same ``topic_of`` tuple is shared by every co-expert who bid on the paper. The remaining relations -- ``recommend`` / ``champion``, an external-review pool, ``assignment``, and two citation / collaboration graphs -- are introduced where first used. Setup ----- .. nb:skip .. tip:: **Prefer not to install? Use the Playground.** You can skip the manual setup below: open this case study `as a runnable notebook in the ProvSQL Playground `_, or open the bare `cs7 database `_ and follow the Studio steps as you read. The steps that call an *external* compiler (``d4``, ``c2d``) will not run in the Playground, which bundles none; the built-in tree-decomposition compiler and everything else do, so the in-process comparison is fully reproducible. See the :ref:`Playground note `. .. nb:omit-begin This case study assumes a working ProvSQL installation (see :doc:`getting-provsql`) and a running ProvSQL Studio session (see :doc:`studio`). Download :download:`setup.sql <../../casestudy7/setup.sql>` and load it into a fresh database: .. code-block:: bash createdb peer_review_demo psql -d peer_review_demo -f setup.sql .. nb:omit-end .. nb:setup: ../../casestudy7/setup.sql The script seeds each tuple's probability and tags every uncertain relation in Studio's schema panel with a :sc:`prov-tid` pill (tuple-independent), or :sc:`prov-bid` for the block-correlated ``assignment``. The provenance class is the :guilabel:`Boolean` / :guilabel:`Absorptive` / :guilabel:`Semiring` / :guilabel:`Where` toggle (see :ref:`studio-query-toggles`): most steps want :guilabel:`Boolean`, where ProvSQL's safe-query rewriter and data compilers are active; :guilabel:`Semiring` turns them off and shows the literal circuit; :guilabel:`Absorptive` is needed only for the cyclic recursion at the very end. Part A: The Query Is Safe ------------------------- A *safe* query is one whose exact probability is PTIME in the data -- whatever the data looks like :cite:`DBLP:journals/jacm/DalviS12`. ProvSQL recognises safety at planning time and answers without any compiler. There are exactly four ways a (self-join-free) query can be safe, and the four steps below are one of each. Safe by shape ^^^^^^^^^^^^^ *We need a coverage shortlist: which papers have at least one plausibly qualified reviewer -- someone who bid on the paper and has some area of expertise?* .. code-block:: postgresql SELECT p.id, p.title FROM bid b, expertise e, papers p WHERE b.reviewer = e.reviewer AND b.paper = p.id GROUP BY p.id, p.title ORDER BY p.id Click into ``p1``'s ``provsql`` cell and, in the eval strip, pick :guilabel:`Marginal probability` with the ``independent`` method. It returns ``≈ 0.666`` instantly, and the other exact methods, such as ``tree-decomposition``, give the same value. Why it works: the query is **hierarchical** -- the atoms mentioning ``topic`` (just ``expertise``) sit inside those mentioning ``reviewer`` (``bid`` and ``expertise``) -- so a paper's coverage is an ``OR`` over reviewers of independent terms, with no tuple shared. The circuit is **read-once**, and ``independent`` is exact on read-once circuits. This is the easiest corner: safe by the query's shape alone, no key needed. Safe by a key ^^^^^^^^^^^^^ *Now the question that matters for assignment: is paper* ``p1`` *competently covered -- did someone bid on it who is expert in one of* ``p1``\ *'s own topics?* .. code-block:: postgresql SELECT DISTINCT 1 FROM bid b, expertise e, topic_of t WHERE b.reviewer = e.reviewer AND e.topic = t.topic AND b.paper = 'p1' AND t.paper = 'p1' Try ``independent`` with the toggle on :guilabel:`Semiring`: it **errors** -- *"Not an independent circuit"*. Switch the toggle to :guilabel:`Boolean` and try again: it succeeds, ``≈ 0.4259``, matching ``tree-decomposition`` exactly. Under :guilabel:`Semiring`, the circuit is the query's literal lineage. This query is non-hierarchical -- ``bid`` mentions only ``reviewer``, ``topic_of`` only ``topic``, ``expertise`` both -- so that lineage reuses the shared ``topic_of(p1, t1)`` tuple (Alice, Bob and Judy are all database experts who bid on ``p1``) and is *not* read-once, hence the error. :guilabel:`Boolean` turns on the safe-query rewriter, which restructures the query before it runs. The restructured circuit has the same probability, but not necessarily the same value in every semiring, which is why the rewriter waits for the toggle. Here it relies on the **key**: because ``expertise`` is keyed on ``reviewer``, each reviewer has a single topic, so the rewriter can group the experts by topic and factor that shared tuple out: .. math:: \bigvee_{t} \; \mathit{topic\_of}(p_1, t) \;\wedge\; \Bigl(\bigvee_{r:\,\mathit{exp}(r,t)} \mathit{bid}(r, p_1) \wedge \mathit{exp}(r, t)\Bigr). Each leaf now appears once -- read-once again, and ``independent`` is exact. The lesson: **safety depends on the query and the keys together**. Drop the key: .. code-block:: postgresql ALTER TABLE expertise DROP CONSTRAINT expertise_pkey; and ``independent`` still returns ``0.4259``, but the route changes -- the query is now genuinely hard and falls through to Part C's data compiler. Add the key back before continuing: .. code-block:: postgresql ALTER TABLE expertise ADD PRIMARY KEY (reviewer); Safe by a query-derived order ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ For this step the fixture adds **Olga** (``r15``), a prolific reviewer who skimmed a 24-paper batch, with two post-review signals: ``recommend`` (she recommended a paper) and ``champion`` (she would champion it at the meeting). *Which reviewers have bids that back up both a recommendation and a championing -- a sign they engaged deeply?* .. code-block:: postgresql SELECT r.id, r.name FROM bid b1, recommend a, bid b2, champion c, reviewers r WHERE b1.reviewer = a.reviewer AND b1.paper = a.paper AND b1.reviewer = b2.reviewer AND b2.reviewer = c.reviewer AND b2.paper = c.paper AND b1.reviewer = r.id GROUP BY r.id, r.name On Olga's row, try the heavy methods first: ``tree-decomposition`` gives up (*"Treewidth greater than 10"*), ``possible-worlds`` refuses (over 64 inputs), and ``compilation`` with an external compiler such as ``d4`` is cut off by ``statement_timeout`` on the 24-paper instance. Then try ``inversion-free`` -- or just the default ``exact`` method -- and it returns ``≈ 0.9753`` in milliseconds. Why the gap: grouping on the reviewer makes the two evidence sides share the ``bid(r15, *)`` tuples, so the lineage is **not** read-once and every circuit-level method treats it as hard. But the query is a *consistent-unification self-join* with a single root variable, which is the **inversion-free** condition :cite:`DBLP:conf/icdt/JhaS11`: it admits a linear-size OBDD over a variable order *read from the query*. ProvSQL finds that order at planning time (the teal :sc:`IF` badge on the root is the certificate) and builds a deep, chain-like d-DNNF -- tractability that is invisible in the materialised circuit and visible only in the query. .. _cs7-mobius: Safe by cancellation (Möbius inversion) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The fourth corner is the subtlest, and it needs its own little world: an **external-review pool**, isolated from the main instance, where four area chairs (``c1``–``c4``) each run three independent assessment passes -- a *prescreen*, a *score* and a *flag* -- over four embargoed submissions (``e1``–``e4``), with ``lead_chair`` marking senior chairs and ``urgent_sub`` the time-critical submissions. *Is the pool in a "well-attended" state?* -- a union of four overlapping patterns of who-assessed-what. This is the textbook query :math:`q_9` / :math:`Q_W` (Dalvi & Suciu). .. code-block:: postgresql SELECT 1 FROM lead_chair r, prescreen a1, flag_pass a3, urgent_sub t3 WHERE r.chair = a1.chair AND a3.sub = t3.sub UNION SELECT 1 FROM prescreen b1, score_pass b2, flag_pass b3, urgent_sub tb WHERE b1.chair = b2.chair AND b1.sub = b2.sub AND b3.sub = tb.sub UNION SELECT 1 FROM score_pass c2, flag_pass c3, flag_pass c3b, urgent_sub tc WHERE c2.chair = c3.chair AND c2.sub = c3.sub AND c3b.sub = tc.sub UNION SELECT 1 FROM lead_chair d, prescreen d1, prescreen d1b, score_pass d2, score_pass d2b, flag_pass d3 WHERE d.chair = d1.chair AND d1b.chair = d2.chair AND d1b.sub = d2.sub AND d2b.chair = d3.chair AND d2b.sub = d3.sub Try :guilabel:`Marginal probability` with the ``exact`` method and the toggle on :guilabel:`Boolean`: it returns ``≈ 0.0569`` (the chooser routes it through the Möbius compiler; once the μ root is rendered you can also pick the ``mobius`` method explicitly). Any circuit compiler blows up instead: :math:`q_9` provably has no polynomial OBDD / FBDD / decision-DNNF :cite:`DBLP:journals/mst/AmarilliCMS20`. Why it is nonetheless safe: writing the probability by inclusion-exclusion, the one :math:`\#P`-hard term -- the conjunction of all four patterns -- gets a **zero Möbius coefficient** and cancels, leaving only easy terms. ProvSQL's Möbius compiler computes exactly that signed combination. The circuit also carries the whole literal lineage, so Studio shows a *Circuit too large* card in place of it. Choose :guilabel:`Render at depth 1`: the root is a single **μ** (Möbius-function) gate, each child edge labelled with its integer coefficient, the hard term among them cancelled to zero. (The pool is **dense** on purpose: on sparse data Part C's compiler would also handle it and hide the point. Unlike the safe-query rewrite of the key step, which replaces the provenance with that of a restructured query, the μ gate keeps the query's literal lineage as a child, so ``shapley`` and ``sr_formula`` still evaluate that lineage.) .. _cs7-route-map: The four routes at a glance ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ These four steps are the complete set of exact query-side routes -- the Dalvi-Suciu dichotomy made operational: .. list-table:: :header-rows: 1 :widths: 34 38 28 * - The query is safe because… - ProvSQL route - Witness in this Part * - its **shape** is hierarchical - read-once lineage → ``independent`` (no rewrite) - coverage, all papers * - a **key** makes it read-once - safe-query rewrite (FD) - ``p1`` competent coverage * - a query-derived **order** - inversion-free certificate - Olga's bid self-join * - its :math:`\#P`-hard term **cancels** - Möbius compiler - the review pool (:math:`q_9`) All four are PTIME, need no external tool, and assume tuple-independent inputs. When none applies, the query is genuinely hard (Part B) -- unless the data rescues it (Part C). See the :ref:`full tractability table `. Part B: The Query Is Hard ------------------------- Ask the competent-coverage question of the **whole program** instead of one paper and every Part A route fails. This Part follows that hard query through knowledge compilation. The hard query, and what a compiler does with it ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ *Is* **any** *paper competently covered?* .. code-block:: postgresql SELECT DISTINCT 1 FROM bid b, expertise e, topic_of t WHERE b.reviewer = e.reviewer AND e.topic = t.topic AND t.paper = b.paper Set the toggle to :guilabel:`Semiring` so no Boolean shortcut fires, and the provenance is the literal circuit of the cyclic join -- Studio draws it, visibly bushy. Run :guilabel:`Marginal probability` with the default ``exact`` method: rather than trying methods in turn, ProvSQL's :ref:`cost-based chooser ` inspects the circuit and runs the exact method it expects to be cheapest, and Studio names it next to the result -- here *via d-tree*, ``≈ 0.8818`` in milliseconds. Forcing a method shows what the chooser avoided: ``independent`` **errors**, while ``tree-decomposition`` or ``compilation`` agree on ``≈ 0.8818``. Why it is hard: with ``paper`` free, ``reviewer``, ``paper`` and ``topic`` form a cycle with no nesting -- non-hierarchical, not inversion-free, and a single conjunct so nothing cancels. All of Part A is exhausted, and computing the probability of this query is :math:`\#P`-hard in the size of the data :cite:`DBLP:journals/jacm/DalviS12`. The circuit's treewidth is **4** (against **1** for a safe query), and an external compiler (:guilabel:`Compiled d-D circuit` with ``d4``) turns it into a d-DNNF of order a thousand nodes -- and the number ``0.8818``. That compiled circuit is the object the rest of Part B inspects. Reading the CNF back against the data ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Pick :guilabel:`Tseytin CNF`: the panel shows the DIMACS CNF ProvSQL streams to an external compiler, with one ``c input`` comment per variable. Studio annotates each with the source tuple it stands for, so a model or weighted count returned by an outside tool reads back against the reviewing data (the same mapping is a table through :sqlfunc:`tseytin_cnf_mapping`). .. figure:: /_static/casestudy7/cnf-mapping.png :alt: The Tseytin CNF panel: one "c input" comment line per DIMACS variable, each annotated with the source tuple it resolves to, such as bid(p6, r14) and expertise(r14, t3). The Tseytin CNF panel for the hard query: each ``c input`` line is annotated with the source tuple the variable stands for (``bid(p6, r14)``, ``expertise(r14, t3)``…). Comparing compilers and methods ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Pick :guilabel:`Probability benchmark`: it times every probability method on the hard circuit, one row each, with the compiled d-DNNF size beside the run time. Observe the spread: the exact methods that finish (``d-tree``, ``tree-decomposition``, the compilers, the model counters) all agree to full precision, ``d-tree`` -- the chooser's pick above -- being the fastest of them; the samplers ``monte-carlo`` and ``karp-luby`` land near ``0.8818``; ``independent`` shows its error; and methods that do not scale -- ``possible-worlds`` enumeration, the ``panini-obdd`` compiler, the ``weightmc`` counter -- hit the ``statement_timeout``. The compiled sizes span two orders of magnitude, from a few hundred nodes to over a hundred thousand; :sqlfunc:`ddnnf_stats` exposes them as ``jsonb`` for comparing one circuit across compilers. .. figure:: /_static/casestudy7/probability-benchmark.png :alt: The probability-benchmark table on the hard circuit, one row per method sorted by time, with method, args, probability, time, and the compiled d-DNNF node/edge sizes; d-tree, tree-decomposition, the compilers and the model counters that finish return 0.8818, monte-carlo and karp-luby return nearby estimates, independent shows a "not an independent circuit" error, and possible-worlds, weightmc and panini-obdd hit the statement timeout. The probability benchmark on the hard circuit, sorted by time: ``d-tree``, ``tree-decomposition``, the compilers and the model counters agree on ``0.8818``; ``monte-carlo`` and ``karp-luby`` land close; ``independent`` reports the circuit is not independent; ``possible-worlds``, ``weightmc`` and ``panini-obdd`` time out. Which compilers appear depends on what is installed; the Tools panel (the :fa:`tools` button) lists the registry and flags each as available / enabled, read live from ``provsql.tools`` (see :doc:`the external-tool registry `). A shortcut that skips the compiler ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Not every hard-looking query reaches a compiler. *Which papers have at least two bidding experts?* .. code-block:: postgresql SELECT p.id, p.title FROM bid b, expertise e, papers p WHERE b.reviewer = e.reviewer AND b.paper = p.id GROUP BY p.id, p.title HAVING count(*) >= 2 ORDER BY p.id Compute the probability for ``p1``: it comes back at once, and ProvSQL emits a NOTICE that the ``count(*) >= 2`` comparison was *shortcut*. The ``HAVING`` threshold over independent contributors follows a `Poisson-binomial `__ distribution, which :sqlfunc:`probability_evaluate` computes in closed form before any compiler runs, so even ``independent`` answers it. Part C: The Data Is Well-Structured ----------------------------------- Computing the probability of Part B's whole-program coverage is :math:`\#P`-hard over arbitrary data -- yet on *this* data it is tractable. When no query-side route applies, ProvSQL still avoids a compiler if the **data** is well-structured: it compiles a certified circuit along a tree decomposition of the data itself, exactly and in linear time -- over independent data, correlated data, and through recursion. .. _cs7-part-c-joint: The same hard query, now easy ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Set the toggle back to :guilabel:`Boolean` and re-run Part B's hard query: .. code-block:: postgresql SELECT DISTINCT 1 FROM bid b, expertise e, topic_of t WHERE b.reviewer = e.reviewer AND e.topic = t.topic AND t.paper = b.paper Exact probability computation now takes a different route: Studio shows *via bounded-jw*, the same ``≈ 0.8818`` -- and no compiler ran. Over arbitrary data the problem is still :math:`\#P`-hard, but on this data the **joint treewidth** (the data graph together with its correlations) is bounded, so ProvSQL's **joint-width compiler** :cite:`Amarilli2016thesis` recognises the shape and compiles the provenance along a tree decomposition of the *data* into a certified d-D, read in linear time; even ``independent``, which rejected the literal circuit, now succeeds on it. This is the route the dropped-key query of Part A fell through to. Correlated inputs ^^^^^^^^^^^^^^^^^ So far every relation was tuple-independent. The ``assignment`` table lists, per reviewer, the papers they *could* be assigned to, made mutually exclusive by ``repair_key`` on ``reviewer`` (each reviewer ends up on one paper). *Which papers get an assigned reviewer?* .. code-block:: postgresql SELECT p.id, p.title FROM assignment a JOIN papers p ON a.paper = p.id GROUP BY p.id, p.title ORDER BY p.id .. figure:: /_static/casestudy7/schema-keys.png :alt: Schema-panel detail: the assignment table (PROV-BID) with a dotted underline on its reviewer grouping key, above the bid table (PROV-TID) whose reviewer and paper primary-key columns are solid-underlined. The schema panel distinguishes key kinds: ``assignment`` is BID (``repair_key`` on ``reviewer``, dotted underline); the TID tables carry solid-underlined primary keys. Run ``independent`` on ``p1``'s row: it returns the exact ``0.875`` (``0.75`` for ``p2``) although the inputs are now correlated, because within a block it *sums* the probabilities of the mutually exclusive alternatives instead of multiplying them. This kind of block correlation, unlike the cycle of Part B, stays tractable with no compiler at all, because the *query* here is safe; only the *inputs* are correlated. Hard *and* correlated ^^^^^^^^^^^^^^^^^^^^^^^ The joint-width route matters most where the two regimes meet. *Is any paper covered by its assigned expert reviewer?* -- Part B's hard cyclic shape, now over the correlated ``assignment`` table. .. code-block:: postgresql SELECT DISTINCT 1 FROM assignment a, expertise e, topic_of t WHERE a.reviewer = e.reviewer AND e.topic = t.topic AND t.paper = a.paper Try ``independent`` with the toggle on :guilabel:`Semiring` (the literal circuit): it **rejects** it (a reviewer's candidate papers are mutually exclusive, so the lineage is neither independent nor read-once), and Part A's routes do not apply to the cyclic shape. Switch the toggle back to :guilabel:`Boolean` and the joint-width route compiles it anyway: the joint treewidth -- data graph *plus* the ``repair_key`` exclusion blocks -- is bounded, so ProvSQL builds a certified d-D that ``independent`` evaluates exactly, in linear time: ``≈ 0.7359``. In the :ref:`tractability table `, this is the joint-treewidth row: it puts no condition on the query, only on the data together with its correlations, and stays exact and linear in the data. Recursion: reachability and reliability ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. note:: Recursive queries (``WITH RECURSIVE``) require **PostgreSQL ≥ 15**. ProvSQL tracks provenance through ``WITH RECURSIVE`` too: a reachability answer's provenance is the disjunction over the paths that reach it. Two more relations exercise the two regimes: ``extends(citing, cited)`` is an **acyclic** citation graph, ``coreview(a, b)`` a **symmetric** (hence cyclic) collaboration graph. *What does paper* ``p6`` *transitively build on?* Set the toggle back to :guilabel:`Semiring` first. .. nb:scheme: semiring .. code-block:: postgresql WITH RECURSIVE anc(paper) AS ( SELECT 'p6' UNION SELECT e.cited FROM anc a JOIN extends e ON e.citing = a.paper ) SELECT p.id, p.title FROM anc JOIN papers p ON anc.paper = p.id WHERE anc.paper <> 'p6' ORDER BY p.id Click ``p1``'s ``provsql`` cell and, in the eval strip, pick :guilabel:`Formula` with the ``extends_label`` mapping: the lineage is the conjunction along the path, ``ext(p6,p4) ⊗ ext(p4,p1)``, and :guilabel:`Marginal probability` with ``exact`` gives its value, ``0.72``. Because the graph is acyclic, no ancestor is derived through itself, so *every* semiring evaluation works, not just probability. *Who is reviewer* ``r1`` *connected to through co-reviewing?* -- now a cyclic walk: .. nb:scheme: semiring .. code-block:: postgresql WITH RECURSIVE conn(node) AS ( SELECT 'r1' UNION SELECT e.b FROM conn c JOIN coreview e ON e.a = c.node ) SELECT r.id, r.name FROM conn JOIN reviewers r ON conn.node = r.id WHERE conn.node <> 'r1' ORDER BY r.id With the toggle still on :guilabel:`Semiring`, a cycle gives a reviewer infinitely many derivations: ``r1`` reaches ``r5`` through ``r2``, but also through ``r2``, back to ``r1``, ``r2`` again, and so on. ProvSQL does not unroll them; it records the recursion as equations between the reviewers reached. Click ``r5``'s ``provsql`` cell: the root is an **lfp** node, ``r5``'s value in the least solution of the equation system held by the **≡** node, shared by the reviewers of the cycle, whose wires are the unknowns (**x**) and their right-hand sides. :guilabel:`Formula` with the ``coreview_label`` mapping writes the system out, with the same names: ``x₁ where x₁ = (x₄ ⊗ co(r2,r5)) ⊕ (x₂ ⊗ co(r4,r5)), …, x₅ = 𝟙 ⊕ (x₄ ⊗ co(r2,r1)) ⊕ (x₃ ⊗ co(r3,r1))``: ``r5`` is ``x₁``, the unknown its **lfp** node reads, and ``r1``, where the walk starts, is ``x₅``. Each product is in the order of the path, since ``conn`` comes first in the recursive ``FROM`` clause. Each evaluation solves these equations in its own algebra: :guilabel:`Why-provenance` lists the sets of co-reviews the derivations use, and :guilabel:`Marginal probability` with ``exact`` gives ``≈ 0.5496``, *via possible-worlds*: it enumerates the :math:`2^{12}` subsets of the co-review edges. That is fine for twelve edges, not for a real collaboration graph: the probability that ``r1`` stays connected to ``r5`` when each edge is present independently is **two-terminal network reliability**, which is :math:`\#P`-hard to compute in general. Probability does not need the infinitely many derivations, though. A derivation that goes around a cycle uses every co-review of the shorter derivation inside it, so whenever the longer one is possible, so is the shorter: only the minimal paths matter. Algebraically, that is *absorption*, :math:`1 \oplus a = 1`: probability computation is unaffected by it, and so are commutative absorptive semirings such as Boolean or min-cost over nonnegative costs, but not counting or why-provenance. Switch the toggle to :guilabel:`Absorptive` to tell ProvSQL that only such evaluations will be asked of the result. ProvSQL can then do much better than enumerating worlds. It recognises the reachability shape and, by the provenance form of Courcelle's theorem :cite:`DBLP:conf/icalp/AmarilliBS15`, compiles along a tree decomposition of the **collaboration graph itself** into a certified d-D, one per reachable reviewer, linear in the edges when the graph has bounded treewidth (see :ref:`network-reliability-btw`). :guilabel:`Marginal probability` with ``exact`` now gives the same ``≈ 0.5496`` *via reachability*, and even ``independent`` evaluates it. That is the case study in miniature: Part B's hardness lived in the *query* and needed a compiler; here -- as throughout Part C -- it is dissolved by the structure of the *data*, with no external tool. The price is the absorption assumption itself: each reviewer's root is now an ``assumed`` gate recording it, and the evaluations it does not justify refuse the circuit rather than return a wrong value: Studio no longer offers :guilabel:`Why-provenance`, for instance. The same walk gives *degrees of separation*: count one hop per co-review and take the cheapest path, in the tropical (min-plus) semiring. Its mapping gives every co-review the cost ``1``: .. code-block:: postgresql DROP TABLE IF EXISTS coreview_hops; SELECT create_provenance_mapping('coreview_hops', 'coreview', '1::float8'); Run the co-review query again, the toggle still on :guilabel:`Absorptive`: .. nb:scheme: absorptive .. code-block:: postgresql WITH RECURSIVE conn(node) AS ( SELECT 'r1' UNION SELECT e.b FROM conn c JOIN coreview e ON e.a = c.node ) SELECT r.id, r.name FROM conn JOIN reviewers r ON conn.node = r.id WHERE conn.node <> 'r1' ORDER BY r.id Click ``r5``'s ``provsql`` cell and, in the eval strip, pick :guilabel:`Tropical (min-plus, nonnegative)` with the ``coreview_hops`` mapping: ``2``, ``r5`` being two co-reviews away from ``r1`` (through ``r2``), as ``r4`` is (through ``r3``), while ``r2`` and ``r3`` are one away. This variant checks that the costs are nonnegative, so that a cycle can only add to a path's cost: the semiring is then absorptive, and accepts these circuits as probability does. The plain :guilabel:`Tropical (min-plus)` is not offered: it is not absorptive, so the assumption under which these circuits were built no longer holds for it. Under :guilabel:`Semiring`, it evaluates the equations without that assumption, and gives :math:`-\infty` if a cycle has a negative total cost. .. seealso:: - :doc:`The knowledge-compilation chapter ` for the full pipeline and every function used here. - :doc:`The chapter on probabilities ` for the probability methods and the :ref:`tractability table ` that organises this case study. - The *Probabilistic Databases* synthesis lecture :cite:`DBLP:series/synthesis/2011Suciu` for the theory of safe queries and the dichotomy.