ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Simple Random Sampling from Relational Databases.

Frank Olken, Doron Rotem: Simple Random Sampling from Relational Databases. VLDB 1986: 160-169
@inproceedings{DBLP:conf/vldb/OlkenR86,
  author    = {Frank Olken and
               Doron Rotem},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Simple Random Sampling from Relational Databases},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {160-169},
  ee        = {db/conf/vldb/OlkenR86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Sampling is a fundamental operation for the auditing and statistical analysis of large databases. It is not well supported in existing relational database management systems. We discuss how to obtain samples from the results of relational queries without first performing the query. Specifically, we examine simple random sampling from selections, projections, joins, unions, and intersections. We discuss data structures and algorithms for sampling, and their performance. We show that samples of relational queries can often be computed for a small fraction of the effort of computing the entire relational query, i.e., in time proportional to sample size, rather than time proportional to the size of the full result of the relational query.

Copyright © 1986 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 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Chr84]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Coc77]
William G. Cochran: Sampling Techniques, 3rd Edition. John Wiley 1977, ISBN 0-471-16240-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dev86]
...
[EN82]
Jarmo Ernvall, Olli Nevalainen: An Algorithm for Unbiased Random Sampling. Comput. J. 25(1): 45-47(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FMR62]
...
[Mor80]
...
[OR86]
...
[Vit84]
Jeffrey Scott Vitter: Faster Methods for Random Sampling. Commun. ACM 27(7): 703-718(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vit85]
Jeffrey Scott Vitter: Random Sampling with a Reservoir. ACM Trans. Math. Softw. 11(1): 37-57(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WE80]
C. K. Wong, Malcolm C. Easton: An Efficient Method for Weighted Sampling Without Replacement. SIAM J. Comput. 9(1): 111-113(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wil84]
Dan E. Willard: Sampling Algorithms for Differential Batch Retrieval Problems (Extended Abstract). ICALP 1984: 514-526 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yao77]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:58 2010 by Michael Ley (ley@uni-trier.de)