Title: Evaluation of the size of a query expressed in relational algebra
Abstract: We present a probabilistic model for evaluating the size of relations derived from given relations through relational algebra operators. We define tools to estimate the derived relations size and we state the assumptions underwhich we perform such an evaluation.The particular class of data base schemata in which we evaluate the derived relation size is characterized by properties such as independence between two relations having union-compatible domains or independence between distinct tuples in a relation. We show that, knowing the expected size of all projections of each relation in the database, we can compute the size of each query expressed in relational algebra and we give the results for each operator of this language (selection, projection, union, intersection, e-join).