The gate_mulinput Gate

ProvSQL represents each BID block in the persistent circuit by a group of gate_mulinput gates that share a common child, an input gate acting as the block key. Each mulinput gate corresponds to one alternative of the block and carries its own probability (set with set_prob). mulinput gates are not first-class leaves of the provenance DAG: semiring evaluators do not know how to interpret them and will refuse any circuit that contains one, and the probability pipeline handles them only after rewriting the blocks into standard Boolean gates -- as described below.

The canonical way to create such gates from SQL is repair_key, which takes a table with duplicate key values, allocates one fresh input gate per key group, and turns each member of the group into a mulinput whose child is that block key. When no probabilities are attached, repair_key defaults them to a uniform distribution over the block members.

Rewriting Blocks into Independent Booleans

Most probability-evaluation algorithms require a purely Boolean circuit: AND, OR, NOT, and independent Bernoulli leaves. A BID block is not directly such a structure -- its elements are mutually exclusive, not independent. BooleanCircuit::rewriteMultivaluedGates (in BooleanCircuit.cpp) reduces every block to an equivalent Boolean subcircuit by introducing O(logn) fresh independent Bernoulli variables per block of size n whose joint distribution reproduces the original discrete weights.

The construction is divide-and-conquer. Given a block with alternatives carrying cumulative probabilities P₀ ≤ P₁ ≤ ⋯ ≤ P_n − 1, the recursive helper BooleanCircuit::rewriteMultivaluedGatesRec splits the range [start, end] at the midpoint mid, creates one fresh input gate g with probability

-- the conditional probability of landing in the left half -- and recurses twice: the left half gets g pushed onto its prefix, the right half gets NOT g. At a leaf (start = end), the mulinput gate is rewritten into the AND of the accumulated prefix, so its truth value becomes the conjunction of the fresh-variable decisions that lead to it. If the block's probabilities do not sum to 1, the outer call wraps the whole construction in one more fresh input of probability P_n − 1 to carry the "none of them" residual.

After rewriting, the block's mulinput gates have been turned into ordinary AND gates over fresh independent Boolean inputs, and the circuit is ready for any TID-based probability method. The dispatcher in probability_evaluate_internal calls BooleanCircuit::rewriteMultivaluedGates lazily: the "independent" method handles mulinput gates natively and runs on the raw circuit; every other method falls through to the rewrite first. This is the pivot point referenced in adding-new-probability-method below.

Entry Point

shapley / banzhaf (and their set-returning variants shapley_all_vars / banzhaf_all_vars) are thin wrappers that unpack their arguments and call shapley_internal in shapley.cpp. That helper performs the following sequence:

1. Build a BooleanCircuit from the persistent store via getBooleanCircuit.
2. Build a dDNNF by calling BooleanCircuit::makeDD. This is the same d-DNNF construction used for ordinary probability evaluation, and obeys the same method / args conventions.
3. dDNNF::makeSmooth -- ensure that every OR gate's children mention the same variable set. The paper's algorithm assumes a smooth d-DNNF.
4. For Shapley (but not Banzhaf): dDNNF::makeGatesBinary on AND -- binarise AND gates so each has at most two children. Together, the previous two steps turn the d-DNNF into a tight d-D circuit in the paper's sense.
5. Call dDNNF::shapley or dDNNF::banzhaf on the target variable's gate.

The Shapley Recurrence

The paper's algorithm conditions the circuit on the target variable being fixed to true (call the result C₁) and to false (call it C₀), computes a pair of per-gate arrays on each conditioned circuit, and combines them into the final score. ProvSQL's dDNNF::shapley mirrors that structure:

double dDNNF::shapley(gate_t var) const {
  auto cond_pos = condition(var, true);   // C_1
  auto cond_neg = condition(var, false);  // C_0

  auto alpha_pos = cond_pos.shapley_alpha();
  auto alpha_neg = cond_neg.shapley_alpha();

  double result = 0.;
  for (size_t k = ...; k < alpha_pos.size(); ++k)
    for (size_t l = 0; l <= k; ++l) {
      double pos = alpha_pos[k][l];
      double neg = alpha_neg[k][l];
      result += (pos - neg) / comb(k, l) / (k + 1);
    }
  result *= getProb(var);
  return result;
}

dDNNF::condition returns a copy of the circuit in which the target input gate has been replaced by an AND / OR-with-no-children acting as the constant true / false respectively. The private helper dDNNF::shapley_alpha() then performs a single bottom-up pass computing a two-dimensional array β^g_k, ℓ (called result[g] in the code) at every gate g, where k is the number of variables under g in the current cofactor and ℓ is the number of them that are positively assigned. The recurrences follow the IN / NOT / OR / AND cases of Algorithm 1 of the paper:

• At a leaf, the array encodes the Bernoulli distribution of that single variable.
• At an OR gate, the arrays of the children are summed coordinatewise (valid because the d-DNNF is smooth, so all children have the same variable set).
• At a binary AND gate, the arrays are convolved via a double sum over (k₁, ℓ₁) pairs -- the decomposability of AND makes this the Cauchy product of two independent distributions. This convolution is the reason AND gates have to be binarised before the algorithm runs.
• A standalone bottom-up pass (dDNNF::shapley_delta()) precomputes the δ^g_k polynomials, which the algorithm uses at NOT gates to turn negation into a coefficient flip.

The final score is px⋅∑k, ℓcShapley(k + 1, ℓ)⋅(βgoutk, ℓ − γgoutk, ℓ), where βgout comes from C1 and γgout from C0, and cShapley(k + 1, ℓ) = (kℓ) − 1 ⁄ (k + 1) is the Shapley coefficient -- i.e.exactly the formula implemented above. The overall complexity is O(|C|⋅|V|5) arithmetic operations, dominated by the double-sum convolution at AND gates over the |V|2-sized arrays.

The if (isProbabilistic()) guards inside shapley_alpha and shapley_delta short-circuit the polynomials to a single top-level coefficient when all input probabilities are 1, so that the same code path computes classical (deterministic) Shapley values without paying the expected-score overhead.

Banzhaf

The expected Banzhaf value admits a much simpler formula DBLP:journals/pacmmod/KarmakarMSB24:

where ENV(φ) = ∑_Z ⊆ VΠ_V(Z)∑_E ⊆ Zφ(E) can be computed in a single linear pass over a smooth d-D circuit without binarising AND gates. dDNNF::banzhaf runs banzhaf_internal() on the two conditioned circuits C₁ and C₀ and returns the difference times p_x; the overall complexity is O(|C|⋅|V|), one factor of |V| less than Shapley. This is why shapley_internal skips the dDNNF::makeGatesBinary call in the Banzhaf branch.