拓广的右线性递归变换算法及其正确性  

TRANSFORMATION OF GENERALIZED RIGHT-LINEAR RECURSIONS: ALGORITHM AND ITS CORRECTNESS

作　　者：范明[1] 

机构地区：[1]郑州大学计算机科学系,郑州450052

出　　处：《计算机学报》1992年第12期906-912,共7页Chinese Journal of Computers

基　　金：河南省自然科学基金

摘　　要：本文给出拓广的右线性递归变换算法并证明其正确性.拓广的右线性递归中可以包含一个或多个IDB谓词,它是右线性递归的一般化.和右线性递归计算算法一样,本文提供的算法遵循魔集的模式:首先改写规则,然后用半扑质的自底向上算法计算新规则.算法的有效性通过减少递归谓词的元数实现.This paper presents an algoorithm transforming a generalized right-linear recursion into more efficient rules, and shows its correctness. A generalized right-linear recursion contains one or more IDB predicates and is essentially the generalization of right-linear recursion. The algorithm follows the magic-set paradigm of a rewriting phase followed by semi-naive bottom-up evaluation, and achieves its efficiency by reducing the arity of the recursive predicates in the transformed rules.

关 键 词：变换算法 右线性递归 拓广 数据库 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]