 |
|
|
|
|
|
 Title: |
US5832475:
Database system and method employing data cube operator for group-by operations
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Gupta, Ashish; Menlo Park, CA
Sarawagi, Sunita; Berkeley, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-11-03
/ 1996-03-29
|
| Application Number: |
US1996000624283
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S4P4P1A;
|
| U.S. Class: |
Current:
707/002;
707/001;
707/003;
707/004;
707/007;
Original:
707/002;
707/007;
707/001;
707/003;
707/004;
|
| Field of Search: |
385/602,607
382/049
707/001,2,3,4
|
| Priority Number: |
| 1996-03-29 |
US1996000624283 |
|
| Abstract: |
Disclosed is a system and method for performing database queries including GROUP-BY operations, in which aggregate values for attributes are desired for distinct, partitioned subsets of tuples satisfying a query. A special case of the aggregation problem is addressed, employing a structure, called the data cube operator, which provides information useful for expediting execution of GROUP-BY operations in queries. Algorithms are provided for constructing the data cube by efficiently computing a collection of GROUP-BYs on the attributes of the relation. Decision support systems often require computation of multiple GROUP-BY operations on a given set of attributes, the GROUP-BYs being related in the sense that their attributes are subsets or supersets of each other. The invention extends hash-based and sort-based grouping methods with optimizations, including combining common operations across multiple GROUP-BYs and using pre-computed GROUP-BYs for computing other GROUP-BYs. An extension of the cube algorithms handles any given collection of aggregates.
|
| Attorney, Agent or Firm: |
Pintner, James C. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Coby, Frantz
|
| Maintenance Status: |
E2 Expired Check current status
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 69 claims |
What is claimed is:
1. A method, for execution by a database system, for performing GROUP-BY operations on a dataset of attributes, the method comprising the steps of:
- generating an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique;
- computing a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and
- computing a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the step of computing a first GROUP-BY operation on the first subset of the attributes.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 71 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G1998-609846
DERABS G1998-609846
|
| Other References: |
M. R. Garey and D. S. Johnson, Computers & Intractability, Chapter Appendix, pp. 208-209.
P. J. Haas, J. F. Naughton, S. Seshadri, and L. Stokes, Sampling-based Estimation of the Number of Distinct Values of an Attribute, In Proceedings of the 21st International Conference on Very Large Databases (VLDB), pp. 311-322, Zurich, Switzerland, Sep. 1995.
J. MacGregor, Smith, Judith S. Liebman, An O (n2) Heuristic Algorithm for the Directed Steiner Minimal Tree Problem, Appl. Math, Modelling, pp. 369-375, vol. 4, Oct. 1980.
(7 pages)
J. Gray, A. Bosworth, A. Layman, & H. Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-tabs and Sub-totals. Technical Report MSR-TR-95-22, Microsoft Research, Advance Technology Division, Microsoft Corporation, Redmond, Washington, Nov. 1995.
Goetz Graefe, Ann Linville, & Leonard D. Shapiro, Sort Versus Hash Revisited, IEEE Transactions on Knowledge and Data Engineering, vol. 6, No. 6, pp. 934-943, Dec. 1994.
(11 pages)
Cited by 2 patents
[ISI abstract]
X. Lin and L.M. Ni, Multicast Communication in Multicomputer Networks, In Proc. International Conference on Parallel Processing, pp. III-114-118, 1990.
Goetz Graefe, Query Evaluation Techniques for Large Databases, ACM Computing Surveys, 25 (2):73-170, Jun. 1993.
(98 pages)
Cited by 17 patents
[ISI abstract]
E. F. Codd, s. B. Codd, C. T. Salley, Providing OLAP (On-line Analytical Processing to User-Analysts: An IT Mandate, E. F. Codd & Associates.
C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorthms and Complexity, Chapter 11, pp. 247-254, 1982.
Gray et al, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Nov. 1995.
|
|
 Nominate this for the Gallery...
|
|
