Abstract
We identify a new representation of propositional knowledge bases, the Sentential Decision Diagram (SDD), which is interesting for a number of reasons. First, it is canonical in the presence of additional properties that resemble reduction rules of OBDDs. Second, SDDs can be combined using any Boolean operator in polytime. Third, CNFs with n variables and treewidth w have canonical SDDs of size O(n2w), which is tighter than the bound on OBDDs based on pathwidth. Finally, every OBDD is an SDD. Hence, working with the latter does not preclude the former.
Introduction
In the field of knowledge compilation, the goal is to translate propositional logic into tractable data structures to enable efficient querying. This process involves a trade-off between succinctness (the size of the data structure) and tractability (the efficiency of operations performed on it).
For decades, Ordered Binary Decision Diagrams (OBDDs) have served as the industry standard due to their canonicity—a unique representation for any given Boolean function and variable order—and their support for polynomial-time Boolean operations via the Apply function. However, OBDDs are limited by the pathwidth of the problem, often leading to exponential size explosions. While more recent representations like d-DNNFs offer better succinctness (bounded by treewidth), they lack the canonicity and efficient Boolean combinations that make OBDDs so practical. The Sentential Decision Diagram (SDD) is introduced to bridge this gap.
The Sentential Decision Diagram (SDD)
The SDD is built upon two foundational concepts that generalize the structure of OBDDs:
- Structured Decomposability via Vtrees: Unlike OBDDs, which rely on a linear variable ordering, SDDs utilize a vtree—a full binary tree where leaves represent variables. The vtree defines the recursive decomposition of the Boolean function.
- Strongly Deterministic Decompositions (X-partitions): While OBDDs use Shannon decomposition (splitting on a single variable), SDDs generalize this by splitting on mutually exclusive and exhaustive sentences (functions over a set of variables $\mathbf{X}$).
To ensure canonicity, SDDs employ specific compression and trimming rules, ensuring no duplicate sub-functions exist. The representation supports an Apply algorithm that can conjoin, disjoin, or negate SDDs in polynomial time $O(|\alpha||\beta|)$, mirroring the efficiency of OBDD operations.
Key Properties and the OBDD Connection
A significant theoretical contribution of this work is the proof that OBDDs are a special case of SDDs. Specifically, if an SDD is restricted to a "right-linear" vtree (where every left child is a leaf), it collapses into a reduced OBDD. This means that adopting SDDs provides a more general framework without losing the benefits of OBDDs.
Furthermore, SDDs offer superior theoretical size bounds. While OBDD size is bounded by $O(n2^{pw})$ (where $pw$ is pathwidth), SDD size is bounded by $O(n2^w)$ (where $w$ is treewidth). Since pathwidth is $O(w \log n)$, SDDs provide a strictly tighter, exponentially better theoretical guarantee for many problems.
Empirical Results
The SDD representation was evaluated using the ISCAS89 benchmark suite, a standard set of digital circuit representations. Preliminary results indicate that SDDs constructed using a "Minfill vtree" heuristic are consistently smaller than OBDDs constructed with state-of-the-art variable ordering techniques like "MINCE."
For example, in the circuit s838.1, the OBDD size using the MINCE order was 57,182 nodes. In contrast, the SDD size using a Minfill vtree was only 14,062 nodes. Even when the SDD was constrained to use the same MINCE order (structured as a balanced vtree), the size remained lower at 19,033 nodes, demonstrating the inherent efficiency of the SDD structure.
Conclusion
SDDs represent a new frontier in knowledge compilation, combining the canonicity and tractability of OBDDs with the succinctness of treewidth-based representations. While the current results are promising, future research will focus on developing sophisticated static and dynamic heuristics for finding optimal vtrees, similar to the extensive research history of OBDD variable reordering.
Summary updated