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.00040035279
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.00076195956
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036487763
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030470848
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029866033
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029627449
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026389403
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024344086
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023792809
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022722971
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021914399
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020329113
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
477 Random Sampling from B+ trees 1989 VLDB 0.00017632787
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017408001
519 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016942879
745 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014288286
821 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013660347
1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012529816
1,184 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00011611937
1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011548537
1,229 Random Sampling from Hash Files 1990 SIGMOD 0.00011420642
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010734049
1,467 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010567959
1,661 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9535453e-05
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5575424e-05
1,891 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4184294e-05
3,005 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7621043e-05
3,341 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB 7.4063139e-05
3,871 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9543581e-05
4,217 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.7271293e-05
4,546 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5436884e-05
5,254 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 6.2079513e-05
5,656 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0488629e-05
8,325 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3540828e-05
9,013 Learning-based Property Estimation with Polynomials 2024 SIGMOD 5.2375369e-05
10,700 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.9793485e-05
13,169 Uniform Generation in Spatial Constraint Databases and Applications 2000 PODS 4.9793485e-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.00026784195
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,456 A Sampling Algebra for Aggregate Estimation 2013 VLDB
2 682 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB
3 1,011 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 36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD
7 3,131 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
8 7,166 Learning to Sample: Counting with Complex Queries 2020 VLDB
9 181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD
10 492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD