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.00026701703
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.0003999751
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
277	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002235043
1,001	Data Compression Support in Databases	1994	VLDB	0.00012586461
1,012	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012489386
1,435	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010659454
1,469	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010533259
1,614	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010054823
2,231	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.7882698e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
3,884	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.9285249e-05
4,563	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5201574e-05
5,611	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0498181e-05
6,022	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.8924888e-05
6,198	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8362492e-05
6,712	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.6852386e-05
6,842	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.6512174e-05
6,881	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	5.6415853e-05
6,988	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	5.6110503e-05
7,010	Skimmer: Rapid Scrolling of Relational Query Results	2012	SIGMOD	5.6056366e-05
7,175	Learning to Sample: Counting with Complex Queries	2020	VLDB	5.5779755e-05
7,267	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.5539363e-05
7,512	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.490671e-05
7,549	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.4809567e-05
7,745	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4457135e-05
8,894	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.2415191e-05
8,915	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2361195e-05
8,976	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.2343756e-05
10,464	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9605343e-05
11,353	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9605343e-05
11,782	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.9605343e-05
13,483	Concepts for a Database System Compiler	1988	PODS	4.9605343e-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

#	Overall Rank	Paper	Year	Venue
1	4,725	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD
2	5,864	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB
3	1,012	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
4	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
5	480	Random Sampling from B+ trees	1989	VLDB
6	7,490	Reservoir Sampling over Joins	2024	SIGMOD
7	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
8	8,579	Sampling Big Ideas in Query Optimization	2023	PODS
9	793	Random Sampling over Joins Revisited	2018	SIGMOD
10	57	On Random Sampling over Joins	1999	SIGMOD