Patent US6532458B1 successfully refreshed from Google Patents.
US6532458B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Sampling for database systems
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-03-15
•
Granted: 2003-03-11
•
Expires: 2019-03-15
Abstract
Abstract A database server supports weighted and unweighted sampling of records or tuples in accordance with desired sampling semantics such as with replacement (WR), without replacement (WoR), or independent coin flips (CF) semantics, for example. The database server may perform such sampling sequentially not only to sample non-materialized records, such as those produced as a stream by a pipeline in a query tree for example, but also to sample records, whether materialized or not, in a single pass. The database server also supports sampling over a join of two relations of records or tuples without requiring the computation of the full join and without requiring the materialization of both relations and/or indexes on the join attribute values of both relations.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Rajeev Motwani
- 👤 Vivek Narasayya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:11
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 70
Claim 1
Independent Claim
143 words
A method for obtaining a sample in a single sequential pass of a plurality of records in a database system, the method comprising the steps of: (a) identifying the plurality of records and sampling semantics; (b) select a sampling operator based on the sampling semantics wherein the sampling operator comprises a probability function that outputs a number of times an input tuple should be included in the sample to obtain a sample according to the sampling semantics; and (c) obtaining a sample from the identified plurality of records using the sampling operator by: (i) inputing each of the plurality of records the sampling operator; and (ii) determining a number of times the record should be included in the sample based on the output of the sample operator; and (iii) selectively outputting the record for inclusion in the sample the determined number of times.
Claim 2
Independent Claim
143 words
A method for obtaining a sample in a single sequential pass of a plurality of records in a database system, the method comprising the steps of: (a) identifying the plurality of records and sampling semantics; (b) select a sampling operator based on the sampling semantics wherein the sampling operator comprises a probability function that outputs a number of times an input tuple should be included in the sample to obtain a sample according to the sampling semantics; and (c) obtaining a sample from the identified plurality of records using the sampling operator by: (i) inputing each of the plurality of records the sampling operator; and (ii) determining a number of times the record should be included in the sample based on the output of the sample operator; and (iii) selectively outputting the record for inclusion in the sample the determined number of times.
Claim 3
Dependent Claim
21 words
The method of claim 1 , wherein the identified sampling semantics is with replacement, without replacement, or coin flip sampling semantics.
Claim 4
Dependent Claim
48 words
The method of claim 1 , wherein the identifying step (a) comprises the step of identifying a size of the sample to be obtained; and wherein the selecting step (b) comprises the step of selecting a sampling operator whose probability function is based on the identified sample size.
Claim 5
Dependent Claim
52 words
The method of claim 1 , wherein the identifying step (a) comprises the step of identifying a weight function to specify a weight for each record; and wherein the selecting step (b) comprises the step of selecting a sampling operator whose probability function is based on the specified weight of each record.
Claim 6
Dependent Claim
87 words
The method of claim 1 , wherein the obtaining step (c) comprises the steps of: (i) inputting one record from the plurality of records to the sampling operator in step (c)(i), (ii) selectively resetting one or more records of a reservoir to be the one record input to the sampling operator based on the output of the sampling operator in step (c)(ii), and (iii) repeating steps (c)(i) and (c)(ii) for other records of the plurality of records such that the records of the reservoir from the sample.
Claim 7
Dependent Claim
64 words
The method of claim 5 , wherein the selectively resetting step (c) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (i) with a probability based on a weight of the one record obtained in step (i) divided by a sum of weight(s) of record(s) that have been obtained for step (i).
Claim 8
Dependent Claim
55 words
The method of claim 5 , wherein the selectively resetting step (c) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (i) based on a probability a number of time(s) equal in number to the weight of the one record obtained in step (i).
Claim 9
Dependent Claim
57 words
The method of claim 5 , wherein the selectively resetting step (c) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (i) with a probability based on a number of records in the reservoir divided by a sum of record(s) evaluated for reset in the reservoir.
Claim 10
Dependent Claim
25 words
The method of claim 1 , wherein at least one record obtained in step (a) may be output more than one time for step (c).
Claim 11
Dependent Claim
26 words
The method of claim 9 , wherein the plurality of records are a relation produced as a stream of records as a result of a query.
Claim 12
Dependent Claim
24 words
The method of claim 9 , wherein the plurality of records are materialized as a base relation in a database of the database system.
Claim 13
Dependent Claim
48 words
The method of claim 1 , wherein the selectively outputting step (c)(iii) comprises the steps of (i) determining a random number based on the probability such that the random number is greater than or equal to zero; and (ii) outputting the one record the determined number of times.
Claim 14
Dependent Claim
23 words
The method of claim 1 , wherein the sampling operator determines a random number from a binomial distribution based on the probability function.
Claim 15
Dependent Claim
38 words
The method of claim 1 , wherein the sampling operator determines a random number such that the random number is less than or equal to a number of record(s) remaining to be output for inclusion in the sample.
Claim 16
Dependent Claim
42 words
The method of claim 1 , wherein the step of the sampling operator determines a random number based on a probability based on a number of record(s) of the plurality of records to be evaluated for output for inclusion in the sample.
Claim 17
Dependent Claim
34 words
The method of claim 1 , wherein the selectively outputting step (c)(iii) comprises the step of selectively outputting the one record one or more times based on a weight specified for the one record.
Claim 18
Dependent Claim
54 words
The method of claim 1 , wherein the determining step (c)(ii) comprises the step of determining a random number based on a probability based on a weight of the one record divided by a sum of weight(s) of record(s) of the plurality of records to be evaluated for output for inclusion in the sample.
Claim 19
Dependent Claim
39 words
The method of claim 1 , wherein the selectively outputting step (c)(iii) comprises the step of selectively outputting the one record based on a probability a number of time(s) equal in number to a weight of the one record.
Claim 20
Dependent Claim
51 words
The method of claim 18 , wherein the selectively outputting step comprises the step of outputting the one record with a probability based on a number of record(s) remaining to be output for the sample divided by a number of possible record(s) that may be output for inclusion in the sample.
Claim 21
Dependent Claim
36 words
The method of claim 1 , wherein the determining step (c)(ii) comprises the step of determining a random number such that the random number is less than or equal to a weight of the one record.
Claim 22
Dependent Claim
31 words
The method of claim 1 , wherein the determining step (c)(ii) comprises the step of determining random number based on a probability based on a fraction of the plurality of records.
Claim 23
Dependent Claim
98 words
A computer readable medium having computer-executable instructions for performing a sequential sampling of records in one pass, the computer-executable instructions for performing the steps of: (a) obtaining one record from a plurality of records; (b) selectively outputting the one record obtained in step (a) one or more times based on a probability; and (c) repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).
Claim 24
Dependent Claim
98 words
A computer readable medium having computer-executable instructions for performing a sequential sampling of records in one pass, the computer-executable instructions for performing the steps of: (a) obtaining one record from a plurality of records; (b) selectively outputting the one record obtained in step (a) one or more times based on a probability; and (c) repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).
Claim 25
Dependent Claim
28 words
The computer readable medium of claim 22 , wherein the plurality of records are a relation produced as a stream of records as a result of a query.
Claim 26
Dependent Claim
26 words
The computer readable medium of claim 22 , wherein the plurality of records are materialized as a base relation in a database of the database system.
Claim 27
Dependent Claim
51 words
The computer readable medium of claim 22 , wherein the selectively outputting step (b) comprises the steps of: (i) determining a random number based on the probability such that the random number is greater than or equal to zero, and (ii) outputting the one record the determined random number of times.
Claim 28
Dependent Claim
29 words
The computer readable medium of claim 25 , wherein the determining step (b)(i) comprises the step of determining the random number from a binomial distribution based on the probability.
Claim 29
Dependent Claim
43 words
The computer readable medium of claim 25 , wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a number of record(s) remaining to be output for the sample.
Claim 30
Dependent Claim
44 words
The computer readable medium of claim 25 , wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a number of record(s) of the plurality of records to be evaluated for output for step (b).
Claim 31
Dependent Claim
54 words
The computer readable medium of claim 25 , wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a weight of the one record divided by a sum of weight(s) of record(s) of the plurality of records to be evaluated for output for step (b).
Claim 32
Dependent Claim
38 words
The computer readable medium of claim 25 , wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a weight of the one record.
Claim 33
Dependent Claim
34 words
The computer readable medium of claim 25 , wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a fraction of the plurality of records.
Claim 34
Dependent Claim
36 words
The computer readable medium of claim 22 , wherein the selectively outputting step (b) comprises the step of selectively outputting the one record one or more times based on a weight specified for the one record.
Claim 35
Dependent Claim
41 words
The computer readable medium of claim 22 , wherein the selectively outputting step (b) comprises the step of selectively outputting the one record based on a probability a number of time(s) equal in number to the weight of the one record.
Claim 36
Dependent Claim
51 words
The computer readable medium of claim 33 , wherein the selectively outputting step comprises the step of outputting the one record with a probability based on a number of record(s) remaining to be output for the sample divided by a number of possible record(s) that may be output for step (b).
Claim 37
Dependent Claim
29 words
The computer readable medium of claim 22 , wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.
Claim 38
Dependent Claim
111 words
A computer readable medium having computer-executable instructions for performing a sequential sampling of records in one pass, the computer-executable instructions for performing the steps of: (a) obtaining one record from a plurality of records; (b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and (c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).
Claim 39
Dependent Claim
111 words
A computer readable medium having computer-executable instructions for performing a sequential sampling of records in one pass, the computer-executable instructions for performing the steps of: (a) obtaining one record from a plurality of records; (b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and (c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).
Claim 40
Dependent Claim
38 words
The computer readable medium of claim 36 , wherein the selectively resetting step (b) comprises the step of selectively resetting each record of the reservoir to be the one record obtained in step (a) based on a probability.
Claim 41
Dependent Claim
52 words
The computer readable medium of claim 36 , wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a number of record(s) that have been obtained for step (a).
Claim 42
Dependent Claim
48 words
The computer readable medium of claim 36 , wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) based on a weight of the one record obtained in step (a).
Claim 43
Dependent Claim
66 words
The computer readable medium of claim 36 , wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a weight of the one record obtained in step (a) divided by a sum of weight(s) of record(s) that have been obtained for step (a).
Claim 44
Dependent Claim
57 words
The computer readable medium of claim 36 , wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) based on a probability a number of time(s) equal in number to the weight of the one record obtained in step (a).
Claim 45
Dependent Claim
59 words
The computer readable medium of claim 36 , wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) with a probability based on a number of records in the reservoir divided by a sum of record(s) evaluated for reset in the reservoir.
Claim 46
Dependent Claim
29 words
The computer readable medium of claim 36 , wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.
Claim 47
Dependent Claim
103 words
A database system for performing a sequential sampling of records in one pass in the database system, the database system comprising: means for performing the step of (a) obtaining one record from a plurality of records; means for performing the step of (b) selectively outputting the one record one or more times based on a probability; and means for repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).
Claim 48
Dependent Claim
103 words
A database system for performing a sequential sampling of records in one pass in the database system, the database system comprising: means for performing the step of (a) obtaining one record from a plurality of records; means for performing the step of (b) selectively outputting the one record one or more times based on a probability; and means for repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).
Claim 49
Dependent Claim
27 words
The database system of claim 44 , wherein the plurality of records are a relation produced as a stream of records as a result of a query.
Claim 50
Dependent Claim
25 words
The database system of claim 44 , wherein the plurality of records are materialized as a base relation in a database of the database system.
Claim 51
Dependent Claim
50 words
The database system of claim 44 , wherein the selectively outputting step (b) comprises the steps of: (i) determining a random number based on the probability such that the random number is greater than or equal to zero, and (ii) outputting the one record the determined random number of times.
Claim 52
Dependent Claim
28 words
The database system of claim 47 , wherein the determining step (b)(i) comprises the step of determining the random number from a binomial distribution based on the probability.
Claim 53
Dependent Claim
42 words
The database system of claim 47 , wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a number of record(s) remaining to be output for the sample.
Claim 54
Dependent Claim
43 words
The database system of claim 47 , wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a number of record(s) of the plurality of records to be evaluated for output for step (b).
Claim 55
Dependent Claim
35 words
The database system of claim 47 , wherein the selectively outputting step (b) comprises the step of selectively outputting the one record one or more times based on a weight specified for the one record.
Claim 56
Dependent Claim
53 words
The database system of claim 47 , wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a weight of the one record divided by a sum of weight(s) of record(s) of the plurality of records to be evaluated for output for step (b).
Claim 57
Dependent Claim
37 words
The database system of claim 47 , wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a weight of the one record.
Claim 58
Dependent Claim
33 words
The database system of claim 47 , wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a fraction of the plurality of records.
Claim 59
Dependent Claim
40 words
The database system, of claim 44 , wherein the selectively outputting step (b) comprises the step of selectively outputting the one record based on a probability a number of time(s) equal in number to the weight of the one record.
Claim 60
Dependent Claim
50 words
The database system of claim 55 , wherein the selectively outputting step comprises the step of outputting the one record with a probability based on a number of record(s) remaining to be output for the sample divided by a number of possible record(s) that may be output for step (b).
Claim 61
Dependent Claim
28 words
The database system of claim 44 , wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.
Claim 62
Dependent Claim
125 words
A database system for performing a sequential sampling of records in one pass in the database system, the database system comprising: means for performing the step of (a) obtaining one record from a plurality of records; means for performing the step of (b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and means for performing the step of (c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).
Claim 63
Dependent Claim
125 words
A database system for performing a sequential sampling of records in one pass in the database system, the database system comprising: means for performing the step of (a) obtaining one record from a plurality of records; means for performing the step of (b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and means for performing the step of (c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).
Claim 64
Dependent Claim
37 words
The database system of claim 58 , wherein the selectively resetting step (b) comprises the step of selectively resetting each record of the reservoir to be the one record obtained in step (a) based on a probability.
Claim 65
Dependent Claim
51 words
The database system of claim 58 , wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a number of record(s) that have been obtained for step (a).
Claim 66
Dependent Claim
47 words
The database system of claim 58 , wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) based on a weight of the one record obtained in step (a).
Claim 67
Dependent Claim
65 words
The database system of claim 58 , wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a weight of the one record obtained in step (a) divided by a sum of weight(s) of record(s) that have been obtained for step (a).
Claim 68
Dependent Claim
56 words
The database system of claim 58 , wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) based on a probability a number of time(s) equal in number to the weight of the one record obtained in step (a).
Claim 69
Dependent Claim
58 words
The database system of claim 58 , wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) with a probability based on a number of records in the reservoir divided by a sum of record(s) evaluated for reset in the reservoir.
Claim 70
Dependent Claim
28 words
The database system of claim 58 , wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.
References Cited (Backward Citations)
US5335345A
Cited
US5270957A
Cited
US5675786A
Cited
US5701460A
Cited
US6295533B2
Cited
US6012064A
Cited
US6278989B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-03-10 | 2006-09-09 | 2007-03-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-10 | 2010-09-09 | 2011-03-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-10 | 2014-09-09 | 2015-03-11 | $7700.00 | Window Closed / Lapsed |