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: 7934
Venue: VLDB
Year: 1986
Pagerank: 0.00027273858
Overall Rank: 173 | 98.82%
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
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012790174
1,017	Data Compression Support in Databases	1994	VLDB	0.00012641552
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
1,440	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010778889
1,582	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010295367
2,206	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.957715e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,803	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	7.1114677e-05
4,458	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.6905953e-05
5,514	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.1901666e-05
5,891	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	6.0495154e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,590	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.8316635e-05
6,699	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.7982932e-05
6,819	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	5.7635226e-05
6,827	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	5.7616041e-05
6,893	Skimmer: Rapid Scrolling of Relational Query Results	2012	SIGMOD	5.7446791e-05
7,048	Learning to Sample: Counting with Complex Queries	2020	VLDB	5.7178054e-05
7,142	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.6917227e-05
7,385	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.6278655e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
8,204	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4667903e-05
8,714	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.3778009e-05
8,724	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.3766157e-05
8,790	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.3722049e-05
10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	5.093636e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,418	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	5.093636e-05
13,146	Concepts for a Database System Compiler	1988	PODS	5.093636e-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,800	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD
2	5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB
3	992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
4	55	Statistical Estimators for Relational Algebra Expressions	1988	PODS
5	467	Random Sampling from B+ trees	1989	VLDB
6	7,335	Reservoir Sampling over Joins	2024	SIGMOD
7	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
8	8,379	Sampling Big Ideas in Query Optimization	2023	PODS
9	802	Random Sampling over Joins Revisited	2018	SIGMOD
10	54	On Random Sampling over Joins	1999	SIGMOD