Handling Redundancy in the Processing of Recursive Database Queries

Jiawei Han, Lawrence J. Henschen

Research output: Contribution to journalArticlepeer-review


Redundancy may exist in the processing of recursive database queries at four different levels precompilation level, iteration level, tuple processing level and file accessing level. Techniques for reducing redundant work at each level are studied. In the precompilation level, the optimization techniques include removing redundant parts in a rule cluster, simplifying recursive clusters and sharing common subexpressions among rules. At the iteration level, the techniques discussed are the use of frontier relations and the counting method. At the tuple processing level, we use merging and filtering methods to exclude processed drivers from database reaccessing. Finally, at the file accessing level, I/O cost can be further reduced by level relaxation. We conclude that even for complex recursion, redundant database processing can be considerably reduced or eliminated by developing appropriate algorithms.

Original languageEnglish (US)
Pages (from-to)73-81
Number of pages9
JournalACM SIGMOD Record
Issue number3
StatePublished - Dec 1 1987
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Handling Redundancy in the Processing of Recursive Database Queries'. Together they form a unique fingerprint.

Cite this