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: 7744
Venue: VLDB
Year: 1986
Pagerank: 0.00071588702
Overall Rank: 46 | 99.69%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Frank Olken
2. Doron Rotem

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
803	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016438972
894	Data Compression Support in Databases	1994	VLDB	0.00015516667
1,735	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010713691
1,867	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010264932
2,603	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.4634633e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6056349e-05
3,965	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5786424e-05
4,100	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.4473679e-05
4,432	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	6.1858589e-05
5,824	StatAdvisor: Recommending Statistical Views	2009	VLDB	5.311975e-05
6,176	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.1650962e-05
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05
6,724	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.9449472e-05
6,819	Skimmer: Rapid Scrolling of Relational Query Results	2012	SIGMOD	4.9105991e-05
6,943	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	4.8876509e-05
7,246	Learning to Sample: Counting with Complex Queries	2020	VLDB	4.7847433e-05
7,358	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	4.7478752e-05
7,392	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	4.737456e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
8,609	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	4.4810481e-05
8,703	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	4.4596255e-05
9,238	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.3648789e-05
9,760	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2838028e-05
10,389	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	4.1905499e-05
10,647	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1905499e-05
11,219	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.1905499e-05
12,961	Concepts for a Database System Compiler	1988	PODS	4.1905499e-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	Pagerank
4,689	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9899401e-05
6,285	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1231886e-05
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
352	Random Sampling from B+ trees	1989	VLDB	0.00026276293
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
8,467	Sampling Big Ideas in Query Optimization	2023	PODS	4.4995247e-05
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117