Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-27
2003-07-29
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S118000
Reexamination Certificate
active
06601062
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to an active cache approach to caching multi-dimensional data sets for an on-line analytical processing (OLAP) system that uses a relational database management system (RDBMS).
2. Description of Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found in the “Detailed Description of the Preferred Embodiment” in Section 9 entitled “References.” Each of these publications is incorporated by reference herein.)
On-Line Analytical Processing (OLAP) systems provide tools for analysis of multi-dimensional data. Most systems are built using a three-tier architecture, wherein the first or client tier provides a graphical user interface (GUI) or other application, the second or middle tier provides a multi-dimensional view of the data, and the third or server tier comprises a relational database management system (RDBMS) that stores the data.
Most queries in OLAP systems are complex and require the aggregation of large amounts of data. However, decision support applications in OLAP systems need to be interactive and demand fast response times. Different techniques to speed up queries have been studied and implemented, both in research and industrial systems. These include pre-computation of aggregates in the RDBMS, having specialized index structures, and caching in the middle tier.
The problem of pre-computing a cube has been studied in [AAD+96], [ZDN97], and [RS97]. [SDNR96] deals with the issue of the space required for pre-computation. Picking GROUP-BYs to pre-compute has been studied in [HRU96] and [SDN98]. [RKR97] and [KR98] consider the problem of efficient organization of the cube data.
In the field of caching, [SSV] presents replacement and admission schemes specific to warehousing. The problem of answering queries with aggregation using views has been studied extensively in [SDJL96]. [SLCJ98] presents a method for dynamically assembling views based on granular view elements which form the building blocks.
Semantic query caching for client-server systems has been studied in [DFJST]. A recent work on semantic caching is based on caching Multidimensional Range Fragments (MRFs), which correspond to semantic regions having a specific shape [KR99]. Each dimension in a MRF either covers the entire range on the dimension or is a point selection on the dimension.
Another kind of caching is chunk-based caching, which is a semantic caching method optimized for the domain of OLAP systems. Chunk-based caching was proposed in [DRSN98]. The motivation of chunk-based caching is to allow a query to take advantage of overlap with previous queries, even if the later queries are not totally contained in the previous queries.
Generally, these different caching techniques have focused on using cached results from a previous query as the answer to another query. This strategy is effective when the query stream exhibits a high degree of locality. Unfortunately, it misses the dramatic performance improvements obtainable when the answer to a query, while not immediately available in the cache, can be computed from data in the cache. The present invention considers answering queries by aggregating data in the cache.
SUMMARY OF THE INVENTION
The present invention discloses a method, apparatus, and article of manufacture for caching multi-dimensional data sets for an on-line analytical processing (OLAP) system. An “active cache” is used, wherein the cache can not only answer queries that match data stored in the cache, but can also answer queries that require aggregation or other computation of the data stored in the cache.
REFERENCES:
patent: 5794229 (1998-08-01), French et al.
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5905985 (1999-05-01), Malloy et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5918232 (1999-06-01), Pouschine et al.
patent: 5943677 (1999-08-01), Hicks
patent: 6003036 (1999-12-01), Martin
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6154746 (2000-11-01), Berchtold et al.
patent: 6275818 (2001-08-01), Subramanian et al.
patent: 6289352 (2001-09-01), Proctor
patent: 6317750 (2001-11-01), Tortolani et al.
patent: 6381605 (2002-04-01), Kothuri et al.
patent: 6424972 (2002-07-01), Berger et al.
patent: 6434544 (2002-08-01), Bakalash et al.
Deshpande et al. “Caching Multidimensional Queries Using Chunks”, Proc. of ACM SIGMOD Int. Conf. on Mgmt. of Data, 1998, pp. 259-270.*
DeWitt et al., “Client-Server Paradise,” Proceedings of the 20thVLDB Conference, 1994, pp. 1-12.
Kabra et al., “OPT++: an Object-Oriented Implementation for Extensible Database Query Optimization,” VLDB Journal, 1999, pp. 55-78.
S. Dar, M.J. Franklin, B.T. Jonsson, D. Srivastava, M. Tan, “Semantic Data Caching and Replacement,” Proc. of the 22ndInt. VLDB Conf., 1996, pp. 330-341.
P.M. Desphpande, K. Ramasamy, A. Shukla, J.F. Naughton, “Caching Multidimensional Queries Using Chunks,” Proc. of ACM SIGMOD Int. Conf. on Mgmt. of Data, 1998, 259-270.
A. Shukla, P.M. Deshpande, J.F. Naughton, J. Ramasamy, “Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies,” Proc. of the 22ndInt. VLDB Conf., 1996, 522-531.
A. Shukla, P.M. Deshpande, J.F. Naughton, “Materialized View Selection for Multidimensional Datasets,” Proc. of the 24thInt. VLDB Conf., 1998, 488-499.
Y. Zhao, P.M. Deshpande, J.F. Naughton, “An Array-Based Algorithm for Simultaneous Multidimensional Aggregates,” Proc. ACM SIGMOD Int. Conf. on Management of Data, 1997, 159-170.
Deshpande Prasad Manikarao
Naughton Jeffrey F.
Ramasamy Karthikeyan
Shukla Amit
Breene John
Gates & Cooper
Lewis Cheryl
NCR Corporation
LandOfFree
Active caching for multi-dimensional data sets in relational... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Active caching for multi-dimensional data sets in relational..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Active caching for multi-dimensional data sets in relational... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030837