sigmod_1997_elementary.txt

利用lwp：：get写的

Our approach to answering range-max queries is based on precomputed max over balanced hierarchical tree structures. We use a branch-and-bound-like procedure to speed up the finding of max in a region. We also show that with a branch-and-bound procedure, the average-case complexity is much smaller than the worst-case complexity.</abstract></paper><paper><title>Cubetree: organization of and bulk incremental updates on the data cube</title><author><AuthorName>Nick Roussopoulos</AuthorName><institute><InstituteName>Department of Computer Science, Stanford University</InstituteName><country></country></institute></author><author><AuthorName>Yannis Kotidis</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Mema Roussopoulos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996</name><name>R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta In. formatica, 1(3):173-189, 1972.</name><name>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</name><name>Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Index Selection for OLAP, Proceedings of the Thirteenth International Conference on Data Engineering, p.208-219, April 07-11, 1997</name><name>Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Ibrahim Kamel and Christos Faloutsos. Hflbert r-tree: an improved r-tree using fraztals. Systems Research Center (SRC) TR-93-19, Univ. of Maryland, College Park, 1993.</name><name>Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States</name><name>Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982</name><name>Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton , Karthikeyan Ramasamy, Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies, Proceedings of the 22th International Conference on Very Large Data Bases, p.522-531, September 03-06, 1996</name></citation><abstract>The data cube is an aggregate operator which has been shown to be very powerful for On Line Analytical Processing (OLAP) in the context of data warehousing. It is, however, very expensive to compute, access, and maintain. In this paper we define the &amp;ldquo;cubetree&amp;rdquo; as a storage abstraction of the cube and realize in using packed R-trees for most efficient cube queries. We then reduce the problem of creation and maintenance of the cube to sorting and bulk incremental merge-packing of cubetrees. This merge-pack has been implemented to use separate storage for writing the updated cubetrees, therefore allowing cube queries to continue even during maintenance. Finally, we characterize the size of the delta increment for achieving good bulk update schedules for the cube. The paper includes experiments with various data sets measuring query and bulk update performance.</abstract></paper><paper><title>Maintenance of data cubes and summary tables in a warehouse</title><author><AuthorName>Inderpal Singh Mumick</AuthorName><institute><InstituteName>Lucent Technologies</InstituteName><country></country></institute></author><author><AuthorName>Dallan Quass</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Barinderpal Singh Mumick</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996</name><name>M. Adiba and [3. Lindsay. Database snapshots. In Proceedings of the sixth International Conference on Very Large Databases, pages 86-91, Montreal, Canada, October 1980.</name><name>O. Peter Buneman , Eric K. Clemons, Efficiently monitoring relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.368-382, Sept. 1979</name><name>Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States</name><name>Latha S. Colby , Timothy Griffin , Leonid Libkin , Inderpal Singh Mumick , Howard Trickey, Algorithms for deferred view maintenance, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.469-480, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994</name><name>Proceedings of the 1995 ACM SIGMOD international conference on Management of data, June 1995</name><name>Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991</name><name>Proceedings of the 21th International Conference on Very Large Data Bases, September 1995</name><name>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</name><name>A. Gupta, V. Harinarayan, and D. Quass. Generalized projections: A powerful approach to aggregation. In Dayal et al. [DGN95].</name><name>Ashish Gupta , H. V. Jagadish , Inderpal Singh Mumick, Data Integration using Self-Maintainable Views, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.140-144, March 25-29, 1996</name><name>Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.328-339, May 22-25, 1995, San Jose, California, United States</name><name>Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States</name><name>Eric N. Hanson, A performance analysis of view materialization strategies, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.440-453, May 27-29, 1987, San Francisco, California, United States</name><name>Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Richard Hull , Gang Zhou, A framework for supporting data integration using the materialized and virtual approaches, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.481-492, June 04-06, 1996, Montreal, Quebec, Canada</name><name>H. Jagadish and I. Mumick, editors. Proceedings of A CM SIGMOD I996 International Conference on Management of Data, Montreal, Canada, June 1996.</name><name>H. V. Jagadish , Inderpal Singh Mumick , Abraham Silberschatz, View maintenance issues for the chronicle data model (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.113-124, May 22-25, 1995, San Jose, California, United States</name><name>James J. Lu , Guido Moerkotte , Joachim Schue , V. S. Subrahmanian, Efficient maintenance of materialized mediated views, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.340-351, May 22-25, 1995, San Jose, California, United States</name><name>Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993</name><name>Dallan Quass , Ashish Gupta , Inderpal Singh Mumick , Jennifer Widom, Making views self-maintainable for data warehousing, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.158-169, December 18-20, 1996, Miami Beach, Florida, United States</name><name>D. Quass. Maintenance expressions for views with aggregation. Presented at the Workshop on Materialized Views, June 1996.</name><name>Dallan Wendell Quass, Materialized views in data warehouses, Stanford University, Stanford, CA, 1998</name><name>X. Qian , G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.337-341, September 1991</name><name>Nick Roussopoulos , Hyunchul Kang, Principles and techniques in the design of ADMS:.F:6WWp, Computer, v.19 n.12, p.19-25, Dec. 1986</name><name>S. Sarawagi, R. Agrawal, and A. Gupta. On computing the data cube. Research report rj 10026, IBM Almaden Research Center, San Jose. California, 1996.</name><name>Oded Shmueli , Alon Itai, Maintenance of views, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>A. Segev , J. Park, Updating Distributed Materialized Views, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.173-184, June 1989</name><name>Proceedings of the 22th International Conference on Very Large Data Bases, September 1996</name><name>Weipeng P. Yan , Per-&amp;#197;ke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995</name><name>Yue Zhuge , H&amp;#233;ctor Garc&amp;#237;a-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States</name></citation><abstract>Data warehouses contain large amounts of information, often collected from a variety of independent sources. Decision-support functions in a warehouse, such as on-line analytical processing (OLAP), involve hundreds of complex aggregate queries over large volumes of data. It is not feasible to compute these queries by scanning the data sets each time. Warehouse applications therefore build a large number of summary tables, or materialized aggregate views, to help them increase the system performance.
As changes, most notably new transactional data, are collected at the data sources, all summary tables at the warehouse that depend upon this data need to be updated. Usually, source changes are loaded into the warehouse at regular intervals, usually once a day, in a batch window, and the warehouse is made unavailable for querying while it is updated. Since the number of summary tables that need to be maintained is often large, a critical issue for data warehousing is how to maintain the summary tables efficiently.