ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Estimating the Size of Generalized Transitive Closures.

Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
@inproceedings{DBLP:conf/vldb/LiptonN89,
  author    = {Richard J. Lipton and
               Jeffrey F. Naughton},
  editor    = {Peter M. G. Apers and
               Gio Wiederhold},
  title     = {Estimating the Size of Generalized Transitive Closures},
  booktitle = {Proceedings of the Fifteenth International Conference on Very
               Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands},
  publisher = {Morgan Kaufmann},
  year      = {1989},
  isbn      = {1-55860-101-5},
  pages     = {165-171},
  ee        = {db/conf/vldb/LiptonN89.html},
  crossref  = {DBLP:conf/vldb/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a framework for the estimation of the size of binary recursively defined relations. We show how the framework can be used to provide estimating algorithms for the size of the transitive closure and generalizations of the transitive closure, and also show that for bounded degree relations, the algorithm runs in linear time. Such estimating algorithms are essential if database systems that support recursive relations or fixpoints are to be able to optimize queries and avoid infeasible computations.

Copyright © 1989 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Peter M. G. Apers, Gio Wiederhold (Eds.): Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. Morgan Kaufmann 1989, ISBN 1-55860-101-5
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AJ87]
Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chr83]
Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dem80]
Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HOT88]
Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioa86]
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IR88]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IW87]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KBZ86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMR87]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LN89]
...
[Lu87]
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lyn88]
Clifford A. Lynch: Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values. VLDB 1988: 240-251 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nau87]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NSRU89]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PSC84]
Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RHDM86]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Row83]
Neil C. Rowe: Top-Down Statistical Estimation on a Database. SIGMOD Conference 1983: 135-145 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SG85]
David E. Smith, Michael R. Genesereth: Ordering Conjunctive Queries. Artif. Intell. 26(2): 171-215(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SG88]
Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:22:49 2010 by Michael Ley (ley@uni-trier.de)