Patent US6519604B1 successfully refreshed from Google Patents.
US6519604B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Approximate querying method for databases with multiple grouping attributes
Assignee: Nokia of America Corp
•
Filing: 2000-07-19
•
Granted: 2003-02-11
•
Expires: 2020-07-19
Abstract
Abstract An approximate querying method comprising grouping tuples within a database according to grouping attributes, determining how many tuples are needed to represent each group, selecting the tuples from a corresponding group to create a database sample, and querying the database sample. The database sample yields statistically unbiased answers when queried. The sample may be created and maintained without a priori knowledge of the data distribution within the database or the queries to be performed.
Inventors
- 👤 Swarup Acharya
- 👤 Phillip B. Gibbons
- 👤 Viswanath Poosala
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 13:17
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/99933; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
71 words
A method for deriving a database sample comprising the steps of selecting grouping attributes within a relational database having tuples; grouping said tuples based on said grouping attributes to derive sub groups; applying a function to determine a number of tuples for each of said sub groups; and selecting a database sample comprising tuples according to said number of tuples for each of said sub groups from a corresponding sub group.
Claim 2
Independent Claim
71 words
A method for deriving a database sample comprising the steps of selecting grouping attributes within a relational database having tuples; grouping said tuples based on said grouping attributes to derive sub groups; applying a function to determine a number of tuples for each of said sub groups; and selecting a database sample comprising tuples according to said number of tuples for each of said sub groups from a corresponding sub group.
Claim 3
Dependent Claim
24 words
The method of claim 1 , wherein said step of selecting grouping attributes comprises: selecting a plurality of grouping attributes within said relational database.
Claim 4
Dependent Claim
31 words
The method of claim 1 , wherein said grouping step comprises: grouping said tuples on one or more subsets of said grouping attributes including no groupings to derive said sub groups.
Claim 5
Dependent Claim
29 words
The method of claim 1 , wherein said grouping step comprises: grouping said tuples on every subset of said grouping attributes including no groupings to derive said sub groups.
Claim 6
Dependent Claim
148 words
The method of claim 4 , wherein said function in said applying step comprises: X max T ⊆ G s g , T ∑ j ∈ G ′ max T ⊆ G s j , T ; where s g , T = X m T · n g n h ; and where X is a total sample size, G represents said grouping attributes, T represents one of said subsets within said grouping attributes G, m T is a number of non-empty groups under a corresponding one of said subsets T, G′ represents all non-empty groups under said grouping attributes G, n g is a number of tuples in a corresponding one of said sub groups g in G′ of a group h under the grouping T, and n h is a number of all tuples in the group h.
Claim 7
Dependent Claim
26 words
The method of claim 1 , wherein said grouping step comprises: grouping said tuples based on a single set of attributes and on no attribute groupings.
Claim 8
Dependent Claim
119 words
The method of claim 6 , wherein said function in said applying step comprises: X max ( n g R , 1 m T ) ∑ j ∈ G ′ max ( n j R , 1 m T ) where X is a total sample size, T is said single set of attributes, m T is a number of non-empty groups under T, G′ represents all non-empty groups under said grouping T, g is one of said sub groups, n g is a number of tuples in a corresponding one of said sub groups g, and R is a number of all tuples in said relational database.
Claim 9
Dependent Claim
26 words
The method of claim 1 , wherein said grouping, applying, and selecting said database sample steps are performed in a single pass over said relational database.
Claim 10
Dependent Claim
30 words
The method of claim 8 , wherein said grouping, applying, and selecting said database sample steps are performed without a priori knowledge of a data distribution within said relational database.
Claim 11
Dependent Claim
33 words
The method of claim 8 , wherein said grouping, applying, and selecting said database sample steps are performed without a priori knowledge of a database query to be performed on said database sample.
Claim 12
Dependent Claim
22 words
The method of claim 1 , further comprising the step of: maintaining said database sample to reflect changes in said relational database.
Claim 13
Dependent Claim
25 words
The method of claim 11 , wherein said maintaining step comprises modifying said database sample in response to a new tuple in said relational database.
Claim 14
Dependent Claim
21 words
The method of claim 12 , wherein said selecting said database sample step and maintaining step comprise using reservoir sampling techniques.
Claim 15
Dependent Claim
42 words
The method of claim 1 , wherein said selecting said database sample step comprises: selecting a uniform random sample for each of said sub groups from a corresponding sub group according to said number of tuples for each of said sub groups.
Claim 16
Dependent Claim
32 words
The method of claim 1 , wherein said applying step comprises: applying said function to determine said number of tuples for each of said sub groups, said function weighting said grouping attributes.
Claim 17
Dependent Claim
15 words
The method of claim 1 , further comprising the step of: storing said database sample.
Claim 18
Dependent Claim
66 words
The method of claim 1 , wherein one of said selected grouping attributes is time; said grouping step comprises grouping said tuples based on intervals of time to derive sub groups; and said applying step comprises applying said function to determine a number of tuples for each of said sub groups such that tuples associated with more recent time intervals are sampled at a higher rate.
Claim 19
Independent Claim
74 words
A method for querying a database comprising the steps of: selecting grouping attributes within a relational database having tuples; grouping said tuples based on said grouping attributes to derive sub groups; applying a function to determine a number of tuples for each of said sub groups; selecting a database sample of tuples according to said number of tuples for each of said sub groups from a corresponding sub group; and querying said database sample.
Claim 20
Independent Claim
74 words
A method for querying a database comprising the steps of: selecting grouping attributes within a relational database having tuples; grouping said tuples based on said grouping attributes to derive sub groups; applying a function to determine a number of tuples for each of said sub groups; selecting a database sample of tuples according to said number of tuples for each of said sub groups from a corresponding sub group; and querying said database sample.
Claim 21
Dependent Claim
25 words
The method of claim 18 , wherein said selecting grouping attributes step comprises: selecting a plurality of grouping attributes within said relational database having tuples.
Claim 22
Dependent Claim
21 words
The method of claim 18 , further comprising the step of storing a scaling factor for each of said sub groups.
Claim 23
Dependent Claim
27 words
The method of claim 20 , further comprising the step of extrapolating results from said querying step utilizing said scaling factor for each of said sub groups.
Claim 24
Dependent Claim
26 words
The method of claim 21 , wherein said scaling factor for each of said sub groups is stored with each tuple within a corresponding sub group.
Claim 25
Dependent Claim
22 words
The method of claim 21 , wherein said scaling factor for each of said sub groups is stored in a scaling table.
Claim 26
Dependent Claim
28 words
The method of claim 18 , wherein said grouping step comprises: grouping said tuples on every subset of the grouping attributes including no groupings to derive sub groups.
Claim 27
Dependent Claim
26 words
The method of claim 18 , wherein said grouping step comprises: grouping said tuples based on a single set of attributes and on no attribute groupings.
Claim 28
Dependent Claim
15 words
The method of claim 18 , further comprising the step of: storing said database sample.
Claim 29
Dependent Claim
26 words
The method of claim 26 , wherein said querying step comprises: performing a plurality of queries with a plurality of groupings on said stored database sample.
Claim 30
Dependent Claim
32 words
The method of claim 18 , wherein said applying step comprises: applying said function to determine said number of tuples for each of said sub groups, said function weighting said grouping attributes.
Claim 31
Dependent Claim
26 words
The method of claim 18 , further comprising the step of: rewriting a query intended for said relational database for use with said relational database sample.
Claim 32
Dependent Claim
21 words
The method of claim 29 , wherein said rewriting step comprises: rewriting said query for use with an approximate querying system.
Claim 33
Dependent Claim
42 words
The method of claim 18 , wherein said selecting said database sample step comprises: selecting a uniform random sample for each of said sub groups from a corresponding sub group according to said number of tuples for each of said sub groups.
Claim 34
Dependent Claim
66 words
The method of claim 18 , wherein one of said selected grouping attributes is time; said grouping step comprises grouping said tuples based on intervals of time to derive sub groups; and said applying step comprises applying said function to determine a number of tuples for each of said sub groups such that tuples associated with more recent time intervals are sampled at a higher rate.
Claim 35
Independent Claim
87 words
A method for deriving a relational database sample comprising the steps of: selecting a uniform sample from a database having tuples; selecting grouping attributes within said database; grouping said tuples based on said grouping attributes to derive sub groups; applying a function to determine a number of tuples for each of said sub groups; and adding additional tuples to said uniform sample in accordance with said function, wherein said additional tuples for each of said sub groups are obtained from a corresponding sub group within said database.
Claim 36
Independent Claim
87 words
A method for deriving a relational database sample comprising the steps of: selecting a uniform sample from a database having tuples; selecting grouping attributes within said database; grouping said tuples based on said grouping attributes to derive sub groups; applying a function to determine a number of tuples for each of said sub groups; and adding additional tuples to said uniform sample in accordance with said function, wherein said additional tuples for each of said sub groups are obtained from a corresponding sub group within said database.
Claim 37
Dependent Claim
42 words
The method of claim 33 , wherein additional tuples are added when said number of tuples for a first one of said sub groups exceed a number of tuples selected from said first one of said sub groups for said uniform sample.
Claim 38
Independent Claim
71 words
A system for deriving a database sample comprising: a relational database having tuples and grouping attributes; grouping means for grouping said tuples based on said grouping attributes to derive sub groups; means for determining a number of tuples for each of said sub groups; and a selector for selecting a database sample comprising tuples according to said number of tuples for each of said sub groups from a corresponding sub group.
Claim 39
Independent Claim
71 words
A system for deriving a database sample comprising: a relational database having tuples and grouping attributes; grouping means for grouping said tuples based on said grouping attributes to derive sub groups; means for determining a number of tuples for each of said sub groups; and a selector for selecting a database sample comprising tuples according to said number of tuples for each of said sub groups from a corresponding sub group.
Claim 40
Dependent Claim
15 words
The system of claim 35 , further comprising: a table for storing said database sample.
Claim 41
Independent Claim
78 words
A system for querying a database comprising: a relational database having tuples and grouping attributes; grouping means for grouping said tuples based on said grouping attributes to derive sub groups; means for determining a number of tuples for each of said sub groups; a selector for selecting a database sample of tuples according to said number of tuples for each of said sub groups from a corresponding sub group; and a querying system for querying said database sample.
Claim 42
Independent Claim
78 words
A system for querying a database comprising: a relational database having tuples and grouping attributes; grouping means for grouping said tuples based on said grouping attributes to derive sub groups; means for determining a number of tuples for each of said sub groups; a selector for selecting a database sample of tuples according to said number of tuples for each of said sub groups from a corresponding sub group; and a querying system for querying said database sample.
Claim 43
Dependent Claim
15 words
The system of claim 37 , further comprising; a table for storing said database sample.
References Cited (Backward Citations)
US5335345A
Cited
US5878426A
Cited
US5890150A
Cited
US5893090A
Cited
US5999928A
Cited
US5987467A
Cited
US6012064A
Cited
US6282570B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-02-10 | 2006-08-12 | 2007-02-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-02-10 | 2010-08-12 | 2011-02-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-02-10 | 2014-08-12 | 2015-02-11 | $7700.00 | Window Closed / Lapsed |