US6012064A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Maintaining a random sample of a relation in a database in the presence of updates to the relation
Assignee: Alcatel Lucent SAS
•
Filing: 1997-08-21
•
Granted: 2000-01-04
•
Expires: 2017-08-21
Abstract
Abstract Techniques for maintaining a random sample of a relation in a database in the presence of updates to the relation. The random sample of the relation is referred to as a "backing sample," and it is maintained in the presence of insert, modify and delete operations involving the relation. When a new tuple is inserted into the relation, a sample of the given tuple is added to the backing sample if the size of the backing sample is below an upper bound. Otherwise, a randomly-selected tuple of the backing sample is replaced with the new tuple if a sample of the new tuple must be inserted into the backing sample to maintain randomness or another characteristic. When a tuple in the relation is the subject of a modify operation, the backing sample is left unchanged if the modify operation does not affect an attribute of interest to an application which uses the backing sample. Otherwise, a value field in a sample of the tuple in the backing sample is updated. When a tuple is deleted from the relation, any sample of that tuple in the backing sample is removed. A new backing sample may be computed if this removal causes the size of the backing sample to fall below a prespecified lower bound. The backing sample can be of a size which is negligible in comparison to the relation, and need only be modified very infrequently. As a result, its overhead in terms of computation time and storage space is minimal.
Inventors
- 👤 Phillip B. Gibbons
- 👤 Yossi Matias
- 👤 Viswanath Poosala
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 06:34
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/284; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/954; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99944
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
103 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: adding at least one attribute value of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, if the size of the random sample is below the upper bound; and replacing a selected tuple of the random sample with the at least one attribute value of the given tuple if the size of the random sample is not below the upper bound.
Claim 2
Independent Claim
103 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: adding at least one attribute value of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, if the size of the random sample is below the upper bound; and replacing a selected tuple of the random sample with the at least one attribute value of the given tuple if the size of the random sample is not below the upper bound.
Claim 3
Dependent Claim
26 words
The method of claim 1 wherein the given tuple is a new tuple added to the relation as part of an insert operation of the update.
Claim 4
Dependent Claim
29 words
The method of claim 1 wherein the adding step includes adding an identifier of the given tuple along with the at least one attribute value of the given tuple.
Claim 5
Dependent Claim
16 words
The method of claim 1 wherein the update includes a modify operation on the given tuple.
Claim 6
Dependent Claim
45 words
The method of claim 4 further including the step of updating a value field of the given tuple in the random sample of the relation only if the modify operation affects an attribute of interest to an application utilizing the random sample of the relation.
Claim 7
Dependent Claim
15 words
The method of claim 1 wherein the update includes deleting a tuple from the relation.
Claim 8
Dependent Claim
25 words
The method of claim 6 further including the step of removing any attribute values of the deleted tuple from the random sample of the relation.
Claim 9
Dependent Claim
48 words
The method of claim 7 further including the step of computing a new random sample of the relation if the size of the previous random sample is less than the lower bound after the step of removing any attribute values of the deleted tuple from the random sample.
Claim 10
Dependent Claim
24 words
The method of claim 1 further including the step of storing the random sample of the relation in consecutive blocks of a disk-based memory.
Claim 11
Dependent Claim
39 words
The method of claim 1 further including the step of storing the random sample of the relation as one or more blocks of a memory such that storage therewith of information not associated with the random sample is reduced.
Claim 12
Independent Claim
119 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation; and a processor coupled to the memory and operative to add at least one attribute value of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, if the size of the random sample is below the upper bound, and to replace a selected tuple of the random sample with the at least one attribute value of the given tuple if the size of the random sample is not below the upper bound.
Claim 13
Independent Claim
119 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation; and a processor coupled to the memory and operative to add at least one attribute value of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, if the size of the random sample is below the upper bound, and to replace a selected tuple of the random sample with the at least one attribute value of the given tuple if the size of the random sample is not below the upper bound.
Claim 14
Dependent Claim
26 words
The apparatus of claim 11 wherein the given tuple is a new tuple added to the relation as part of an insert operation of the update.
Claim 15
Dependent Claim
34 words
The apparatus of claim 11 wherein the processor is operative to add an identifier of the given tuple to the random sample along with the at least one attribute value of the given tuple.
Claim 16
Dependent Claim
23 words
The apparatus of claim 11 wherein the processor is further operative to execute a modify operation of a given tuple in the relation.
Claim 17
Dependent Claim
47 words
The apparatus of claim 14 wherein the processor is further operative to update a value field in the given tuple in the random sample of the relation only if the modify operation affects an attribute of interest to an application utilizing the random sample of the relation.
Claim 18
Dependent Claim
18 words
The apparatus of claim 11 wherein the processor is further operative to delete a tuple from the relation.
Claim 19
Dependent Claim
27 words
The apparatus of claim 16 wherein the processor is further operative to remove any attribute values of the deleted tuple from the random sample of the relation.
Claim 20
Dependent Claim
54 words
The apparatus of claim 17 wherein the processor is further operative to compute a new random sample of the relation if the size of the previous random sample of the relation is less than the lower bound after the attribute values of the deleted tuple are removed from the random sample of the relation.
Claim 21
Dependent Claim
28 words
The apparatus of claim 11 wherein the memory is a disk-based memory, and the random sample of the relation is stored in consecutive blocks of the disk-based memory.
Claim 22
Dependent Claim
36 words
The apparatus of claim 11 wherein the random sample of the relation is stored in one or more blocks of the memory such that storage therewith of information not associated with the random sample is reduced.
Claim 23
Independent Claim
96 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: adding a sample of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, when the size of the random sample is below the upper bound; and replacing a tuple of the random sample, selected uniformly at random, with the given tuple when the size of the random sample is not below the upper bound.
Claim 24
Independent Claim
96 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: adding a sample of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, when the size of the random sample is below the upper bound; and replacing a tuple of the random sample, selected uniformly at random, with the given tuple when the size of the random sample is not below the upper bound.
Claim 25
Independent Claim
112 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation; and a processor coupled to the memory and operative to add a sample of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, when the size of the random sample is below the upper bound, and to replace a tuple of the random sample, selected uniformly at random, with the given tuple when the size of the random sample is not below the upper bound.
Claim 26
Independent Claim
112 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation; and a processor coupled to the memory and operative to add a sample of a given tuple, associated with an update to the relation, to the random sample of the relation wherein a size of the random sample is maintained between an upper bound and a lower bound, when the size of the random sample is below the upper bound, and to replace a tuple of the random sample, selected uniformly at random, with the given tuple when the size of the random sample is not below the upper bound.
Claim 27
Independent Claim
81 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: deleting one or more existing tuples of the random sample in response to an update to the relation, the size of the random sample having an upper bound associated therewith; and replacing a selected tuple of the random sample with a given tuple, associated with an update to the relation, whether or not the size of the random sample is below the upper bound.
Claim 28
Independent Claim
81 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: deleting one or more existing tuples of the random sample in response to an update to the relation, the size of the random sample having an upper bound associated therewith; and replacing a selected tuple of the random sample with a given tuple, associated with an update to the relation, whether or not the size of the random sample is below the upper bound.
Claim 29
Independent Claim
97 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation; and a processor coupled to the memory and operative to delete one or more existing tuples of the random sample in response to an update to the relation, the size of the random sample having an upper bound associated therewith, and to replace a selected tuple of the random sample with a given tuple, associated with an update to the relation, whether or not the size of the random sample is below the upper bound.
Claim 30
Independent Claim
97 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation; and a processor coupled to the memory and operative to delete one or more existing tuples of the random sample in response to an update to the relation, the size of the random sample having an upper bound associated therewith, and to replace a selected tuple of the random sample with a given tuple, associated with an update to the relation, whether or not the size of the random sample is below the upper bound.
Claim 31
Independent Claim
78 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: storing the random sample in one or more blocks of memory separate from the relation such that storage therewith of information not associated with the random sample is reduced; and updating the random sample in response to one or more updates to the relation, wherein a size of the random sample is maintained between an upper bound and a lower bound.
Claim 32
Independent Claim
78 words
A method of maintaining a random sample of a relation in a database, comprising the steps of: storing the random sample in one or more blocks of memory separate from the relation such that storage therewith of information not associated with the random sample is reduced; and updating the random sample in response to one or more updates to the relation, wherein a size of the random sample is maintained between an upper bound and a lower bound.
Claim 33
Independent Claim
94 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation and for storing the random sample in one or more blocks of memory separate from the relation such that storage of information with the random sample not associated therewith is reduced; and a processor coupled to the memory and operative to update the random sample in response to one or more updates to the relation, wherein a size of the random sample is maintained between an upper bound and a lower bound.
Claim 34
Independent Claim
94 words
An apparatus for use in maintaining a random sample of a relation in a database, comprising: a memory for storing the relation and for storing the random sample in one or more blocks of memory separate from the relation such that storage of information with the random sample not associated therewith is reduced; and a processor coupled to the memory and operative to update the random sample in response to one or more updates to the relation, wherein a size of the random sample is maintained between an upper bound and a lower bound.
References Cited (Backward Citations)
US4956774A
Cited
US5379422A
Cited
US5630120A
Cited
US5794229A
Cited
US5675786A
Cited
US5555191A
Cited
US5696964A
Cited
US5758338A
Cited
US5893090A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-03 | 2003-07-05 | 2004-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-03 | 2007-07-05 | 2008-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-03 | 2011-07-05 | 2012-01-04 | $7700.00 | Window Closed / Lapsed |