Patent ID: 8095515

Claim:
A computer-implemented method for approximating a number of results returned by a query over a relational data source, the method comprising: receiving, by an information processing system, a number of distinct values in each field of each relation in a relational data source, wherein the distinct values are a size approximation; receiving, by the information processing system, a plurality of relationships between fields, where a relationship between a first field and at least a second field is a relationship approximation that approximates a number of distinct values stored in the second field for each value stored in the first field, and where the relationships between fields of a relation are given in a form of a graph whose vertices represent fields of a relation, and whose edges represent relationships between fields and edges are added to the graph using a database schema containing the relationships between fields; producing, by the information processing system based on the size approximation and the relationship approximation, a query size approximation of the number of distinct values in each field of a result of a query; and producing, by the information processing system, based on the query size approximation, a query quantity approximation of a total number of distinct records in the result of the query without running the query against the relational data source.