Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-27
2004-07-13
Pardo, Thuy N. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06763357
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 multidimensional 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: 5553234 (1996-09-01), Cotner et al.
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5946688 (1999-08-01), Roberts
patent: 6128624 (2000-10-01), Papierniak et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6279033 (2001-08-01), Selvarajan et al.
patent: 6289352 (2001-09-01), Proctor
patent: 6308168 (2001-10-01), Dovich et al.
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: 6430565 (2002-08-01), Berger et al.
Dar et al., “Extending SQL with Generalized Transitive Closure”, IEEE, 1993, pp. 799-812.*
Markl et al., “Improving OLAP Performance by Multidimensional Hierarchical Clustering”, IEEE, Aug. 1999, pp. 165-177.*
Chen et al., “A Data-Warehouse/OLAP Framework for Scalable Telecommunication Tandem Traffic Analysis”, IEEE, Mar. 2000, pp. 201-210.*
Albrecht et al., “Management of Multidimensional Aggregates for Efficient Online Analytical Processing”, IEEE, 1999, pp. 156-164.*
Ross, K.A.,, et al., Complex Aggregation at Multiple Granularities, Int. Conf. on Extending Database Technology, pp. 263-277, 1998. [not able to obtain a copy].
Ross, K.A., et al., Fast Computation of Sparse Datacubes, Proc. Of the 23rdIntl. VLDB Conf., p. 116-125, 1997.
Srivastava, D., et al., Answering Queries with Aggregation Using Views, Proc. Of the 22ndInt. VLDB Conf., 1996.
Smith, J.R., et al., Dynamic Assembly of Views in Data Cubes, Proc. Of the 17thSym. On PODS, pp. 274-283, 1998.
Scheuermann, P., et al., WATCHMAN: A Data Warehouse Intelligent Manager, Proc. Of the 22ndInt. VLDB Conf., 1996.
Sarawagi, S., et al., Efficient Organization of Large Multidimensional Arrays, Proc. Of the 11thIntl. Conf. on Data Engg., 1994.
TMI technology papers available at http://www.applix.com/tm1/tm_tech.htm.
TMI technology papers available at http://www.applix.com/tm1/rescentr/tm1wppr.htm.
Ullman, J.D. Efficient Implementation of Data Cubes Via Materialized Views, The 2ndInt. Conf. on Knowledge Discovery and Data Mining, pp. 386-388, 1996.
The Analytical Processing Benchmark available at http://www.olapcouncil.org/research/bmarkco.htm.
APB benchmark performance results available at http://www.oracle.com/olap/html/bnchmark.html [not able to obtain a copy].
APB benchmark performance results available at http://www.hyperion.com/unix-hench.cfm [not able to obtain a copy].
S. Agarwal, et al., On the Computation of Multidimensional Aggregates, Proc. Of the 22ndInt. VLDB Conf., pp. 506-521, 1996.
Baralis, E., et al., Materialized View Selection in a Multidimensional Database, Proc. Of the 23rdInt. VLDB Conf., 1997.
Gray, J., et al., Data Cube: A Relational Aggregation Operator Generalizing GroupBy, Cross-Tab, and Sub-Totals, Proc. Of the 12thInt. Conf. On Data Engg., pp. 152-159, 1996.
Gupta, H., et al., Index Selection for OLAP, Proc. Of the 13thICDE, pp. 208-219, 1997.
Gupta, H., Selection of Views to Materialize in a Data Warehouse, Proc. Of the Sixth ICDT, pp. 98-112, 1997.
Harinarayanan, V., et al., Implementing Data Cubes Efficiently, Proc. ACM SIGMOD Int. Conf. On Management of Data, pp. 205-216, 1996.
Kotidis, Y., et al., An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees, Proc. ACM SIGMOD Int. Conf. On Management of Data, pp. 249-258, 1998.
Kotidis, Y., et al., DynaMat: A Dynamic View Management System for Data Warehouses, Proc. ACM SIGMOD Int. Conf. On Management of Data, pp. 371-382, 1999.
Roussopoulos, N., et al., Cubetree: Organization of and Bulk Updates on the Data Cube, Proc. ACM SIGMOD Int. Conf. On Management of Data, pp. 89-99, 1997.
Kimball, R., The Data Warehouse Toolkit, John & Wiley & Sons, 1996.
J. Patel et al., Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation, SIGMOD 1997, Proceedings ACM SIGMOD International Conference.
D. De Witt et al., “Client-Server Paradise,” Proceedings of the 20thVLDB Conference, Santiago, Chile, 1994.
“Opt++: An Object-Orient
Deshpande Prasad Manikarao
Naughton Jeffrey F.
Ramasamy Karthikeyan
Shukla Amit
Gates & Cooper LLP
NCR Corporation
Pardo Thuy N.
LandOfFree
Method for determining the computability of data for an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining the computability of data for an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining the computability of data for an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3255537