Towards an Algebraic Theory of Recursion
Yannis Ioannidis
Eugene Wong
Date published: 
Published In: 
Journal of the ACM (JACM), Vol. 38, No. 2, April 1991, pp. 329-381
Journal Article

An algebraic framework for the study of recursion has been developed. For immediate linear recursion, a Horn clause is represented by a relational algebra operator. It is shown that the set of all such operators forms a closed semiring. In this formalism. query answering corresponds to solving a linear equation. For the first time, the query answer is able to be expressed in an expicit algebraic form within an algebraic structure. The manipulative power thus afforded has several implications on the implementation of recursive query processing algorltbms. Several possible decompositions of a given operator are presented that improve the performance of the algorithms, as well as several transformations that give the ability to take into account any selections or projections that are present in a given query. In addition, it is shown that mutual linear recursion can also be studied within a closed semiring, by using relatlon vectors and operator matrices. Regarding nonlinear recursion, it is first shown that Horn clauses always give rise to multilinear recursion, which can always be reduced to bilinear recursion. Bilinear recursion is then shown to form a nonassociatlve closed semiring. Finally, several sufficient and necessary-and-sufficient conditions for bilinear recursion to be equivalent to a linear one of a specific form are given. One of the sufficient conditions is derived by embedding bilinear recursion in an algebra.

Related files: 

MaDgIK 2009-2016