| 摘要: |
| 本文给出拓广的左线性递归变换算法并证明其正确性．拓广的左线性递归中可以包含一个或多个ＩＤＢ谓词，它是左线性递归的一般化．和左线性递归计算算法一样，本文提供的算法遵循魔集的模式：首先改写规则，然后用半扑质的自底向上算法计算新规则．算法的有效性也在本文作简略讨论． |
| 关键词: 演绎数据库 查询处理 线性递归 左线性递归 |
| DOI： |
| 分类号: |
| 基金项目:河南省优秀中青年教师奖励基金 |
|
| TRANSFORMATION FOR GENERALIZED LEFT-LINEAR RECURSIONS: ALGORITHM AND ITS CORRECTNESS |
|
Fan Ming
|
| Abstract: |
| This paper presents an algorithm which transform a generalized left-linear recursion into more efficient rules,and shows the correctness of the given algorithm. A generalized left-linear recursion contains one or more IDB predicates and its definition is essentially generalized from that of left-linear recursions. As the algorithm for the evaluation of left - linear recursions, the algorithm we present here follows the magic-sets paradigm of a rewriting phase followed by semi -naive bottom-up evaluation. The efficinecy of the transformed rules is also discussed in this paper. |
| Key words: Deductive database query processing linear recursion left - linear recursion |
