Method to estimate the number of distinct value combinations for a set of attributes in a database system
AssigneeInternational Business Machines Corporation
InventorsCalisto Paul Zuzarte, Xiaohui Yu
Life of this patent
Estimating the term…
Abstract
A method to estimate the number of distinct value combinations for a set of attributes in a database system is disclosed. The method comprises utilizing frequency information within the set of attributes to provide a best estimate for the number of distinct value combinations. In a preferred embodiment, the utilizing step comprises estimating the number of distinct value combinations utilizing frequency information of the set of attributes based upon probability theory and further includes providing bounds on the distinct value information combinations utilizing the frequency information of the set of attributes. In so doing, an estimate for the number of distinct value combinations is provided.
Claims14
A method implemented by a computer system including a processor to estimate the number of distinct value combinations for a set of attributes in a table of a database system, the number of distinct value combinations being provided for a number of distinct values of each of the attributes in the set of attributes, the method comprising:
- using the processor to utilize frequency information for the set of attributes to provide an estimate for the number of distinct value combinations, wherein the frequency information includes individual frequency statistics for each individual attribute in the set of attributes, the individual frequency statistics indicating the number of times each distinct value appears in each individual attribute in the set of attributes,
- wherein using the processor to utilize frequency information includes:
- using the individual frequency statistics to determine a probability of occurrence of each specific value combination of the distinct values, and
- using the probability of occurrence of each specific value combination to provide the estimate for the number of distinct value combinations, including determining a lower number of distinct value combinations than a maximum number of distinct value combinations for the distinct values, wherein determining a lower number of distinct value combinations includes subtracting from the maximum possible number of distinct value combinations a sum of probabilities that the value combinations do not occur in the table, wherein the sum of probabilities is determined using the individual frequency statistics.
A non-transitory computer readable storage medium storing program instructions implemented by a computer system for estimating the number of distinct value combinations for a set of attributes in a table of a database system, the number of distinct value combinations being provided for a number of distinct values of each of the attributes in the set of attributes, the program instructions for:
- utilizing frequency information for the set of attributes to provide an estimate for the number of distinct value combinations, wherein the frequency information includes individual frequency statistics for each individual attribute in the set of attributes, the individual frequency statistics indicating the number of times each distinct value appears in each individual attribute in the set of attributes,
- wherein utilizing the frequency information includes:
- using the individual frequency statistics to determine a probability of occurrence of each specific value combination of the distinct values, and
- using the probability of occurrence of each specific value combination to provide the estimate for the number of distinct value combinations, including determining a lower number of distinct value combinations than a maximum number of distinct value combinations for the distinct values, wherein determining a lower number of distinct value combinations includes subtracting from the maximum possible number of distinct value combinations a sum of probabilities that the value combinations do not occur in the table, wherein the sum of probabilities is determined using the individual frequency statistics.
A data processing system for estimating the number of distinct value combinations for a set of attributes, the number of distinct value combinations being provided for a number of distinct values of each of the attributes in the set of attributes, the data processing system comprising:
- at least one storage element storing a table of a database system, the set of attributes applying to the table;
- and
- at least one processor utilizing frequency information for the set of attributes to provide an estimate for the number of distinct value combinations, wherein the frequency information includes individual frequency statistics for each individual attribute in the set of attributes, the individual frequency statistics indicating the number of times each distinct value appears in each individual attribute in the set of attributes.
- wherein using the processor utilizing the frequency information includes:
- using the individual frequency statistics to determine a probability of occurrence of each specific value combination of the distinct values, and
- using the probability of occurrence of each specific value combination to provide the estimate for the number of distinct value combinations, including determining a lower number of distinct value combinations than a maximum number of distinct value combinations for the distinct values, wherein determining a lower number of distinct value combinations includes subtracting from the maximum possible number of distinct value combinations a sum of probabilities that the value combinations do not occur in the table, wherein the sum of probabilities is determined using the individual frequency statistics.
Dependencies are inferred from the claim text.