Classification of recursive formulas in deductive databases

Cheong Youn, Lawrence J. Henschen, Jiawei Han

Research output: Contribution to journalArticlepeer-review


In this paper, we present results on the classification of linear recursive formulas in deductive databases and apply those results to the compilation and optimization of recursive queries. We also introduce compiled formulas and query evaluation plans for a representative query for each of these classes. To explain general recursive formulas, we use a graph model that shows the connectivity between variables. The connecticity between variables is the most critical part in processing recursive formulas. We demonstrate that based on such a graph model all the linear recursive formulas can be classified into several classes and each class shares some common characteristics in compilation and query processing. The compiled formulas and the corresponding query evaluation plans can be derived based on the study of the compilation of each class.

Original languageEnglish (US)
Pages (from-to)320-328
Number of pages9
JournalACM SIGMOD Record
Issue number3
StatePublished - Jun 1 1988
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Classification of recursive formulas in deductive databases'. Together they form a unique fingerprint.

Cite this