Handling Redundancy in the Processing of Recursive Database Queries.

Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81

@inproceedings{DBLP:conf/sigmod/HanH87,
  author    = {Jiawei Han and
               Lawrence J. Henschen},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Handling Redundancy in the Processing of Recursive Database Queries},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {73-81},
  ee        = {http://doi.acm.org/10.1145/38713.38727, db/conf/sigmod/HanH87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Redundancy may exist in the processing of recursive database queries at four different levels: precompilation level, iteration level, tuple processing level and file accessing level. Techniques for reducing redundant work at each level are studied. In the precompilation level, the optimization techniques include removing redundant parts in a rule cluster, simplifying recursive clusters and sharing common subexpressions among rules. At the iteration level, the techniques discussed are the use of frontier relations and the counting method. At the tuple processing level, we use merging and filtering methods to exclude processed drivers from database reaccessing. Finally, at the file accessing level, I/O cost can be further reduced by level relaxation. We conclude that even for complex recursion, redundant database processing can be considerably reduced or eliminated by developing appropriate algorithms.

Copyright © 1987 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 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

Printed Edition

Umeshwar Dayal, Irving L. Traiger (Eds.): Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987. ACM Press 1987 BibTeX , SIGMOD Record 16(3)
Contents

Online Edition: ACM Digital Library

References

[Agra 87]: Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX
[BaRa 86]: François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[BMSU 86]: 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
[CGM 86]: ...
[HaHE 86a]: ...
[HaHe 86b]: ...
[HaHe 87]: ...
[HHS 87]: ...
[HeNa 84]: Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[IoWo 86]: Yannis E. Ioannidis, Eugene Wong: An Algebraic Approach to Recursive Inference. Expert Database Conf. 1986: 295-309 BibTeX
[KOT 86]: Charles Kellogg, Anthony B. O'Hare, Larry Travis: Optimizing the Rule-Data Interface in a KMS. VLDB 1986: 42-51 BibTeX
[KrZa 86]: ...
[LMR 87]: Hongjun Lu, Krishna P. Mikkilineni, James P. Richardson: Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation. ICDE 1987: 112-119 BibTeX
[Lozi 86]: Eliezer L. Lozinskii: A Problem-Oriented Inferential Database System. ACM Trans. Database Syst. 11(3): 323-356(1986) BibTeX
[RHDM 86]: Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[Sagi 87]: Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[Ullm 85]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[VaBo 86]: Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX
[Viel 86]: Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

Referenced by

Cheong Youn, Hyoung-Joo Kim, Lawrence J. Henschen, Jiawei Han: Classification and Compilation of Linear Recursive Queries in Deductive Databases. IEEE Trans. Knowl. Data Eng. 4(1): 52-67(1992)
Weining Zhang, Clement T. Yu, Daniel Troy: Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases. ACM Trans. Database Syst. 15(3): 459-482(1990)
Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
Yuki Kusumi, Shojiro Nishio, Toshiharu Hasegawa: File Access Level Optimization Using Page Access Graph on Recursive Query Evaluation. EDBT 1990: 136-152
Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989)
Hussien Aly, Z. Meral Özsoyoglu: Synchronized Counting Method. ICDE 1989: 366-373
Jai Hyoung Rhee, Seog Park: An Extension of Counting Method for Efficient Processing of the Cyclic Data. DASFAA 1989: 320-326
Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. DASFAA 1989: 285-292
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
Cheong Youn, Lawrence J. Henschen, Jiawei Han: Classification of Recursive Formulas in Deductive Databases. SIGMOD Conference 1988: 320-328
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319
Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340
Sanggoo Lee, Jiawei Han: Semantic Query Optimization in Recursive Databases. ICDE 1988: 444-451
Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75

BibTeX

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