Efficient integration and aggregation of historical information

ABSTRACT

Data warehouses support the analysis of historical data. This often involves aggregation over a period of time. Furthermore, data is typically incorporated in the warehouse in the increasing order of a time attribute, e.g., date of sale or time of a temperature measurement. In this paper we propose a framework to take advantage of this append only nature of updates due to a time attribute. The framework allows us to integrate large amounts of new data into the warehouse and generate historical summaries efficiently. Query and update costs are virtually independent from the extent of the data set in the time dimension, making our framework an attractive aggregation approach for append-only data streams. A specific instantiation of the general approach is developed for MOLAP data cubes, involving a new data structure for append-only arrays with pre-aggregated values. Our framework is applicable to point data and data with extent, e.g., hyper-rectangles.

REFERENCES

• 1: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 2: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel, Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.216-230, March 23-27, 1998
• 3: Gerth Stølting Brodal, Partially persistent data structures of bounded degree with constant update time, Nordic Journal of Computing, v.3 n.3, p.238-255, Fall 1996
• 4: Chee Yong Chan , Yannis E. Ioannidis, Hierarchical Prefix Cubes for Range-Sum Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.675-686, September 07-10, 1999
• 5: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 6: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 7: C. S. Jensen et al. Temporal Databases - Research and Practice, volume 1399 of LNCS, chapter The Consensus Glossary of Temporal Database Concepts, pages 367-405. Springer Verlag, 1998.
• 8: Steven Geffner , Divyakant Agrawal , Amr El Abbadi, The Dynamic Data Cube, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.237-253, March 27-31, 2000
• 9: Bruce C. Huang, Parallel Algorithms for Computing Temporal Aggregates, Proceedings of the 15th International Conference on Data Engineering, p.418, March 23-26, 1999
• 10: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 11: C. J. Hahn, S. G. Warren, and J. London. Edited synoptic cloud reports from ships and land stations over the globe, 1982-1991, 1996. Data available at http://cdiac.esd.ornl.gov/ftp/ndp026b.
• 12: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 13: W. H. Inmon. What is a data warehouse? White Paper, 2000. Available at http://www.billinmon.com/cif/edw/edw_content.html.
• 14: Nick Kline , Richard Thomas Snodgrass, Computing Temporal Aggregates, Proceedings of the Eleventh International Conference on Data Engineering, p.222-231, March 06-10, 1995
• 15: Anil Kumar , Vassilis J. Tsotras , Christos Faloutsos, Designing Access Methods for Bitemporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.1-20, January 1998 [doi>10.1109/69.667079]
• 16: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 17: Ines Fernando Vega Lopez, Scalable Algorithms for Large Temporal Aggregation, Proceedings of the 16th International Conference on Data Engineering, p.145, February 28-March 03, 2000
• 18: Melissa E. O'Neill , F. Warren Burton, A new method for functional arrays, Journal of Functional Programming, v.7 n.5, p.487-513, September 1997 [doi>10.1017/S0956796897002852]
• 19: Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, pCube: Update-Efficient Online Aggregation with Progressive Feedback and Error Bounds, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.95, July 26-28, 2000 [doi>10.1109/SSDM.2000.869781]
• 20: Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Flexible Data Cubes for Online Aggregation, Proceedings of the 8th International Conference on Database Theory, p.159-173, January 04-06, 2001
• 21: M. Riedewald, D. Agrawal, and A. El Abbadi. Efficient integration and aggregation of historical information. Technical Report 2002-07, University of California, Santa Barbara, 2002.
• 22: Yufei Tao , Dimitris Papadias, MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.431-440, September 11-14, 2001
• 23: Donhui Zhang , Alexander Markowetz , Vassilis Tsotras , Dimitrios Gunopulos , Bernhard Seeger, Efficient computation of temporal aggregates with range predicates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-245, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375600]
• 24: D. Zhang, V. J. Tsotras, and D. Gunopulos. Efficient aggregation over objects with extent. In Proc. Int. Conf. on Extending Database Technology (EDBT), 2002. To appear.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

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

General Terms:
Algorithms, Documentation, Theory