Abstract

Rule / goal graphs have been popularly used in the analysis of binding propagation in deductive databases. Some interesting techniques, such as the Magic rule rewriting and its variations, have been developed based on such an analysis. We re-examine the binding propagation in linear recursions and demonstrate that the rule / goal graph cannot capture the binding propagation information for certain kinds of linear recursions, and hence the Magic rule rewriting technique cannot derive the minimal Magic Sets for such recursions. A compilation technique, based on the simulation of recursive rule expansions, is proposed to solve this problem.

Original languageEnglish (US)
Pages (from-to)263-268
Number of pages6
JournalInformation Processing Letters
Volume42
Issue number5
DOIs
StatePublished - Jul 3 1992

    Fingerprint

Keywords

  • Databases
  • deductive databases
  • linear recursions
  • rule / goal graphs
  • rule rewriting techniques
  • the Magic Sets method
  • the recursive query evaluation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this