Sentential decision diagram

In artificial intelligence, a sentential decision diagram is a type of knowledge representation used in knowledge compilation to represent Boolean functions. SDDs can be viewed as a generalization of the influential ordered binary decision diagram representation, by allowing decisions on multiple variables at once. Like OBDDs, SDDs allow for tractable Boolean operations, while being exponentially more succinct. For this reason, they have become an important representation in knowledge compilation.

Properties

SDDs are defined with respect to a generalization of variable ordering known as a variable tree.
Provided that they satisfy additional properties known as compression and trimming, SDDs are a canonical representation of Boolean functions; that is, they are unique given a vtree.
Like OBDDs, they allow for operations such as conjunction, disjunction and negation to be computed directly on the representation in polynomial time, while being potentially more compact. They also allow for polynomial-time model counting.
SDDs are known to be exponentially more succinct than OBDDs.

Applications

SDDs are used as a compilation target for probabilistic logic programs by the ProbLog 2 system since they support tractable model counting as well as tractable negation, conjunction and disjunction while being more succinct than BDDs. SDDs have also been extended to model probability distributions, in which context they are known as probabilistic sentential decision diagrams.