Efficient Evaluation of One -directional Cycle- recursive Formulas

• Item type: Journal(1)
• 公開日: 1996-12-15
• タイトル: Efficient Evaluation of One -directional Cycle- recursive Formulas
• タイトル / 言語: en
• タイトル: Efficient Evaluation of One -directional Cycle- recursive Formulas
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: データベース
• 著者所属: Department of Intelligence and Computer Science Nagoya Institute of Technology
• 著者所属: Department of Intelligence and Computer Science Nagoya Institute of Technology
• 著者所属: Department of Intelligence and Computer Science Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Intelligence and Computer Science, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Intelligence and Computer Science, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Intelligence and Computer Science, Nagoya Institute of Technology
• 著者名: Xiaoyong, Du; Zhibin, Liu; Naohiro, Ishii
• 著者名(英): Xiaoyong, Du; Zhibin, Liu; Naohiro, Ishii
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 37, 号 12, p. 2284-2294, 発行日 1996-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764