Database Paper Browser

Back to papers

Statistical Estimators for Relational Algebra Expressions

Summary: Develops consistent, unbiased estimators for COUNT(E) over arbitrary relational-algebra expressions without assuming value distributions or tuple ordering. Proposes a cluster-sampling plan to boost sample reuse, cut sampling cost, and empirically evaluates estimator accuracy and efficiency. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
837
Venue
PODS
Year
1988
Pagerank
0.00075597514
Overall Rank
37 | 99.75%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank Citing Paper Year Venue Pagerank
14 Online Aggregation 1997 SIGMOD 0.0010813443
60 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064450997
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
133 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00043220055
140 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00042289025
151 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00041010211
212 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00033997204
216 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00033560137
250 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030640525
291 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00028778973
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
352 Random Sampling from B+ trees 1989 VLDB 0.00026276293
369 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025502381
380 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00024943236
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
531 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.0002079072
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272747
699 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.0001794078
751 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017155121
764 Random Sampling from Hash Files 1990 SIGMOD 0.00016958917
803 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016438972
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
1,019 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014623543
1,254 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013018797
1,790 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 0.00010529479
2,005 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.8168893e-05
2,369 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9462051e-05
3,056 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.6459653e-05
3,841 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB 6.7090738e-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,244 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3228453e-05
4,902 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 5.8415033e-05
6,277 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 5.1260947e-05
7,833 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6367487e-05
8,835 Learning-based Property Estimation with Polynomials 2024 SIGMOD 4.4351469e-05
10,227 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.1905499e-05
12,695 Uniform Generation in Spatial Constraint Databases and Applications 2000 PODS 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank Cited Paper Year Venue Pagerank
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7606324e-05
1,017 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB 0.00014627121
751 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017155121
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
3,706 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 6.8232992e-05
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080571183
7,246 Learning to Sample: Counting with Complex Queries 2020 VLDB 4.7847433e-05
133 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00043220055
291 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00028778973