Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-03-29
1998-11-03
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 7, 707 1, 707 3, 707 4, G06F 1730
Patent
active
058324755
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.
REFERENCES:
patent: 5280547 (1994-01-01), Mahoney
patent: 5412804 (1995-05-01), Krishma
patent: 5497486 (1996-03-01), Stoffo et al.
patent: 5537589 (1996-07-01), Dalal
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5548755 (1996-08-01), Leung et al.
patent: 5598559 (1997-01-01), Chaudhuri
patent: 5613109 (1997-03-01), Yamauchi et al.
patent: 5642502 (1997-06-01), Driscoll
patent: 5717915 (1998-02-01), Stoffo et al.
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.
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.
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.
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.
Agrawal Rakesh
Gupta Ashish
Sarawagi Sunita
Black Thomas G.
Coby Frantz
International Business Machines - Corporation
Pintner James C.
LandOfFree
Database system and method employing data cube operator for grou does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database system and method employing data cube operator for grou, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system and method employing data cube operator for grou will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-703936