APPROXIMATING RELATION SIZES USING FIELD DEPENDENCIES

A method and system is provided for computing an approximation of the number of distinct results of a query over a relational data source. The approximation uses information about dependencies between fields of relations, in particular the number of distinct values of a field for each possible value of another field. This information can be obtained by analysis of the data stored in the relational data source, or may be specified as annotations to a database schema. An approximation of the number of results is and the dependencies between fields of each part of the query are computed. The approximation can be used to reorder parts of a query, by using the estimated size of parts to guide reordering. The approximation can further be used to determine which parts of a query are relevant to the evaluation of a subquery, which can be used to guide the magic sets transformation.