Binding propagation beyond the reach of rule / goal graphs

Research output: Contribution to journalArticlepeer-review


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
Issue number5
StatePublished - Jul 3 1992
Externally publishedYes


  • 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


Dive into the research topics of 'Binding propagation beyond the reach of rule / goal graphs'. Together they form a unique fingerprint.

Cite this