Asynchronous Chain Recursions

An asynchronous chain recursion is a recursion whose compiled formula consists of single chain or asynchronous chains. We study the compilation and efficient processing of asynchronous chain recursions and show that many complex function-free recursions, which may contain single or multiple linear recursive rules, nonlinear recursive rules, mutually recursive rules, and different-level recursions, can be compiled to asynchronous chain recursions. Our study on the compilation methods, the simplification of compiled formulas, and the query processing techniques shows that asynchronous chain recursions can be compiled to relatively simple compiled formulas and processed efficiently using transitive closure query processing methods.