DTree.h File Reference

Anytime interval-bounds probability for monotone DNFs (d-trees). More...

#include <set>
#include <vector>
#include "Circuit.h"

Include dependency graph for DTree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	provsql::DTreeInterval
	A certified probability interval lower <= Pr <= upper. More...

Namespaces
namespace	provsql

Functions
DTreeInterval	provsql::dtreeBounds (const BooleanCircuit &c, std::vector< std::set< gate_t > > clauses, double max_width, unsigned long budget=0, unsigned long *steps_out=nullptr)
	Certified probability interval of a monotone DNF, refined to a target width (Olteanu-Huang-Koch d-tree).
DTreeInterval	provsql::dtreeBoundsCircuit (const BooleanCircuit &c, gate_t root, double max_width, unsigned long budget=0, unsigned long *steps_out=nullptr)
	Certified probability interval of an arbitrary Boolean circuit, refined to a target width (the d-tree generalised off monotone DNF).

Detailed Description

Anytime interval-bounds probability for monotone DNFs (d-trees).

Implements the recursive half of Olteanu, Huang & Koch, "Approximate Confidence Computation in Probabilistic Databases" (ICDE 2010): the cheap leaf bound BooleanCircuit::dnfBounds is refined by two decompositions – independent-or (connected components of the clause graph) and Shannon expansion (on the most frequent variable) – until the certified interval is narrow enough, or exactly (interval width 0).

The recursion operates purely on the clause-support sets of a monotone DNF: a clause is the conjunction of its positive input leaves, so the DNF is the list of those leaf sets, and every decomposition (component split, Shannon cofactor) maps a DNF to DNFs of the same representation.

Definition in file DTree.h.