A Study on the Structure of Linear Recursion

Wenyu Lu, Dik Lun Lee, Jiawei Han

Research output: Contribution to journalArticlepeer-review


We study a general class of single linear recursions and the properties of their expansions by analyzing the structures of the recursions. We show that the expansions of a linear recursion of this class are very regular in that the variable connections are heavily shared and change periodically with respect to the expansions. The variable connections can be precisely characterized as static bindings and chain connections. We conclude that a single linear recursion under our assumptions either is bounded or can be expressed as chain recursions. This study contributes to query processing, because it provides the basis for rule compilation as a general and powerful technique for query processing. Combined with query information, the expansion properties of the recursion provide optimized query-processing plans.

Original languageEnglish (US)
Pages (from-to)723-737
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number5
StatePublished - Oct 1994
Externally publishedYes


  • Query processing
  • deductive database
  • logic database
  • query compilation
  • rule classification
  • rule compilation

ASJC Scopus subject areas

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


Dive into the research topics of 'A Study on the Structure of Linear Recursion'. Together they form a unique fingerprint.

Cite this