Decision Structures

Core Concepts

Decision Tables

Decision tables organize rules in a tabular format where conditions (inputs) and actions (outputs) are represented as columns. This structure has two significant practical properties.

First, it is accessible to non-technical stakeholders. Business analysts can author and review logic directly without translating through code. This makes the rules engine a collaboration surface, not just an execution surface.

Second, the tabular format enables tooling to mechanically check for rule completeness and consistency — detecting gaps (inputs with no matching rule) or conflicts (inputs matching multiple contradictory rules) before execution.

Decision tables are the right fit when:

• Rules are authored or reviewed by non-developers.
• You need auditability and traceability of individual rules.
• The condition space is well-bounded and enumerable.

Decision Trees

Decision trees represent rules as hierarchical branching structures where each internal node represents a condition test and each branch represents a possible outcome of that test. The structure is visually intuitive — you can walk through a decision by following a path from root to leaf.

The structural problem with trees is rooted in their geometry. Tree depth grows linearly with the number of variables, but the number of branches grows exponentially with the number of states. A function over n binary variables has up to 2ⁿ terminal paths, all of which the tree must represent, including duplicates.

Decision trees are the right fit when:

• Rule depth is shallow and variable count is small.
• Visual interpretability of individual paths matters more than memory efficiency.
• You are not evaluating at high frequency or scale.

Binary Decision Diagrams

Binary Decision Diagrams (BDDs) are the structure that addresses the redundancy problem that trees cannot solve.

From truth tables to graphs. A BDD is constructed through recursive application of Shannon's expansion theorem, also called cofactoring. Shannon's theorem says that any Boolean function f over variable x can be decomposed as:

f(x, ...) = (x AND f|x=1) OR (NOT x AND f|x=0)

Applying this recursively in a chosen variable order produces a binary tree. The BDD then applies two reduction rules to compress it into a directed acyclic graph (DAG):

1. Merge isomorphic sub-graphs — if two sub-trees are structurally identical, replace them with a single shared node.
2. Eliminate redundant nodes — if a node's two branches both point to the same successor, remove the node and redirect its predecessor.

The result is a Reduced Ordered Binary Decision Diagram (ROBDD).

Evaluation as graph traversal. Evaluating a Boolean function encoded in a BDD reduces to traversing a DAG from root to a terminal node (0 or 1). At each internal node, you test one variable and follow the corresponding branch. The time complexity is O(k) where k is the number of variables — and critically, this is independent of the number of rules encoded in the BDD.

Evaluation time is constant relative to rule count growth. Adding more rules to a BDD does not slow down per-evaluation time.

The canonical property. ROBDDs provide a unique canonical representation for any Boolean function given a fixed variable ordering. Two Boolean functions are equivalent if and only if their ROBDDs are identical. This reduces equivalence testing to a graph comparison — an operation that is structurally simple and mechanically reliable.

This is the property that enables BDD-based verification: equivalence checking, satisfiability testing, and property verification all become tractable graph operations rather than exhaustive enumeration problems.

Variable Ordering

The most operationally important fact about BDDs is that variable ordering dominates BDD size.

Different variable orderings for the same Boolean function can produce BDD sizes ranging from linear to exponential. This is not a small difference in practice — a poor ordering can make a BDD that would otherwise fit in memory too large to construct at all.

Finding the optimal variable ordering is an NP-complete problem. This is a fundamental computational complexity result, not an engineering limitation. For any realistic rule set, exhaustive search for the optimal ordering is intractable.

The Sifting algorithm, introduced by Rudell in 1993, is the standard practical response. It works by applying adjacent variable interchanges — moving each variable through the ordering and measuring the effect on diagram size, then keeping the best position found. Sifting is considered one of the most effective heuristics for variable ordering optimization and often produces substantially more compact diagrams than static orderings.

Zero-Suppressed Decision Diagrams

ZDDs (Zero-suppressed Decision Diagrams) are a variant of BDDs optimized for sparse Boolean functions — functions that evaluate to zero almost everywhere.

The difference is in the suppression rule. BDDs suppress nodes where both branches are identical. ZDDs suppress nodes where the 1-branch leads to the zero terminal. For combinatorial sets and sparse functions, this produces significantly better compression than a standard ROBDD.

ZDDs appear when you are encoding set membership, feature combinations, or permission sets where most combinations are absent. They are a specialized tool, not a general replacement for BDDs.

Dependency Graphs and Topological Sort

When rules depend on each other — the output of one rule feeds as input to another — the evaluation problem is structurally a DAG traversal problem at a different level.

Topological sorting of a rule dependency DAG establishes an ordering where each rule is evaluated only after all its dependencies have been satisfied. This enables time-forward processing where rule evaluation completes in linear time with respect to the number of dependencies. Algorithms like IterTS have demonstrated order-of-magnitude improvements over naive approaches for this pattern.

---

Compare & Contrast

Property	Decision Table	Decision Tree	BDD
Structure	Flat rows, condition/action columns	Hierarchical branching tree	Directed acyclic graph
Redundancy	None (each row is independent)	High (no sub-expression sharing)	Low (isomorphic sub-graphs merged)
Space complexity	Linear in rule count	Exponential in variable count	Variable; depends on ordering and function
Evaluation time	Linear in row count	Linear in tree depth (bounded)	O(k) in variable count, independent of rule count
Canonical form	No	No	Yes (for fixed variable ordering)
Equivalence checking	Expensive (row-by-row)	Expensive (path-by-path)	O(1) graph comparison
Non-technical authoring	Yes	Moderately	No
Sparse function efficiency	Moderate	Poor	Good with ZDD variant
Construction cost	Low	Low	High (amortized across evaluations)

---

Worked Example

Scenario: An authorization system with three binary conditions:

• isEmployee (E)
• isManager (M)
• hasActiveProject (P)

The rule: grant access if the user is a manager, OR if the user is an employee with an active project.

ACCESS = M OR (E AND P)

As a decision table:

isManager	isEmployee	hasActiveProject	ACCESS
true	any	any	true
false	true	true	true
false	true	false	false
false	false	any	false

Clean and readable. Tooling can verify completeness.

As a decision tree:

[M?]
 ├─ yes → GRANT
 └─ no → [E?]
         ├─ yes → [P?]
         │        ├─ yes → GRANT
         │        └─ no  → DENY
         └─ no  → DENY

For this small example the tree is tractable. Now imagine expanding to 10 binary conditions — 2¹⁰ = 1,024 terminal paths, many of which encode the same outcome.

As a BDD (variable order: M, E, P):

Fig 1

The terminal 0 and 1 nodes are shared. Every path that grants access converges on the same 1 terminal; every denial converges on the same 0 terminal. No sub-expression is duplicated.

Evaluating {M=false, E=true, P=true}:

1. At node M: take the 0-branch (dashed).
2. At node E: value is true, take the 1-branch (solid).
3. At node P: value is true, take the 1-branch (solid).
4. Arrive at terminal 1 — access granted.

Three comparisons. The same traversal cost applies whether this BDD encodes 3 rules or 300.

---

Boundary Conditions

BDDs are not always smaller than trees. BDD space complexity can be exponential in the number of variables for certain Boolean functions. The reduction only works when isomorphic sub-graphs exist to merge. For functions with no shared structure, a BDD degenerates toward a tree.

Construction is expensive and must be amortized. BDD construction involves applying reduction rules over intermediate graphs that may be substantially larger than the final diagram. This upfront cost only pays off if the BDD will be evaluated many times. For low-frequency evaluation or rapidly changing rule sets, simpler structures will outperform.

Variable ordering is critical and hard. Finding the optimal ordering is NP-complete. The Sifting algorithm is the practical state of the art, but it is still a heuristic. Poor ordering choices are not recoverable without reconstruction — and poor orderings can produce BDDs that are orders of magnitude larger than the optimally ordered equivalent.

Canonicity is ordering-relative. The canonical property holds only for a fixed variable ordering. Two BDDs for the same function built with different orderings will not be identical even though they represent the same function. This matters when comparing BDDs across systems that may have used different ordering strategies.

ZDDs are a targeted tool, not a general upgrade. ZDDs outperform BDDs only for sparse functions — those evaluating to zero almost everywhere. For dense Boolean functions, ZDDs offer no advantage and may perform worse.

Decision tables do not scale to high-frequency evaluation. Matching an input against a decision table requires scanning rows. For large rule sets evaluated at high throughput, this linear-in-rule-count cost is a structural bottleneck that BDDs avoid.