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: 7743
Venue: VLDB
Year: 1986
Pagerank: 0.00070894702
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.00092385438
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
811	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016425612
898	Data Compression Support in Databases	1994	VLDB	0.00015525779
1,874	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010244443
1,909	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010121304
2,616	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.4471955e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6078243e-05
3,966	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.580483e-05
4,100	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.4531387e-05
4,435	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	6.1918164e-05
5,815	StatAdvisor: Recommending Statistical Views	2009	VLDB	5.3165295e-05
6,174	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.1696569e-05
6,190	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1645517e-05
6,740	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.944395e-05
6,822	Skimmer: Rapid Scrolling of Relational Query Results	2012	SIGMOD	4.9152454e-05
6,941	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	4.8924e-05
7,251	Learning to Sample: Counting with Complex Queries	2020	VLDB	4.7890519e-05
7,362	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	4.752436e-05
7,395	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	4.7420041e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
8,610	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	4.4853485e-05
8,728	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	4.4589711e-05
9,758	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2879116e-05
10,377	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	4.1945683e-05
10,497	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.1945683e-05
10,639	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1945683e-05
11,217	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.1945683e-05
12,951	Concepts for a Database System Compiler	1988	PODS	4.1945683e-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,694	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9944898e-05
6,286	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1280225e-05
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
357	Random Sampling from B+ trees	1989	VLDB	0.00026020098
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
8,470	Sampling Big Ideas in Query Optimization	2023	PODS	4.5038423e-05
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438