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
836
Venue
PODS
Year
1988
Pagerank
0.00040746149
Overall Rank
55 | 99.63%
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.00077458002
75 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00037277061
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
131 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00030424509
132 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030378624
136 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00030123303
178 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026881845
210 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024797689
222 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00024193708
255 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00023174541
288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022296371
339 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020723773
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
418 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018812821
467 Random Sampling from B+ trees 1989 VLDB 0.00018002218
484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017746696
508 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00017275873
730 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014539362
801 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013909408
992 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012790174
1,172 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00011825923
1,186 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011764128
1,206 Random Sampling from Hash Files 1990 SIGMOD 0.00011663837
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
1,440 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010778889
1,634 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 0.00010163938
1,806 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.7112151e-05
1,893 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.5269935e-05
2,984 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.8920597e-05
3,288 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB 7.5578177e-05
3,803 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 7.1114677e-05
4,138 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.8779166e-05
4,458 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.6905953e-05
5,142 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 6.3482762e-05
5,537 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.1820087e-05
8,155 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.4766319e-05
8,850 Learning-based Property Estimation with Polynomials 2024 SIGMOD 5.3577504e-05
10,515 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 5.093636e-05
12,879 Uniform Generation in Spatial Constraint Databases and Applications 2000 PODS 5.093636e-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
173 Simple Random Sampling from Relational Databases 1986 VLDB 0.00027273858
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,413 A Sampling Algebra for Aggregate Estimation 2013 VLDB
2 682 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB
3 992 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS
4 173 Simple Random Sampling from Relational Databases 1986 VLDB
5 76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
6 3,215 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,048 Learning to Sample: Counting with Complex Queries 2020 VLDB
9 178 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD
10 484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD