Evaluation of regular nonlinear recursions by deductive database techniques

Jiawei Han, Laks V.S. Lakshmanan

Research output: Contribution to journalArticlepeer-review


Nonlinear recursion is one of the most challenging classes of logic programs for efficient evaluation in logic programming systems. We identify one popular class of nonlinear recursion, regular nonlinear recursion, and investigate its efficient implementation by a deductive database approach. The approach performs a detailed query binding analysis based on query information, constraint information and the structure of a recursion, selects an appropriate predicate evaluation order and generates an efficient query evaluation plan. Interesting query evaluation techniques, such as chain-following, chain-split, and constraint pushing, are developed for the efficient evaluation of different kinds of queries. Furthermore, the technique can be extended to the evaluation of regular nonlinear recursions in HiLog and F-logic programs. The study not only presents a method for the evaluation of regular nonlinear recursions in a declarative way but also demonstrates the power of the deductive database approach in the analysis and evaluation of sophisticated logic programs.

Original languageEnglish (US)
Pages (from-to)419-441
Number of pages23
JournalInformation Systems
Issue number5
StatePublished - Jul 1995
Externally publishedYes


  • Deductive database
  • declarative programs
  • implementation techniques
  • logic programming
  • nonlinear recursion
  • recursive query evaluation
  • regular nonlinear recursion

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Evaluation of regular nonlinear recursions by deductive database techniques'. Together they form a unique fingerprint.

Cite this