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.00026776696
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.00040095727
58
Statistical Estimators for Relational Algebra Expressions 1988
PODS
0.00040025054
79
Practical Selectivity Estimation through Adaptive Sampling 1990
SIGMOD
0.00036476265
275
Optimal Histograms with Quality Guarantees 1998
VLDB
0.00022404363
999
Data Compression Support in Databases 1994
VLDB
0.00012615754
1,011
Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990
PODS
0.00012524973
1,428
Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014
SIGMOD
0.0001069161
1,467
On the Relative Cost of Sampling for Join Selectivity Estimation 1994
PODS
0.00010563809
1,608
SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011
CIDR
0.00010085907
2,219
DAQ: A New Paradigm for Approximate Query Processing 2015
VLDB
8.8127129e-05
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018
SIGMOD
7.3084429e-05
3,872
A Bi-Level Bernoulli Scheme for Database Sampling 2004
SIGMOD
6.9512121e-05
4,546
Random Sampling from Pseudo-Ranked B+ Trees 1992
VLDB
6.5406658e-05
5,598
StatAdvisor: Recommending Statistical Views 2009
VLDB
6.0690976e-05
6,011
Maintaining Bernoulli Samples over Evolving Multisets 2007
PODS
5.911598e-05
6,202
Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing 2021
SIGMOD
5.8494367e-05
6,698
MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023
SIGMOD
5.7040999e-05
6,825
Percentile Finding Algorithm for Multiple Sorted Runs 1989
VLDB
5.6698066e-05
6,885
Estimating the Impact of Unknown Unknowns on Aggregate Query Results 2016
SIGMOD
5.6546466e-05
6,968
Sampling Dirty Data for Matching Attributes 2010
SIGMOD
5.6296644e-05
6,994
Skimmer: Rapid Scrolling of Relational Query Results 2012
SIGMOD
5.6241476e-05
7,152
Learning to Sample: Counting with Complex Queries 2020
VLDB
5.5959861e-05
7,248
Efficient Dynamic Weighted Set Sampling and Its Extension 2024
VLDB
5.572362e-05
7,496
Synopses for Query Optimization: A Space-Complexity Perspective 2004
PODS
5.5081355e-05
7,532
Algebraic Optimization of Computations over Scientific Databases 1993
VLDB
5.4991388e-05
7,749
PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025
SIGMOD
5.4585522e-05
8,876
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views 2015
VLDB
5.2587627e-05
8,895
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds 2025
SIGMOD
5.2534908e-05
8,953
Practical Dynamic Extension for Sampling Indexes 2023
SIGMOD
5.2517412e-05
10,398
Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026
PODS
4.9769913e-05
11,298
Cardinality Estimation for Having-Clauses 2025
VLDB
4.9769913e-05
11,738
Efficient Approximation Framework for Attribute Recommendation 2023
SIGMOD
4.9769913e-05
13,442
Concepts for a Database System Compiler 1988
PODS
4.9769913e-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