STATISTICAL ESTIMATORS FOR AGGREGATE RELATIONAL ALGEBRA QUERIES

This paper discusses the estimation of COUNT(E) queries by sampling, where E is an arbitrary relational algebra expression. Consistent and unbiased statistical estimators for COUNT(E) are proposed without any assumptions on the distributions of attribute values or the orderings of tuples in the operand relations of E. We present a set of COUNT(E) estimator evaluation algorithms, all based on simple random sampling, and each suitable for a different type of relational algebra expression E. To improve the efficiency, we propose three enhancements, and revise the estimator evaluation algorithms to incorporate the enhancements. One of the enhancements is the use of cluster sampling. Estimator evaluation algorithms with the enhancements have been incorporated into a prototype DBMS. We present the performance evaluation of the estimators using the implemented prototype DBMS.