依赖图

在对SDD的求值过程中，如果结点N的属性依赖于其他结点的属性，那么必须要先计算出依赖的这些属性，才能计算N的属性。

$$N \cdot a=\ldots M_{1} \cdot a_{1} \ldots M_{2} \cdot a_{2} \ldots$$

所以我们使用依赖图来表示计算顺序。这些值的计算顺序形成了一个偏序关系，如果依赖图中出现了环，表示属性值无法计算。

依赖图

描述了某棵特定的分析树上各个属性之间的信息流（计算顺序），从实例a1到实例a2到有向边表示计算a2时需要a1的值。对于分析树结点N，与N关联的每个属性a都对应依赖图的一个结点N.a。

属性值的计算顺序：各个属性值需要按照依赖图的拓扑顺序计算，如果依赖图中存在环，则无法计算。给定一个SDD，很难判定是否存在一个分析树，其对应的依赖图中是否有环。但是特定类型的SDD一定不包含环，且有固定的计算顺序。如S属性的SDD、L属性的SDD。