TY - JOUR
T1 - Binding propagation beyond the reach of rule / goal graphs
AU - Han, Jiawei
N1 - Funding Information:
The work was supported in part by the Natural Sciences and Engineering Research Council of Canada under grant A-3723. The author would like to express his thanks to Lawrence J. Hen-schen, Michael Kifer, Raghu Ramakrishnan, Ko-tagiri Ramamohanarao, Yehoshua Sagiv, Shalom Tsur and Carlo Zaniolo for their helpful discussions on the binding propagation problems.
PY - 1992/7/3
Y1 - 1992/7/3
N2 - 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.
AB - 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.
KW - Databases
KW - deductive databases
KW - linear recursions
KW - rule / goal graphs
KW - rule rewriting techniques
KW - the Magic Sets method
KW - the recursive query evaluation
UR - http://www.scopus.com/inward/record.url?scp=28044448925&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=28044448925&partnerID=8YFLogxK
U2 - 10.1016/0020-0190(92)90034-S
DO - 10.1016/0020-0190(92)90034-S
M3 - Article
AN - SCOPUS:28044448925
SN - 0020-0190
VL - 42
SP - 263
EP - 268
JO - Information Processing Letters
JF - Information Processing Letters
IS - 5
ER -