Optimizing Multiple Dimensional Queries Simultaneously in Multidimensional Databases.
Weifa Liang, Maria E. Orlowska, Jeffrey Xu Yu:
Optimizing Multiple Dimensional Queries Simultaneously in Multidimensional Databases.
VLDB J. 8(3-4): 319-338(2000)@article{DBLP:journals/vldb/LiangOY00,
author = {Weifa Liang and
Maria E. Orlowska and
Jeffrey Xu Yu},
title = {Optimizing Multiple Dimensional Queries Simultaneously in Multidimensional
Databases},
journal = {VLDB J.},
volume = {8},
number = {3-4},
year = {2000},
pages = {319-338},
ee = {db/journals/vldb/LiangOY00.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Some significant progress related to multidimensional data analysis has been achieved in the past few years, including the design of fast algorithms for computing datacubes, selecting some precomputed group-bys to materialize, and designing efficient storage structures for multidimensional data.
However, little work has been carried out on multidimensional query optimization issues.
Particularly the response time (or evaluation cost) for answering several related dimensional queries simultaneously is crucial to the OLAP applications.
Recently, Zhao et al. first exploited this problem by presenting three heuristic algorithms.
In this paper we first consider in detail two cases of the problem in which all the queries are either hash-based star joins or index-based star joins only.
In the case of the hash-based star join, we devise a polynomial approximation algorithm which delivers a plan whose evaluation cost is O(nepsilon) times the optimal, where n is the number of queries and epsilon is a fixed constant with 0 < epsilon <= 1.
We also present an exponential algorithm which delivers a plan with the optimal evaluation cost. In the case of the index-based star join, we present a heuristic algorithm which delivers a plan whose evaluation cost is n times the optimal, and an exponential algorithm which delivers a plan with the optimal evaluation cost.
We then consider a general case in which both hash-based star-join and index-based star-join queries are included.
For this case, we give a possible improvement on the work of Zhao et al., based on an analysis of their solutions.
We also develop another heuristic and an exact algorithm for the problem.
We finally conduct a performance study by implementing our algorithms.
The experimental results demonstrate that the solutions delivered for the restricted cases are always within two times of the optimal, which confirms our theoretical upper bounds.
Actually these experiments produce much better results than our theoretical estimates.
To the best of our knowledge, this is the only development of polynomial algorithms for the first two cases which are able to deliver plans with deterministic performance guarantees in terms of the qualities of the plans generated.
The previous approaches including that of [ZDNS98] may generate a feasible plan for the problem in these two cases, but they do not provide any performance guarantee, i.e., the plans generated by their algorithms can be arbitrarily far from the optimal one.
Key Words
Multiple dimensional query optimization - OLAP - MDDBs - Query modeling - Data warehousing
Copyright © 2000 by Springer, Berlin, Heidelberg.
Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or
direct commercial advantage, and that copies show this notice along with the full citation.
Citation Page
CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [AAD+96]
- Sameet Agarwal, Rakesh Agrawal, Prasad Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, Sunita Sarawagi:
On the Computation of Multidimensional Aggregates.
VLDB 1996: 506-521 BibTeX
- [AESY97]
- Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek:
Efficient View Maintenance at Data Warehouses.
SIGMOD Conference 1997: 417-427 BibTeX
- [BPT97]
- Elena Baralis, Stefano Paraboschi, Ernest Teniente:
Materialized Views Selection in a Multidimensional Database.
VLDB 1997: 156-165 BibTeX
- [BD99]
- ...
- [DANR96]
- ...
- [GT90]
- Harold N. Gabow, Robert Endre Tarjan:
Faster Scaling Algorithms for General Graph-Matching Problems.
J. ACM 38(4): 815-853(1991) BibTeX
- [GJ79]
- M. R. Garey, David S. Johnson:
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
- [GBLP95]
- Jim Gray, Adam Bosworth, Andrew Layman, Hamid Pirahesh:
Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total.
ICDE 1996: 152-159 BibTeX
- [GM95]
- Ashish Gupta, Inderpal Singh Mumick:
Maintenance of Materialized Views: Problems, Techniques, and Applications.
IEEE Data Eng. Bull. 18(2): 3-18(1995) BibTeX
- [GHRU97]
- Himanshu Gupta, Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman:
Index Selection for OLAP.
ICDE 1997: 208-219 BibTeX
- [Gupta97]
- Himanshu Gupta:
Selection of Views to Materialize in a Data Warehouse.
ICDT 1997: 98-112 BibTeX
- [HRU96]
- Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman:
Implementing Data Cubes Efficiently.
SIGMOD Conference 1996: 205-216 BibTeX
- [HZ96]
- Richard Hull, Gang Zhou:
A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches.
SIGMOD Conference 1996: 481-492 BibTeX
- [Kim96]
- Ralph Kimball:
The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses.
John Wiley 1996, ISBN 0-471-15337-0
BibTeX
- [Knuth93]
- ...
- [MS]
- ...
- [OQ97]
- Patrick E. O'Neil, Dallan Quass:
Improved Query Performance with Variant Indexes.
SIGMOD Conference 1997: 38-49 BibTeX
- [PS88]
- Jooseok Park, Arie Segev:
Using Common Subexpressions to Optimize Multiple Queries.
ICDE 1988: 311-319 BibTeX
- [RSC98]
- Kenneth A. Ross, Divesh Srivastava, Damianos Chatziantoniou:
Complex Aggregation at Multiple Granularities.
EDBT 1998: 263-277 BibTeX
- [RSS96]
- Kenneth A. Ross, Divesh Srivastava, S. Sudarshan:
Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time.
SIGMOD Conference 1996: 447-458 BibTeX
- [RS97]
- Kenneth A. Ross, Divesh Srivastava:
Fast Computation of Sparse Datacubes.
VLDB 1997: 116-125 BibTeX
- [SAG96]
- ...
- [S88]
- Timos K. Sellis:
Multiple-Query Optimization.
ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
- [SS94]
- Kyuseok Shim, Timos K. Sellis, Dana S. Nau:
Improvements on a Heuristic Algorithm for Multiple-Query Optimization.
Data Knowl. Eng. 12(2): 197-222(1994) BibTeX
- [Su96]
- Prakash Sundaresan:
Data Warehousing Features in Informix OnLine XPS (Abstract).
PDIS 1996: 288 BibTeX
- [YKL97]
- Jian Yang, Kamalakar Karlapalem, Qing Li:
Algorithms for Materialized View Design in Data Warehousing Environment.
VLDB 1997: 136-145 BibTeX
- [Zeli97]
- Alexander Zelikovsky:
A Series of Approximation Algorithms for the Acyclic Directed Steiner Tree Problem.
Algorithmica 18(1): 99-110(1997) BibTeX
- [ZDN97]
- Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton:
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates.
SIGMOD Conference 1997: 159-170 BibTeX
- [ZDNS98]
- Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton, Amit Shukla:
Simultaneous Optimization and Evaluation of Multiple Dimensional Queries.
SIGMOD Conference 1998: 271-282 BibTeX
- [ZGHW95]
- Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom:
View Maintenance in a Warehousing Environment.
SIGMOD Conference 1995: 316-327 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:38 2009