US5999928A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Estimating the number of distinct values for an attribute in a relational database table
Assignee: International Business Machines Corp
•
Filing: 1997-06-30
•
Granted: 1999-12-07
•
Expires: 2017-06-30
Abstract
Abstract A method and apparatus for estimating the number of distinct values in a database table selects one of several numerical methods to solve a model of the number of distinct values in a database table based on a table size, a sample size, and the number of distinct values in the sample. The sample may be a sample previously collected for purposes other than to estimate the number of distinct values, and the number of records in the sample and the number of distinct values in the sample may be determined at the time the sample was collected.
Inventors
- 👤 Weipeng Yan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 09:29
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24545; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/954; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
204 words
In a relational database system, a computer-implemented method for estimating the number of distinct values for an attribute in a database table, comprising: determining a size of the database table; obtaining a sample of records from the database table and determining a number of records in the sample and a number of distinct values for the attribute in the sample; and using the size of the database table, the size of the sample, and the number of distinct values for the attribute in the sample to select one of a plurality of numerical methods to solve a model of the number of distinct values for the attribute in the database table to calculate an estimate of the number of distinct values for the attribute in the database table, wherein the model is 0=1-N/n*(1-(1-t/T).sup.(T/N)), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in the sample, t is the number of records in the sample, and T is the size of the database table, and where solving for N, given values of n, t, and T, yields an estimate of the number of distinct values in the database table.
Claim 2
Dependent Claim
204 words
In a relational database system, a computer-implemented method for estimating the number of distinct values for an attribute in a database table, comprising: determining a size of the database table; obtaining a sample of records from the database table and determining a number of records in the sample and a number of distinct values for the attribute in the sample; and using the size of the database table, the size of the sample, and the number of distinct values for the attribute in the sample to select one of a plurality of numerical methods to solve a model of the number of distinct values for the attribute in the database table to calculate an estimate of the number of distinct values for the attribute in the database table, wherein the model is 0=1-N/n*(1-(1-t/T).sup.(T/N)), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in the sample, t is the number of records in the sample, and T is the size of the database table, and where solving for N, given values of n, t, and T, yields an estimate of the number of distinct values in the database table.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein: the plurality of numerical methods include the secant method and the bisection method.
Claim 4
Dependent Claim
89 words
The method of claim 1, wherein: the number of distinct values in the sample divided by the sample size is compared to a threshold value, and if the quotient is less than or equal to the threshold value, using the secant method as the selected numerical method, and if the quotient is greater than the threshold value or the secant method produces an error, using the bisection method as the selected numerical method, and if the bisection method produces an error, using Newton's method as the selected numerical method.
Claim 5
Dependent Claim
38 words
The method of claim 3, wherein: if Newton's method produces an error, the estimated number of distinct values is half the sum of the number of distinct values in the sample and the size of the database table.
Claim 6
Dependent Claim
75 words
The method of claim 3, wherein: if the estimated number of distinct values is less than the number of distinct values in the sample, then the estimated number of distinct values is set to the number of distinct values in the sample; and if the estimated number of distinct values is greater than the size of the database table, then the estimated number of distinct values is set to the size of the database table.
Claim 7
Dependent Claim
11 words
The method of claim 3, wherein: the threshold value is 0.32.
Claim 8
Dependent Claim
67 words
The method of claim 3, wherein: the sample was previously collected for a purpose other than to estimate distinct values in the database table; the number of records in the sample and the number of distinct values in the sample were determined at the time the sample was collected; and the error arising from applying the numerical method comprises a failure of the numerical method to converge.
Claim 9
Dependent Claim
27 words
The method of claim 1, wherein: the sample was previously collected for a purpose other than to estimate the number of distinct values in the database table.
Claim 10
Dependent Claim
37 words
The method of claim 1, wherein: the sample was previously collected and the number of records in the sample and the number of distinct values in the sample were determined at the time the sample was collected.
Claim 11
Dependent Claim
24 words
The method of claim 1, further comprising: selecting and using a second numerical method if an error occur using the first selected numerical method.
Claim 12
Dependent Claim
24 words
The method of claim 10, further comprising: selecting and using a third numerical method if an error occurs using the second selected numerical method.
Claim 13
Dependent Claim
135 words
A computer-implemented method for estimating the number of distinct values for an attribute in a database table, comprising: using a model of the number of distinct values for the attribute in the database table, the model being 0=1-N/n*(1-(1-t/T).sup.(T/N)), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in a sample from the database table, t is the number of records in the sample, and T is the size of the database table; and solving for N, given values of n, t, and T, by using a numerical method to find a value for N that satisfies the model, the found value for N being the estimate of the number of distinct values for the attribute in the database table.
Claim 14
Dependent Claim
135 words
A computer-implemented method for estimating the number of distinct values for an attribute in a database table, comprising: using a model of the number of distinct values for the attribute in the database table, the model being 0=1-N/n*(1-(1-t/T).sup.(T/N)), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in a sample from the database table, t is the number of records in the sample, and T is the size of the database table; and solving for N, given values of n, t, and T, by using a numerical method to find a value for N that satisfies the model, the found value for N being the estimate of the number of distinct values for the attribute in the database table.
Claim 15
Dependent Claim
195 words
A computer program, residing on a computer-readable medium, comprising instructions causing a computer to: determine a size of a database table; obtain a sample of records from the database table, and determine a number of records in the sample and a number of distinct values for an attribute in the sample; and use the size of the database table, the size of the sample, and the number of distinct values for the attribute in the sample to select one of a plurality of numerical methods to solve a model of the number of distinct values for the attribute in the database table to calculate an estimate of the number of distinct values for the attribute in the database table, wherein the model is 0=1-N/n*(1-(1-t/T).sup.(T/N), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in the sample, t is the number of records in the sample, and T is the size of the database table, and where solving for N, given values of n, t, and T, yields an estimate of the number of distinct values in the database table.
Claim 16
Dependent Claim
195 words
A computer program, residing on a computer-readable medium, comprising instructions causing a computer to: determine a size of a database table; obtain a sample of records from the database table, and determine a number of records in the sample and a number of distinct values for an attribute in the sample; and use the size of the database table, the size of the sample, and the number of distinct values for the attribute in the sample to select one of a plurality of numerical methods to solve a model of the number of distinct values for the attribute in the database table to calculate an estimate of the number of distinct values for the attribute in the database table, wherein the model is 0=1-N/n*(1-(1-t/T).sup.(T/N), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in the sample, t is the number of records in the sample, and T is the size of the database table, and where solving for N, given values of n, t, and T, yields an estimate of the number of distinct values in the database table.
Claim 17
Dependent Claim
90 words
The computer program of claim 13, wherein: the number of distinct values in the sample divided by the sample size is compared to a threshold value, and if the quotient is less than or equal to the threshold value, using the secant method as the selected numerical method, and if the quotient is greater than the threshold value or the secant method produces an error, using the bisection method as the selected numerical method, and if the bisection method produces an error, using Newton's method as the selected numerical method.
Claim 18
Dependent Claim
39 words
The computer program of claim 14, wherein: if Newton's method produces an error, the estimated number of distinct values is half the sum of the number of distinct values in the sample and the size of the database table.
Claim 19
Dependent Claim
76 words
The computer program of claim 14, wherein: if the estimated number of distinct values is less than the number of distinct values in the sample, then the estimated number of distinct values is set to the number of distinct values in the sample; and if the estimated number of distinct values is greater than the size of the database table, then the estimated number of distinct values is set to the size of the database table.
Claim 20
Dependent Claim
12 words
The computer program of claim 14, wherein: the threshold value is 0.32.
Claim 21
Dependent Claim
68 words
The computer program of claim 14, wherein: the sample was previously collected for a purpose other than to estimate distinct values in the database table; the number of records in the sample and the number of distinct values in the sample were determined at the time the sample was collected; and the error arising from applying the numerical method comprises a failure of the numerical method to converge.
Claim 22
Dependent Claim
27 words
The computer program of claim 13, wherein: the sample was previously collected for purposes other than to estimate the number of distinct values in the database table.
Claim 23
Dependent Claim
38 words
The computer program of claim 13, wherein: the sample was previously collected and the number of records in the sample and the number of distinct values in the sample were determined at the time the sample was collected.
Claim 24
Dependent Claim
27 words
The computer program of claim 13, further comprising instructions to: select and use a second numerical method if an error occurs using the first selected numerical method.
Claim 25
Dependent Claim
27 words
The computer program of claim 21, further comprising instructions to: select and use a third numerical method if an error occurs using the second selected numerical method.
Claim 26
Dependent Claim
131 words
A computer program, residing on a computer-readable medium, comprising instructions causing a computer to: use a model of the number of distinct values for an attribute in a database table, the model being 0=1-N/n*(1-(1-T).sup.(T/N)), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in a sample from the database table, t is the number of records in the sample, and T is the size of the database table; and solving for N, given values of n, t, and T, by using a numerical method to find a value for N that satisfies the model, the found value for N being the estimate of the number of distinct values for the attribute in the database table.
Claim 27
Dependent Claim
131 words
A computer program, residing on a computer-readable medium, comprising instructions causing a computer to: use a model of the number of distinct values for an attribute in a database table, the model being 0=1-N/n*(1-(1-T).sup.(T/N)), where N is the number of distinct values for the attribute in the database table, n is the number of distinct values for the attribute in a sample from the database table, t is the number of records in the sample, and T is the size of the database table; and solving for N, given values of n, t, and T, by using a numerical method to find a value for N that satisfies the model, the found value for N being the estimate of the number of distinct values for the attribute in the database table.
References Cited (Backward Citations)
US5414834A
Cited
US5295256A
Cited
US5784017A
Cited
US5546575A
Cited
US5542089A
Cited
US5890148A
Cited
US5724573A
Cited
US5752025A
Cited
US5878426A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-06 | 2003-06-07 | 2003-12-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-06 | 2007-06-07 | 2007-12-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-06 | 2011-06-07 | 2011-12-07 | $7700.00 | Window Closed / Lapsed |