Efficient Evaluation of One-directional Cycle-recursive Formulas

概要

論文の詳細を見る
Normalization is an efficient method of optimization and evaluation for linear recursions. It facilitates the generation of efficient execution plans, since it can directly select the most efficient evaluation algorithm from d set of candidates according to the structural characteristics of recursions. Therefore, it is useful to develop new specialized algorithms for some frequently appearing classes of linear recursions in the normalization framework. This paper focuses on a class of linear recursions, which in terms of the graph model^<11)> are called one-directional cycle recursions. We show that one-directional cycle recursion is a very frequently appearing pattern in the normalization of linear recursions. We also prove that this kind of recursion can be normalized to a specially formed formula in which all chains have same chain predicate. Based on this interesting property, an efficient evaluation algorithm is proposed. It is efficient because it evaluates only one binary transitive closure and does not need to trace initial driver information in evaluation of the transitive closure, as it is necessary in the multi-way counting method^<7)>. Some simulation results also how the efficiency of our method.
一般社団法人情報処理学会の論文
1996-12-15