Error-Constrained COUNT Query Evaluation in Relational Databases

Summary: Introduces double sampling for error-constrained COUNT(E) in relational algebra, guaranteeing an estimator within a user-specified error e at a given confidence. Compares double sampling to adaptive sampling, showing sample-size tradeoffs, with prototype CASE-MDB and real-time experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2536
Venue: SIGMOD
Year: 1991
Pagerank: 0.0002802103
Overall Rank: 315 | 97.82%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272061
811	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016425612
1,020	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00014624893
1,255	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013024064
1,797	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	0.00010523169
3,842	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	6.7102374e-05
7,415	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	4.7355557e-05
10,497	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
134	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00042452811
688	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00018134733
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7137441e-05
3,702	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8295759e-05
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
7,251	Learning to Sample: Counting with Complex Queries	2020	VLDB	4.7890519e-05
9,523	Analysis and Application of Adaptive Sampling	2000	PODS	4.331052e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
134	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00042452811
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564