摘要
本文给出拓广的右线性递归变换算法并证明其正确性.拓广的右线性递归中可以包含一个或多个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.
出处
《计算机学报》
EI
CSCD
北大核心
1992年第12期906-912,共7页
Chinese Journal of Computers
基金
河南省自然科学基金
关键词
变换算法
右线性递归
拓广
数据库
Deductive database, query processing, linear recursion, right-linear recursion.
