Relational Operators in Heterogeneous Random Databases

In this paper, we investigate the sizes of some approximate relational operations results, focusing on join, outer join and difference. We extend the notion of random database, in which the records are random vectors following a certain probability distribution, to heterogeneous random databases, in which each column can have its own unidimensional distribution. In this framework, we will investigate if the results already existing for the homogeneous databases remain true. Our approach follows three steps. First, we build up the histograms for some relational operations on heterogeneous tables with specific distributions, then we apply the chi square test of goodness of fit and, in the end, we prove the result that sets the limits for which the cardinality of the self-join can be approximated by a Poisson distribution.