具有多值约束的线性递归查询的有效计算

本文给出三个算法,分别用于把给定的右线性、左线性或左-右线性递归程序改写为一组更有效的规则.与Ullman等人的变换算法不同,本文的算法允许查询的初始约束可以是含任意多个约束元组的集合,而不必是单值的;这样,本文的算法不仅可以用于查询的求值,而且也可以用于子目标的处理.变换算法的正确性和变换后规则的有效性也在本文简略讨论.

EFFICIENT EVALUATION OF LINEAR RECURSIONS WITH MULTIVALUE BINDING SETS

This paper presents three algorithms transforming given right-linear, left-linear and left-right-linear recursions into more efficient rules respectively. The difference between the algorithms presented here and those of Ullman et al. is that the iniltial binding sets of queries need not be singleton. Therefore, these algorithms can be used not only for query evaluation, but also for subgoal processing. The correctness of the transformation and the efficiency of the transformed rules are also discussed briefly.