Efficient Evaluation of Multiple Linear Recursions

Jiawei Han, Ling Liu

Research output: Contribution to journalArticlepeer-review


A multiple linear (ML) recursion is a recursion which consists of multiple linear recursive rules and one or more nonrecursive rules. ML recursions can be classified into two classes: side-coherent and non-side-coherent. This paper studies the efficient evaluation of side-coherent ML recursions, which can be further classified into three types: (I) multiple one-sided, (II) multiple balanced k-sided, and (III) multiple mixed k-sided. New techniques are developed by integrating the existing single-linear recursive query evaluation methods with the idea of side-relation unioned processing, which leads to a set of efficient query evaluation algorithms such as a side-relation unioned transitive closure algorithm for the processing of Type I ML recursions, and a generalized side-relation unioned magic sets method for the processing of Types II and III ML recursions. Therefore the evaluation of ML recursions can be mapped to the framework of the evaluation of single linear recursions. Previously developed techniques for the evaluation of single linear recursions, such as the selection of processing strategies for queries with complex instantiations and inquiries, can be applied to the evaluation of ML recursions as well.

Original languageEnglish (US)
Pages (from-to)1241-1252
Number of pages12
JournalIEEE Transactions on Software Engineering
Issue number12
StatePublished - Dec 1991
Externally publishedYes


  • Deductive database
  • linear recursion
  • logic programming
  • multiple
  • query optimization
  • recursive query processing

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Efficient Evaluation of Multiple Linear Recursions'. Together they form a unique fingerprint.

Cite this