SDD的求值顺序

文章目录

• 依赖图
• 属性值的计算顺序

依赖图

• 依赖图是一个描述了分析树种节点属性间依赖关系的有向图
• 分析树中每个标号为X的节点的每个属性a都对应着依赖图中的一个结点
• 如果属相X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

例如：

属性值的计算顺序

• 可行的求值顺序是满足下列条件的结点序列$N_1,N_2,...,N_k$：如果依赖图中有一条从结点$N_i$到$N_j$的边$(N_i \rightarrow{N_j})$，那么$i（即在结点序列中，$N_i$排在$N_j$前面）
  • 这样的排序讲一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序 。