US6424967B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for querying a cube forest data structure
Assignee: AT&T Inc
•
Filing: 1998-11-17
•
Granted: 2002-07-23
•
Expires: 2018-11-17
Abstract
Abstract A device and method is disclosed for using a data structure known as a cube forest for use in a batch-load-then-read-intensively system. The device and method significantly improve the time to execute a bit vector query. Hierarchically split cube forests provide a method for efficiently duplicating information, and can be optimized to reduce update and storage costs. Cube forests including hierarchically split cube forests are most appropriate for read-intensive, update-rarely-and-in-large-batches multidimensional applications in an off-the-shelf (low cost) hardware environment. A method and an apparatus for querying a cube forest for aggregates are disclosed herein.
Inventors
- 👤 Theodore Johnson
- 👤 Dennis Shasha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 20:31
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2264; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
188 words
A method for efficiently answering a query for a single aggregate of data stored on a computer and indexed by a cube forest comprising the steps of: a) inputting a query, including specifying the type of query by stating how far down a hierarchy a value of an attribute is specified; and b) generating a query plan by finding a path in a cube forest template that starts at a root, and includes a node for every attribute value specified in the query; wherein the path found in step b) represents the query plan; said method further including the step of transforming the path into a query plan that contains detailed instructions for a generic query plan executer; said method further including the steps of: c) beginning at a top of the path and walking to an end of the path; and d) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute value is specified in the query, the instruction is (dimension, attribute, value, single), otherwise the instruction is (dimension, attribute, *, sum).
Claim 2
Independent Claim
188 words
A method for efficiently answering a query for a single aggregate of data stored on a computer and indexed by a cube forest comprising the steps of: a) inputting a query, including specifying the type of query by stating how far down a hierarchy a value of an attribute is specified; and b) generating a query plan by finding a path in a cube forest template that starts at a root, and includes a node for every attribute value specified in the query; wherein the path found in step b) represents the query plan; said method further including the step of transforming the path into a query plan that contains detailed instructions for a generic query plan executer; said method further including the steps of: c) beginning at a top of the path and walking to an end of the path; and d) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute value is specified in the query, the instruction is (dimension, attribute, value, single), otherwise the instruction is (dimension, attribute, *, sum).
Claim 3
Dependent Claim
50 words
The method according to claim 1 , wherein the step b) of generating the query plan by finding a path further comprises selecting a shortest path if there are more than one path that starts at a root and includes a node for every attribute value specified in the query.
Claim 4
Dependent Claim
95 words
The method according to claim 1 , wherein the step b) of executing the query plan comprises the substeps of: (i) matching a superkey of an index with a maximal segment of the query plan, such that the maximal segment starts with a first key in the index's superkey; and (ii) summing, for each effective leaf that matches the values specified by the query plan segment, a result and returning said result, wherein if the query plan segment is a suffix of the query plan, then returning a stored aggregate, else making a recursive search.
Claim 5
Independent Claim
204 words
A method for querying a cube forest for a group-by aggregate comprising the steps of: a) specifying a type of query by stating (i) how far down a hierarchy a value of an attribute is specified in a query; and (ii) specifying how much further down a hierarchy an answer is grouped; and b) generating a query plan by finding a path in a cube forest template that starts at a root and includes a node for every attribute specified in the query; wherein the path found in step b) represents the query plan; said method further including the step of transforming the path into a query plan that contains detailed instructions for a generic query plan executer; said method further including the steps of: c) beginning at a top of the path and walking to an end of the path; and d) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute is specified in the query, the instruction is (dimension, attribute, value, single), else if the attribute is specified as a grouping attribute, the instruction is (dimension, attribute, *, groupby), otherwise the instruction is (dimension, attribute, *, sum).
Claim 6
Independent Claim
204 words
A method for querying a cube forest for a group-by aggregate comprising the steps of: a) specifying a type of query by stating (i) how far down a hierarchy a value of an attribute is specified in a query; and (ii) specifying how much further down a hierarchy an answer is grouped; and b) generating a query plan by finding a path in a cube forest template that starts at a root and includes a node for every attribute specified in the query; wherein the path found in step b) represents the query plan; said method further including the step of transforming the path into a query plan that contains detailed instructions for a generic query plan executer; said method further including the steps of: c) beginning at a top of the path and walking to an end of the path; and d) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute is specified in the query, the instruction is (dimension, attribute, value, single), else if the attribute is specified as a grouping attribute, the instruction is (dimension, attribute, *, groupby), otherwise the instruction is (dimension, attribute, *, sum).
Claim 7
Dependent Claim
49 words
The method according to claim 4 , wherein the step b) of generating the query plan by finding a path further comprises selecting a shortest path if there are more than one path that starts at a root and includes a node for every attribute specified in the query.
Claim 8
Dependent Claim
95 words
The method according to claim 4 , wherein the step b) of executing the query plan comprises the substeps of: (i) matching a superkey of an index with a maximal segment of the query plan, such that the maximal segment starts with a first key in the index's superkey; and (ii) summing, for each effective leaf that matches the values specified by the query plan segment, a result and returning said result, wherein if the query plan segment is a suffix of the query plan, then returning a stored aggregate, else making a recursive search.
Claim 9
Dependent Claim
18 words
The method according to claim 6 , further comprising the step of retrieving values for a group-by query.
Claim 10
Dependent Claim
45 words
The method according to claim 7 , wherein the step of retrieving values for a group-by query further comprises the step of creating a query plan according to the steps for creating a query plan for a single-value retrieval, except distinguishing between “single” and group-by.
Claim 11
Dependent Claim
28 words
The method according to claim 8 , further comprising the step of upon reaching a terminal effective leaf, determining which result aggregate the answer should be added to.
Claim 12
Dependent Claim
38 words
The method according to claim 4 , wherein range queries are performed according to the same steps above, except that high and low values are attached to attribute selections, and a range of the search is extended appropriately.
Claim 13
Independent Claim
201 words
A device for querying a cube forest for a single aggregate comprising: a) an input/output device specifying a type of query by stating how far down a hierarchy a value of an attribute is specified; and b) a processor coupled to the input/output device and generating a query plan by finding a path in a cube forest template that starts at a root, and includes a node for every attribute specified in the query; said processor to generate the query plan by finding a shortest path if there are more than one path that starts at a root and includes a node for every attribute specified in the query, wherein the path found represents the query plan said processor to transform the path into a query plan that contains detailed instructions for a generic query plan executer by: c) beginning at a top of the path and walking to an end of the path; and d) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute value is specified in the query, the instruction is (dimension, attribute, value, single), otherwise the instruction is (dimension, attribute, *, sum).
Claim 14
Independent Claim
201 words
A device for querying a cube forest for a single aggregate comprising: a) an input/output device specifying a type of query by stating how far down a hierarchy a value of an attribute is specified; and b) a processor coupled to the input/output device and generating a query plan by finding a path in a cube forest template that starts at a root, and includes a node for every attribute specified in the query; said processor to generate the query plan by finding a shortest path if there are more than one path that starts at a root and includes a node for every attribute specified in the query, wherein the path found represents the query plan said processor to transform the path into a query plan that contains detailed instructions for a generic query plan executer by: c) beginning at a top of the path and walking to an end of the path; and d) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute value is specified in the query, the instruction is (dimension, attribute, value, single), otherwise the instruction is (dimension, attribute, *, sum).
Claim 15
Dependent Claim
90 words
The device according to claim 11 , wherein the processor executes the query plan by: a) matching a superkey of an index with a maximal segment of the query plan, such that the maximal segment starts with a first key in the index's superkey; and b) summing, for each effective leaf that matches the values specified by the query plan segment, a result and returning said result, wherein if the query plan segment is a suffix of the query plan, then returning a stored aggregate, else making a recursive search.
Claim 16
Independent Claim
191 words
A device for querying a cube forest for a group-by aggregate comprising: a) an input/output device specifying a type of query by stating how far down a hierarchy a value of an attribute is specified; and b) a processor generating a query plan by finding a path in a cube forest template that starts at a root and includes a node for every attribute specified in the query, by finding a shortest path, if there are more than one path that starts at a root and includes a node for every attribute specified in the query, wherein the path found represents the query plan, and by transforming the path into a query plan that contains detailed instructions for a generic query plan executer according to the steps of: (i) beginning at a top of the path and walking to an end of the path; and (ii) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute is specified in the query, the instruction is (dimension , attribute, value, single), otherwise the instruction is (dimension, attribute, *, sum).
Claim 17
Independent Claim
191 words
A device for querying a cube forest for a group-by aggregate comprising: a) an input/output device specifying a type of query by stating how far down a hierarchy a value of an attribute is specified; and b) a processor generating a query plan by finding a path in a cube forest template that starts at a root and includes a node for every attribute specified in the query, by finding a shortest path, if there are more than one path that starts at a root and includes a node for every attribute specified in the query, wherein the path found represents the query plan, and by transforming the path into a query plan that contains detailed instructions for a generic query plan executer according to the steps of: (i) beginning at a top of the path and walking to an end of the path; and (ii) creating, for every node, an entry that specifies what to do at that node, including (dimension, attribute, value, and operation), wherein if the attribute is specified in the query, the instruction is (dimension , attribute, value, single), otherwise the instruction is (dimension, attribute, *, sum).
Claim 18
Dependent Claim
173 words
The device according to claim 13 , wherein the processor executes the query plan according to the steps of: a) matching a superkey of an index with a maximal segment of the query plan, such that the maximal segment starts with a first key in the index's superkey; b) summing, for each effective leaf that matches the values specified by the query plan segment, a result and returning said result, wherein if the query plan segment is a suffix of the query plan, then returning a stored aggregate, else making a recursive search; c) retrieving values for a group-by query by creating a query plan according to the steps for creating a query plan for a single-value retrieval, except distinguishing between “single” and group-by; and d) upon reaching a terminal effective leaf, determining which result aggregate an answer should be added to, wherein range queries are performed according to the same steps above, except that high and low values are attached to attribute selections, and a range of the search is extended appropriately.
References Cited (Backward Citations)
US5806060A
Cited
US5809212A
Cited
US5603024A
Cited
US5812840A
Cited
US5675785A
Cited
US5832475A
Cited
US5822751A
Cited
US5978788A
Cited
US6141655A
Cited
US5943677A
Cited
US6122628A
Cited
US6003036A
Cited
US6334125B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-07-22 | 2006-01-21 | 2006-07-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-07-22 | 2010-01-21 | 2010-07-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-07-22 | 2014-01-21 | 2014-07-23 | $7700.00 | Window Closed / Lapsed |