ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
ProbCache.h File Reference

Cache of compiled d-DNNFs, and folding of independent parts. More...

#include <cstdint>
#include <functional>
#include <list>
#include <string>
#include <unordered_map>
#include <vector>
#include "CircuitCanonicalForm.h"
#include "dDNNF.h"
Include dependency graph for ProbCache.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  provsql::ProbCacheStats
 Counters of the cache since it was last emptied. More...
class  provsql::ProbCache
 The cache of compiled d-DNNFs of one backend. More...
struct  provsql::ProbCache::Entry
 A compiled d-DNNF and how its inputs match the leaves of its form. More...
struct  provsql::ProbCacheReport
 What a call to probCachedProbability actually did, so the caller can report it instead of the method it was asked for. More...
struct  provsql::ProbCacheOptions
 What probCachedProbability may do, and what it reports back. More...
struct  provsql::ProbFoldEval
 How probFoldedProbability evaluates what it cannot fold. More...

Namespaces

namespace  provsql

Typedefs

using provsql::ProbCacheCompileFn
 Compiles the circuit below a gate into a d-DNNF.

Functions

bool provsql::probCacheEligible (const BooleanCircuit &c, gate_t root)
 Whether the circuit below root is one the cache and the fold handle: AND, OR and NOT gates over inputs that carry a UUID.
double provsql::probFoldedProbability (const BooleanCircuit &c, gate_t root, const ProbFoldEval &eval)
 Probability of the circuit below root, folding the independent groups of AND and OR gates from the root down and leaving the rest to eval.
double provsql::probCachedProbability (const BooleanCircuit &c, gate_t root, const ProbCacheCompileFn &compile, bool *ran_compiler=nullptr, const ProbCacheOptions &options=ProbCacheOptions())
 Probability of the circuit below root through the fold and the cache.

Detailed Description

Cache of compiled d-DNNFs, and folding of independent parts.

Two ways of not compiling the d-DNNF of a whole circuit, used by the tree-decomposition and compilation probability methods:

  • the cache keeps, for the session, the d-DNNFs compiled so far, under the canonical form of the circuit they were compiled for (CircuitCanonicalForm.h). A circuit is looked up island by island, then for its residual, so that a shape repeated inside a circuit or across circuits is compiled once; a hit evaluates the stored d-DNNF with the probabilities of the circuit at hand;
  • the fold groups the children of an AND or OR root by the inputs they share. Groups are independent, so their probabilities are multiplied (for an OR, through the complements); a group of one child is folded in turn and a larger one is handed to the method.

Whether each applies is decided by the caller, from provsql.prob_cache and provsql.idp_fold.

Definition in file ProbCache.h.