BoolExpr.h File Reference

Boolean-expression (lineage formula) semiring. More...

#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include "Semiring.h"
#include "../BooleanCircuit.h"

Include dependency graph for BoolExpr.h:

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

Go to the source code of this file.

Classes
class	semiring::BoolExpr
	Provenance-as-Boolean-circuit semiring. More...

Namespaces
namespace	semiring

Detailed Description

Boolean-expression (lineage formula) semiring.

The BoolExpr semiring represents provenance as a Boolean circuit rather than a scalar value. Each semiring value is a gate_t identifier inside a shared BooleanCircuit. The semiring operations create new gates in that circuit:

• zero() → a fresh OR gate with no children (always false)
• one() → a fresh AND gate with no children (always true)
• plus() → an OR gate whose children are the operands
• times() → an AND gate whose children are the operands
• monus() → an AND gate combining \(x\) with a NOT of \(y\)
• delta() → identity

The result of evaluating a circuit over this semiring is the root gate of a new Boolean circuit that encodes the provenance formula. This circuit can then be compiled to a d-DNNF for probability computation.

The semiring is absorptive: duplicate children of OR/AND gates are deduplicated during gate construction.

Definition in file BoolExpr.h.