Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-27
2003-05-20
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06567804
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 the shared computation of user-defined metrics for an on-line analytical processing (OLAP) system that uses a relational database management system (RDBMS).
2. Description of Related Art
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. In OLAP systems, expressions and aggregates are often generated by user-defined metrics. Examples of such metrics include running averages of sales over vanous time windows, actual vs. forecast profit margins, and many others. Often, one metric is defined in terms of another, e.g., profit may be defined in terms of sales and various costs. Frequently, a single user query will request multiple metrics, and each metric may have many component sub-metrics. The result is a complex set of expressions and aggregates, which provide the potential for sharing and re-use during evaluation.
A naive way of executing these sets of expressions and aggregations is to consider each expression or aggregation in isolation, evaluating each one separately from all the others. In many cases, this naive approach is very inefficient, because the expressions and aggregations often share a lot of internal structure. Thus, there is a need in the art for improved techniques for evaluating expressions, in order to improve the performance of OLAP systems.
SUMMARY OF THE INVENTION
An On-Line Analytic Processing (OLAP) system computes complex expressions and aggregations in queries by re-using and sharing subparts of the expressions and aggregations. A dependency generation phase performed by the OLAP system identifies dependencies among metrics based on the expressions, aggregations, and other metrics used by the metrics. An access plan generation phase performed by the OLAP system generates an access plan based on the identified dependencies, wherein the access plan ensures that expressions, aggregations, and metrics are computed before they are needed, and that required values and intermediate results are passed up a tree structure of the access plan until they are used or consumed by some operator. An operator assignment phase performed by the OLAP system generates operators based on the access plan, and also generates project list expressions, aggregations to be computed in each operator, and input and output tuple types for each operator.
REFERENCES:
patent: 5553234 (1996-09-01), Cotner et al.
patent: 6167396 (2000-12-01), Lokken
patent: 6182061 (2001-01-01), Matsuzawa et al.
patent: 6275818 (2001-08-01), Subramanian et al.
patent: 6434544 (2002-08-01), Bakalash et al.
Goil et al. “A parallel scalable infrastructure for OLAP and data mining”, IEEE, IDEAS, 1999, pp. 178-186.*
Jurgens et al. “The R/sub a/*-tree: an improved R*-tree with materialized data for supporting range queries on OLAP-data”, IEEE, Database and Expert Systems Applications, 1998, pp. 186-191.*
Kabra et al. “OPT++: an object-oriented implementation for extensible database query optimization”, The VLDB Journal, Jan. 1999, pp. 55-78.*
Shukla et al. “Materialized View Selection for Multidimensional Datasets”, Proceedings of the 24th VLDB Conference, 1998, pp. 488-499.*
J. Patel et al., Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation, SIGMOD 1997, Proceedings ACM SIGMOD International Conference, pp. 1-12.
D. De Witt et al., “Client-Server Paradise,” Proceedings of the 20thVLDB Conference, Santiago, Chile, 1994 pp. 1-12.
“Opt++: An Object-Oriented Design for Extensible Database Query Optimization,” with David J. DeWitt, The VLDB Journal, vol. 8, Issue 1, Jan. 1999 pp. 55-78.
S. Dar et al., “Semantic Data Caching and Replacement,” Proc. of the 22ndInt. VLDB Conf., 1996 pp. 330-341.
P.M. Desphpande et al., “Caching Multidimensional Queries Using Chunks,” Proc. of ACM SIGMOD Int. Conf. on Mgmt. of Data, 1998, 259-270.
A. Shukla et al., “Storage Estimation for Multidimensional Aggregates in the Prescence of Hierarchies,” Proc. of the 22ndInt. VLDB Conf., 1996, 522-531.
A. Shukla et al., “Materialized View Selection for Multidimensional Datasets,” Proc. of the 24thInt. VLDB conf., 1998, 488-499.
Y. Zhao et al., “An Array-Based Algorithm for Simultaneous Multidimensional Aggregates,” Proc. ACM SIGMOD Int. Conf. on Management of Data, 1997, 159-170.
N. Pendse, R. Creeth, The OLAP Report available at http://www.olapreport.com Feb. 26, 2001.
Deshpande Prasad Manikarao
Naughton Jeffrey F.
Ramasamy Karthikeyan
Shukla Amit
Breene John
Gates & Cooper
Lewis Cheryl
NCR Corporation
LandOfFree
Shared computation of user-defined metrics in an on-line... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shared computation of user-defined metrics in an on-line..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared computation of user-defined metrics in an on-line... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3011651