DBScholar

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
h0c59eb4aed44e7f9
Venue
PODS
Year
1988
Pagerank
0.00039922419
Overall Rank
58 | 99.62%
DOI
10.1145/308386.308455

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{hou_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Statistical Estimators for Relational Algebra Expressions}},
        url = {https://dl.acm.org/doi/10.1145/308386.308455},
        doi = {10.1145/308386.308455},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hou, Wen-Chu and Ozsoyoglu, Gultekin and Taneja, Baldeo K},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank Citing Paper Year Venue Pagerank
9 Online Aggregation 1997 SIGMOD 0.00076079812
78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036725074
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030398363
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029805026
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
183 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026316699
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024275691
234 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023726296
268 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022654182
296 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021874894
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020265363
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
480 Random Sampling from B+ trees 1989 VLDB 0.00017573936
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017359343
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
750 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014246313
822 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013616674
1,012 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012489386
1,187 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00011580993
1,206 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011510881
1,237 Random Sampling from Hash Files 1990 SIGMOD 0.00011381076
1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010696781
1,469 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010533259
1,668 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9190265e-05
1,828 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5396315e-05
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
3,009 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7439468e-05
3,348 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB 7.3783668e-05
3,884 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9285249e-05
4,236 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.7028998e-05
4,563 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5201574e-05
5,279 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 6.1848178e-05
5,670 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0266818e-05
8,346 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3339321e-05
9,032 Learning-based Property Estimation with Polynomials 2024 SIGMOD 5.219814e-05
10,771 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.9605343e-05
13,216 Uniform Generation in Spatial Constraint Databases and Applications 2000 PODS 4.9605343e-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
175 Simple Random Sampling from Relational Databases 1986 VLDB 0.00026701703
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,461 A Sampling Algebra for Aggregate Estimation 2013 VLDB
2 676 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB
3 1,012 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS
4 175 Simple Random Sampling from Relational Databases 1986 VLDB
5 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
6 3,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
7 36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD
8 7,175 Learning to Sample: Counting with Complex Queries 2020 VLDB
9 183 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD
10 492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD