Efficient estimation of joint queries from multiple OLAP databases

ABSTRACT

Given an OLAP query expressed over multiple source OLAP databases, we study the problem of estimating the resulting OLAP target database. The problem arises when it is not possible to derive the result from a single database. The method we use is linear indirect estimation, commonly used for statistical estimation. We examine two obvious computational methods for computing such a target database, called the full cross-product (F) and preaggregation (P) methods. We study the accuracy and computational cost of these methods. While the F method provides a more accurate estimate, it is more expensive computationally than P. Our contribution is in proposing a third, new method, called the partial preaggregation method (PP), which is significantly less expensive than F, but just as accurate. We prove formally that the PP method yields the same results as the F method, and provide analytical and experimental results on the accuracy and computational benefits of the PP method.

REFERENCES

• 1: Rakesh Agrawal , Ashish Gupta , Sunita Sarawagi, Modeling Multidimensional Databases, Proceedings of the Thirteenth International Conference on Data Engineering, p.232-243, April 07-11, 1997
• 2: Francesco Buccafurri , Filippo Furfaro , Domenico Saccà, Estimating Range Queries Using Aggregate Data with Integrity Constraints: A Probabilistic Approach, Proceedings of the 8th International Conference on Database Theory, p.390-404, January 04-06, 2001
• 3: Chan, P. and Shoshani, A. 1981. SUBJECT: A directory driven system for organizing and accessing large statistical databases. In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB) (Cannes, France), C. Zaniolo and C. Delobel Eds. IEEE Computer Society Press, Los Alamitos, CA. 553--563.
• 4: Chand, N. and Alexander, C. H. 1996. Small area estimation with administrative records and continuous measurement. In Proceedings of the Survey Research Methods Section, Annual Meeting of the American Statistical Association (ASA) (Chicago, IL). 870--875.
• 5: Codd, E. F., Codd, S. B., and Salley, C. T. 1993. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. Tech. Rep., E.F. Codd and Associates.
• 6: Elliott, P., Cuzick, J., English, D., and Stern, R. 1996. Geographical and Environmental Epidemiology: Methods for Small-Area Studies. Oxford University Press, New York.
• 7: Christos Faloutsos , H. V. Jagadish , Nikolaos Sidiropoulos, Recovering Information from Summary Data, Proceedings of the 23rd International Conference on Very Large Data Bases, p.36-45, August 25-29, 1997
• 8: Ghosh, M. and Rao, J. N. K. 1994. Small area estimation: An appraisal. Statis. Sci. 9, 55--93.
• 9: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 10: Marc Gyssens , Laks V. S. Lakshmanan, A Foundation for Multi-dimensional Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.106-115, August 25-29, 1997
• 11: Hans-Joachim Lenz , Arie Shoshani, Summarizability in OLAP and Statistical Data Bases, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.132-143, August 11-13, 1997 [doi>10.1109/SSDM.1997.621175]
• 12: Francesco M. Malvestuto, A universal-scheme approach to statistical databases containing homogeneous summary tables, ACM Transactions on Database Systems (TODS), v.18 n.4, p.678-708, Dec. 1993 [doi>10.1145/169725.169712]
• 13: Wee-Keong Ng , Chinya V. Ravishankar, Information synthesis in statistical databases, Proceedings of the fourth international conference on Information and knowledge management, p.355-361, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221638]
• 14: Pfeffermann, D. 2002. Small area estimation-New developments and directions. Int. Statis. Revi. 70, 1, 125--143.
• 15: Pourabbas, E. and Shoshani, A. 2003. Answering joint queries from multiple aggregate OLAP databases. In Data Warehousing and Knowledge Discovery, 5th International Conference (DaWaK), Y. Kambayashi et al., Eds. Lecture Notes Notes in Computer Science vol. 2737. Springer Verlag. 24--34.
• 16: Rao, J. N. K. 2003. Small Area Estimation. John Wiley, New York.
• 17: RTI International. 2007. RTI webpage. http://www.rti.org/page.cfm?nav=497.
• 18: Schaible, W. L. 1996. Indirect estimators in U.S. federal programs, bureau of labor statistics. Lecture Notes Stat. 108, 1--212.
• 19: Arie Shoshani, OLAP and statistical databases: similarities and differences, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.185-196, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263682]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Management, Performance

Keywords:
OLAP, multiple summary databases, query estimation