A Bayesian Nonparametric Approach to Query Optimization

The thesis presents several approaches to the estimation of the number of distinct values in a database relation, which is a key quantity for query optimization purposes. In particular, we consider the case of data following a Power Law distribution, which is an assumption that allows to model different human activity data. After a review of the estimators proposed in the literature, we present a Bayesian nonparametric apprroach based on the Pitman Yor process that is particularly fitted for this estimation problem. Finally, we test and compare the estimators on real human activity databases. ​