Asynchronous Chain Recursions

Jiawei Han, Wenyu Lu

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)185-195
Number of pages11
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number2
StatePublished - Jun 1989
Externally publishedYes


  • Compilation techniques
  • deductive database systems
  • query optimization
  • recursions
  • recursive query processing
  • transitive closures

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Asynchronous Chain Recursions'. Together they form a unique fingerprint.

Cite this