Handling Redundancy in the Processing of Recursive Database Queries

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

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
Volume16
Issue number3
DOIs
StatePublished - Dec 1 1987

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint

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

Cite this