Back to papers
Simple Random Sampling from Relational Databases
Summary: Proposes simple random sampling directly from relational query results without materializing the full result. For selections, projections, joins, unions, and intersections, it shows data structures and algorithms that run in time proportional to the sample size, enabling efficient auditing.
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
h0547ac8e7ec4217a
Venue
VLDB
Year
1986
Pagerank
0.00026784195
Overall Rank
175 | 98.83%
DOI
-
Incoming Non-self Citations Over Time
Authors
1.
Frank Olken
(Lawrence Berkeley National Laboratory)
2.
Doron Rotem
(Lawrence Berkeley National Laboratory; University of Waterloo)
BibTeX Citation
@article{olken_vldb86,
title = {{Simple Random Sampling from Relational Databases}},
author = {Olken, Frank and Rotem, Doron},
journal = {PVLDB},
series = {{VLDB} '86},
pages = {160--166},
year = {1986}
}
Incoming Citations (Sorted by Pagerank)
Showing 33 of 33 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
57
On Random Sampling over Joins 1999
SIGMOD
0.00040108301
58
Statistical Estimators for Relational Algebra Expressions 1988
PODS
0.00040035279
79
Practical Selectivity Estimation through Adaptive Sampling 1990
SIGMOD
0.00036487763
275
Optimal Histograms with Quality Guarantees 1998
VLDB
0.00022413521
999
Data Compression Support in Databases 1994
VLDB
0.00012617745
1,011
Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990
PODS
0.00012529816
1,428
Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014
SIGMOD
0.00010693831
1,467
On the Relative Cost of Sampling for Join Selectivity Estimation 1994
PODS
0.00010567959
1,607
SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011
CIDR
0.0001008742
2,224
DAQ: A New Paradigm for Approximate Query Processing 2015
VLDB
8.80823e-05
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018
SIGMOD
7.3117029e-05
3,871
A Bi-Level Bernoulli Scheme for Database Sampling 2004
SIGMOD
6.9543581e-05
4,546
Random Sampling from Pseudo-Ranked B+ Trees 1992
VLDB
6.5436884e-05
5,597
StatAdvisor: Recommending Statistical Views 2009
VLDB
6.0718206e-05
6,011
Maintaining Bernoulli Samples over Evolving Multisets 2007
PODS
5.9143905e-05
6,221
Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing 2021
SIGMOD
5.8463347e-05
6,694
MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023
SIGMOD
5.7068014e-05
6,829
Percentile Finding Algorithm for Multiple Sorted Runs 1989
VLDB
5.6696028e-05
6,880
Estimating the Impact of Unknown Unknowns on Aggregate Query Results 2016
SIGMOD
5.6573214e-05
6,967
Sampling Dirty Data for Matching Attributes 2010
SIGMOD
5.6323307e-05
6,992
Skimmer: Rapid Scrolling of Relational Query Results 2012
SIGMOD
5.6267971e-05
7,166
Learning to Sample: Counting with Complex Queries 2020
VLDB
5.5949741e-05
7,246
Efficient Dynamic Weighted Set Sampling and Its Extension 2024
VLDB
5.5750011e-05
7,493
Synopses for Query Optimization: A Space-Complexity Perspective 2004
PODS
5.5103311e-05
7,527
Algebraic Optimization of Computations over Scientific Databases 1993
VLDB
5.5016558e-05
8,223
PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025
SIGMOD
5.3751366e-05
8,870
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views 2015
VLDB
5.2601766e-05
8,886
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds 2025
SIGMOD
5.2559789e-05
8,944
Practical Dynamic Extension for Sampling Indexes 2023
SIGMOD
5.2542285e-05
10,386
Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026
PODS
4.9793485e-05
11,290
Cardinality Estimation for Having-Clauses 2025
VLDB
4.9793485e-05
11,732
Efficient Approximation Framework for Attribute Recommendation 2023
SIGMOD
4.9793485e-05
13,436
Concepts for a Database System Compiler 1988
PODS
4.9793485e-05
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
Semantically Similar Papers