A New Recursive Query Evaluation Strategy Using Search History Information.

Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
  author    = {Shojiro Nishio and
               Masatsugu Nakahata and
               Eric G. Manning},
  editor    = {Sukho Lee and
               Hideko S. Kunii and
               Won Kim and
               In Sup Paik and
               Yahiko Kambayashi},
  title     = {A New Recursive Query Evaluation Strategy Using Search History
  booktitle = {International Symposium on Database Systems for Advanced Applications,
               Seoul, Korea, April 10-12, 1989},
  publisher = {Dept. of Computer Science, KAIST, P.O. Box 150, ChongRyang, Seoul,
               131-650, Korea},
  year      = {1989},
  pages     = {310-319},
  ee        = {db/conf/dasfaa/NishioNM89.html},
  crossref  = {DBLP:conf/dasfaa/89},
  bibsource = {DBLP,}


We propose a new general purpose query evaluation algorithm "WINC" for the stable multiple linear recursiye rule system. Algorithm WINC always terminates and computes the complete answer for a given query without executing any redundant searching by means of search history information. Its performance is not inferior to that of Magic Set method, and it works very efficiently in case that any redundant data exist in the extensional database.

Copyright © 1989 by The Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. Permission to copy without all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the DASFAA copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. To copy otherwise, or to republish, requires a fee and/or special permission from the Organizing Commitee.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 2, EDBT, ICDT, MFDBS, DASFAA" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX


François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402 BibTeX
Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 BibTeX
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX
Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:05:14 2009