A Comparison of I/O Performance of Some Linear Recursive Query Processing Methods.

Wo-Shun Luk, Simon Mok: A Comparison of I/O Performance of Some Linear Recursive Query Processing Methods. DASFAA 1989: 293-300

@inproceedings{DBLP:conf/dasfaa/LukM89,
  author    = {Wo-Shun Luk and
               Simon Mok},
  editor    = {Sukho Lee and
               Hideko S. Kunii and
               Won Kim and
               In Sup Paik and
               Yahiko Kambayashi},
  title     = {A Comparison of I/O Performance of Some Linear Recursive Query
               Processing Methods},
  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     = {293-300},
  ee        = {db/conf/dasfaa/LukM89.html},
  crossref  = {DBLP:conf/dasfaa/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

This paper studies the I/O performance of four popular query processing methods for deductive databases when they am applied to a linear recursive rule set popularly known as the same-generation rule set. These methods are: Henschen-Naqvi. Counting, Reverse Counting and Magic Set. Our analysis and simulation identify Counting as the most efficient method so long as there is not an extraordinarily deep recursion. The paper contains also a new characterization of these four methods according to the ordering in which the necessary join operations are performed. The scheme we adopt to present these methods is arguably more natural, and hence more easily understandable than the scheme used to present them in the original paper. Since it is mom implementationally oriented, it also provides a better framework for performance comparisons.

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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

References

[BMSU86]: 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
[BR86]: François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[GMN84]: Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
[HH87]: ...
[HL86]: Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541 BibTeX
[HN84]: Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[YZ87]: Clement T. Yu, Weining Zhang: Efficient Recursive Query Processing using Wavefront Methods. ICDE 1987: 652-657 BibTeX
[Z86]: Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]