Patent US3069503A successfully refreshed from Google Patents.
Patent US4113701A successfully refreshed from Google Patents.
US5822751A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient multidimensional data aggregation operator implementation
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-12-16
•
Granted: 1998-10-13
•
Expires: 2016-12-16
Abstract
Abstract An efficient implementation of a multidimensional data aggregation operator that generates all aggregates and super-aggregates for all available values in a results set by first generating a minimal number of aggregates at the lowest possible system level using a minimal number of function calls, and second categorizing the aggregate function being applied and applying the aggregate function with the fewest possible function calls. The aggregates are generated from a union of roll-ups of the n attributes to the GROUP BY clause of the SELECT statement. The number of roll-ups are minimized by including a barrel shift of the attributes being rolled up. A scoreboard array of 2 n bits is updated during the roll-up and barrel shifting process to keep track of which roll-ups are complete and with are not yet complete. Generating super-aggregates is further optimized by identifying the type of aggregate function being applied and facilitating the most efficient application of the aggregate function. A lter -- super() function is implemented to facilitate the most efficient application of algebraic aggregate functions that require access to intermediate aggregate data that heretofore was not available to any algebraic aggregation operator.
Inventors
- 👤 Jim Gray
- 👤 Donald C. Reichart
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 19:34
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
117 words
A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising: identifying a roll-up string of attributes from said results set; generating at least one aggregate from said roll-up string by way of a minimum union of roll-up operator calls based on a barrel shift of said roll-up string; saving said at least one aggregate in said data cube; and generating at least one super-aggregate from said at least one aggregate by way of a minimum number of aggregation function calls dictated by an aggregation function classification selected from a group of aggregation categories consisting of: distributive, algebraic, and holistic.
Claim 2
Dependent Claim
117 words
A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising: identifying a roll-up string of attributes from said results set; generating at least one aggregate from said roll-up string by way of a minimum union of roll-up operator calls based on a barrel shift of said roll-up string; saving said at least one aggregate in said data cube; and generating at least one super-aggregate from said at least one aggregate by way of a minimum number of aggregation function calls dictated by an aggregation function classification selected from a group of aggregation categories consisting of: distributive, algebraic, and holistic.
Claim 3
Independent Claim
45 words
A method according to claim I wherein said step of generating at least one aggregate includes: executing a roll-up operation on said roll-up string; executing said barrel shift of said roll-up string; and executing a roll-up operation on said barrel shift of said roll-up string.
Claim 4
Dependent Claim
57 words
A method according to claim 2 including: maintaining a scoreboard array of one scoreboard bit entry for each roll-up aggregate on said roll-up string; examining said scoreboard array to determine when a complete set of said at least one aggregate exists; and executing a roll-up operation on an attribute string associated with each unset scoreboard bit entry.
Claim 5
Dependent Claim
80 words
A method according to claim 3 including: translating a base 10 scoreboard bit entry position in said scoreboard array to a base 2 equivalent; and identifying said attribute string associated with said base 10 scoreboard bit entry position by way of said base 2 equivalent wherein a first binary value indicates a presence of an attribute in said attribute string and a second binary setting opposite said first binary value indicates an absence of an attribute in said attribute string.
Claim 6
Dependent Claim
18 words
A computer-readable storage device containing instructions for controlling a computer system to perform the steps of claim 4.
Claim 7
Dependent Claim
61 words
A method according to claim 1 wherein said step of generating at least one super-aggregate includes: identifying an aggregate function as an algebraic aggregate function; assigning a handle to each value presently in said data cube; and executing at least one iteration of said algebraic aggregate function to fold each of said at least one sub-aggregate into at least one super-aggregate.
Claim 8
Dependent Claim
133 words
A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising: generating at least one aggregate from said results set by way of a minimum union of roll-up operator calls on a barrel shift of an attribute set; saving said at least one aggregate in said data cube; and categorizing an applicable aggregation function according to a group of aggregation categories consisting of: distributive, algebraic, and holistic; assigning a handle to each value presently in said data cube that is subject to aggregation by an algebraic aggregation function; and generating at least one super-aggregate from said at least one sub-aggregate by way of a minimum number of aggregation function calls dictated by said aggregation function category.
Claim 9
Dependent Claim
133 words
A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising: generating at least one aggregate from said results set by way of a minimum union of roll-up operator calls on a barrel shift of an attribute set; saving said at least one aggregate in said data cube; and categorizing an applicable aggregation function according to a group of aggregation categories consisting of: distributive, algebraic, and holistic; assigning a handle to each value presently in said data cube that is subject to aggregation by an algebraic aggregation function; and generating at least one super-aggregate from said at least one sub-aggregate by way of a minimum number of aggregation function calls dictated by said aggregation function category.
Claim 10
Dependent Claim
18 words
A computer-readable storage device containing instructions for controlling a computer system to perform the steps of claim 7.
Claim 11
Dependent Claim
49 words
A method according to claim 7 wherein said step of generating at least one aggregate includes: executing a roll-up operation on said attribute set from said results set; executing said barrel shift of said attribute set; and executing a roll-up operation on said barrel shift of said attribute set.
Claim 12
Dependent Claim
57 words
A method according to claim 9 including: maintaining a scoreboard array of one scoreboard bit entry for each roll-up aggregate on said attribute set; examining said scoreboard array to determine when a complete set of said at least one aggregate exists; and executing a roll-up operation on an attribute string associated with each unset scoreboard bit entry.
Claim 13
Dependent Claim
52 words
A method according to claim 7 wherein said step of generating at least one super-aggregate includes: executing, in response to said aggregate function being a said algebraic aggregate function, at least one iteration of said algebraic aggregate function to fold each of said at least one sub-aggregate into at least one super-aggregate.
Claim 14
Dependent Claim
161 words
A computer readable medium containing computer executable instructions to perform a method comprising: determine a minimum plurality of aggregate operations required for n attributes of an n-dimensional results set; executing said minimum plurality of aggregate operations in a manner comprising; executing an aggregate roll-up operation on said n attributes; repeatedly generating a unique barrel shift sub-set string of said n attributes and executing said aggregate roll-up operation on said unique barrel shift sub-set string until no unique barrel shift set string of said n attributes exists; tracking completed aggregations of said aggregate roll-up operation in a scoreboard array; examining said scoreboard array to verify that a complete set of aggregates exists; executing a roll-up operation on an attribute string associated with each unset entry in said scoreboard array; and generating at least one super-aggregate from said complete set of sub-aggregates dictated by at least one aggregate function selected from a group of aggregate function categories consisting of: distributive, algebraic, and holistic.
Claim 15
Dependent Claim
161 words
A computer readable medium containing computer executable instructions to perform a method comprising: determine a minimum plurality of aggregate operations required for n attributes of an n-dimensional results set; executing said minimum plurality of aggregate operations in a manner comprising; executing an aggregate roll-up operation on said n attributes; repeatedly generating a unique barrel shift sub-set string of said n attributes and executing said aggregate roll-up operation on said unique barrel shift sub-set string until no unique barrel shift set string of said n attributes exists; tracking completed aggregations of said aggregate roll-up operation in a scoreboard array; examining said scoreboard array to verify that a complete set of aggregates exists; executing a roll-up operation on an attribute string associated with each unset entry in said scoreboard array; and generating at least one super-aggregate from said complete set of sub-aggregates dictated by at least one aggregate function selected from a group of aggregate function categories consisting of: distributive, algebraic, and holistic.
Claim 16
Dependent Claim
61 words
A method according to claim 12 wherein said step of generating at least one super-aggregate includes: identifying an aggregate function as an algebraic aggregate function; assigning a handle to each value presently in said data cube; and executing at least one iteration of said algebraic aggregate function to fold each of said at least one sub-aggregate into at least one super-aggregate.
Claim 17
Dependent Claim
18 words
A computer-readable storage device containing instructions for controlling a computer system to perform the steps of claim 13.
References Cited (Backward Citations)
EP0372185A2
Cited
US5359724A
Cited
US5412804A
Cited
US5713020A
Cited
US5598559A
Cited
US5511190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-12 | 2002-04-13 | 2002-10-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-12 | 2006-04-13 | 2006-10-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-12 | 2010-04-13 | 2010-10-13 | $7700.00 | Window Closed / Lapsed |