ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On Tree-Based Techniques for Query Evaluation.

Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
@inproceedings{DBLP:conf/pods/Jakobsson92,
  author    = {H{\aa}kan Jakobsson},
  title     = {On Tree-Based Techniques for Query Evaluation},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {380-392},
  ee        = {http://doi.acm.org/10.1145/137097.137914, db/conf/pods/Jakobsson92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We discuss a technique for query evaluation based on storing intermediary results as trees and study two applications. We first consider the problem of computing the transitive closure of a graph for a specific set of source nodes. Algorithms for this problem can be directly applied to many nonrecursive queries as well. We give a new algorithm and show that it is superior to several previous algorithms. We then consider Warshall's transitive closure algorithm. This algorithm is not O(n e), but we show that by using trees instead flat representations of intermediary results, we can derive a new version of the algorithm with an O(n e) upper bound.

Copyright © 1992 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1010 KB]

References

[ADJ90]
Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990) BibTeX
[AJ87]
Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 BibTeX
[AHU74]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[BS88]
Joachim Biskup, Holger Stiefeling: Transitive Closure Algorithms for Very Large Databases. WG 1988: 122-147 BibTeX
[BKV90]
...
[DJ92]
Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11 BibTeX
[Dzi75]
...
[Ebe81]
Jürgen Ebert: A Sensitive Transitive Closure Algorithm. Inf. Process. Lett. 12(5): 255-258(1981) BibTeX
[Flo62]
...
[GK79]
...
[IR88]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 BibTeX
[Ita86]
Giuseppe F. Italiano: Amortized Efficiency of a Path Retrieval Data Structure. Theor. Comput. Sci. 48(3): 273-281(1986) BibTeX
[JAN87]
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX
[Jak91]
Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205 BibTeX
[Jia90]
Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271 BibTeX
[KRS90]
David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391 BibTeX
[Meh84]
...
[MP91a]
...
[MP91b]
Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141 BibTeX
[Nau87]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
[NRSU89]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 BibTeX
[Pur70]
...
[SCH83]
...
[TH90]
...
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[UY90]
Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53 BibTeX
[War62]
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX
[Yan90]
Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242 BibTeX

Referenced by

  1. Ismail H. Toroslu, Ghassan Z. Qadah: The Strong Partial Transitive-Closure Problem: Algorithms and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 8(4): 617-629(1996)
  2. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
  3. Håkan Jakobsson: On Materializing Views and On-Line Queries. ICDT 1992: 407-420
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:07 2009