Stéphane Grumbach
ABSTRACT
We consider the problem of answering queries using only materialized views. We first show that if the views subsume the query from the point of view of the information content, then the query can be answered using only the views, but the resulting query might be extremely inefficient. We then focus on aggregate views and queries over a single relation, which are fundamental in many applications such as data warehousing. We show that in this case, it is possible to guarantee that as soon as the views subsume the query, it can be completely rewritten in terms of the views in a simple query language. Our main contribution is the conception of various rewriting algorithms which run in polynomial time, and the proof of their completeness which relies on combinatorial arguments. Finally, we discuss the choice of materializing or not ratio views such as average and percentage, important for the design of materialized views. We show that it has an impact on the information content, which can be used to protect data, as well as on the maintenance of views.
- 1.S. Agarwal, R. Agrawal, P. Deshpande, A. Gupta, J. Naughton, R. Ramakrishnan, and S. Sarawagi. On the computation of multidimensional aggregates. In Proceedings of the 22th International Conference on Very Large Data Bases, VLDB'96, pages 506-521, 1996.]] Google Scholar
Digital Library
- 2.S. Abiteboul, and O.M. Duschka. Complexity of Answering Queries Using Materialized Views. In Proceedings of the Seventeenth ACM SIGA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS'98, pages 254-263, 1998.]] Google ScholarDigital Library
- 3.F.N. Afrati, M. Gergatsoulis, and T.G. Kavalieros. Answering Queries Using Materialized Views with Disjunctions. In Proceedings of the 7th International Conference on Database Theory, ICDT'99, pages 435-452, 1999.]] Google ScholarDigital Library
- 4.R. Agrawal, A. Gupta, and S. Sarawagi. Modeling multidimensional databases. In Proceedings of the Thirteenth International Conference on Data Engineering, April 7-11, 1997 Birmingham U.K, pages 232-243. IEEE Computer Society, 1997.]] Google ScholarDigital Library
- 5.S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]] Google ScholarDigital Library
- 6.D. Barbar~ and T. Imielinski. Sleepers and workaholics: Caching strategies in mobile environments. VLDB Journal, 4(4):567-602, 1995.]] Google ScholarDigital Library
- 7.K. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. In Proceedings of A CM SIGMOD International Conference on Management of Data, pages 359-370, 1999.]] Google ScholarDigital Library
- 8.S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In Proceedings of the Eleventh International Conference on Data Engineering, March 6-10, 1995, Taipei, Taiwan, pages 190-200. IEEE Computer Society, 1995.]] Google ScholarDigital Library
- 9.S. Cohen, W. Nutt, and A. Serebrenik. Rewriting aggregate queries using views. In Proceedings of the Eighteenth A CM SIGA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, pages 155-166. ACM Press, 1999.]] Google ScholarDigital Library
- 10.M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J. Ullman. Computing iceberg queries efficiently. In Proceedings of the 2~th International Conference on Very Large Data Bases, VLDB'98, pages 299-310, 1998.]] Google ScholarDigital Library
- 11.O.M. Duschka, and M.R. Genesereth Answering Recursive Queries Using Views. In Proceedings of the Sixteenth A CM SIGA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS'97, pages 109-116, 1997.]] Google ScholarDigital Library
- 12.J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. In Proceed. 12th Intern. Conference on Data Engineering, New Orleans, Louisiana USA, February 1996.]] Google ScholarDigital Library
- 13.S. Grumbach, M. Rafanelli, and L. Tininini. Querying aggregate data. In Proceedings of the Eighteenth A CM SIGA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, pages 174-184. ACM Press, 1999.]] Google ScholarDigital Library
- 14.H. Gupta. Selection of views to materialize in a data warehouse. In Database Theory - ICDT '97, 6th International Conference, Delphi, Greece, January 8-10, 1997, Proceedings, volume 1186, pages 98-112. Springer, 1997.]] Google ScholarDigital Library
- 15.H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman. Index selection for olap. In Proceedings of the Thirteenth International Conference on Data Engineering, April 7-11, 1997 Birmingham U.K, pages 208-219. IEEE Computer Society, 1997.]] Google ScholarDigital Library
- 16.H. Gupta and I. Mumick. Selection of views to materialize under a maintenance cost constraint. In Proceedings of the 7th International Conference on Database Theory, January 10-12, 1999, Jerusalem, Israel, pages 453-470. Springer, 1999.]] Google ScholarDigital Library
- 17.V. Harinarayan, A. Rajaraman, and J. Ullman. Implementing data cube efficiently. In Proceed. Intern. Conference on Management of Data- SIGMOD '96, Montreal, Canada, 1996.]] Google ScholarDigital Library
- 18.A. Levy, A. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proc. A CM Syrnp. on Principles of Database Systems, pages 95-104, 1995.]] Google ScholarDigital Library
- 19.F. Malvestuto. A universal-scheme approach to statistical databases containing homogeneous summary tables. A CM Transactions on Database Systems, 18(4):678-708, 1993.]] Google ScholarDigital Library
- 20.F. Malvestuto and M. Moscarini. Computational issues connected with the protection of sensitive statistics by auditing sum queries. In 10th International Conference on Scientific and Statistical Database Management, Proceedings, Capri, Italy, July 1-3, 1998, pages 134-144. IEEE Computer Society, 1998.]] Google ScholarDigital Library
- 21.F. Malvestuto, M. Moscarini, and M. Rafanelli. Suppressing marginal cells to protect sensitive information in a two-dimensional statistical table. In Proceedings of the Tenth A CM SIGA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado, pages 252-258. ACM Press, 1991.]] Google ScholarDigital Library
- 22.I. Mumick, D. Quass, and B. Mumick. Maintenance of data cubes and summary tables in a warehouse. In SIGMOD 1997, Proceedings A CM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA, pages 100-111. ACM Press, 1997.]] Google ScholarDigital Library
- 23.G. Ozsoyoglu, Z. Ozsoyoglu, and V. Matos. Extending relational algebra and relational calculus with set-valued attributes and aggregate functions. ACM Transactions on Database Systems, 12(4):566-592, December 1987.]] Google ScholarDigital Library
- 24.D. Quass. Maintenance expressions for views with aggregation. In VIEW 1996, Proceedings of the Workshop on Materialized Views: Techniques and Applications, June 7, 1996, Monteal, Canada, pages 110-118, 1996.]]Google Scholar
- 25.M. Rafanelli, A. Bezenchek, and L. Tininini. The aggregate data problem: a system for their definition and management. A CM Sigmod Record, 25(4):8-13, December 1996.]] Google ScholarDigital Library
- 26.A. Shoshani. Olap and statistical databases: Similarities and differences. In Proceed. Intern. Confer. on Principles of Database Systems, PODS'97, Tucson, Arizona, USA, May 1997.]] Google ScholarDigital Library
- 27.D. Sristava, S. Dar, H. Jagadish, and A. Levy. Answering queries with aggregation using views. In Proc. of Intl. Conf. on Very Large Data Bases, pages 318-329, 1996.]] Google ScholarDigital Library
- 28.J. Widom. Research problems in data warehousing. In CIKM 1995, Proceedings of the ~th International Conference on Information and Knowledge Management, November, 1995, Baltimore, Maryland, USA, pages 25-30, 1995.]] Google ScholarDigital Library
- 29.O. Wolfson, A. Sistla, S. Dao, K. Narayanan, and R. Raj. View maintenance in mobile computing. SIGMOD Record, 24(4):22-27, 1995.]] Google ScholarDigital Library
Index Terms
- On the content of materialized aggregate views
Recommendations
Processing Aggregate Queries with Materialized Views in Data Warehouse Environment
Materialized views, which are derived from base relations and stored in the database, offer opportunities for significant performance gain in query evaluation by providing quick access to the pre-computed data. A materialized view can be utilized in ...
On the content of materialized aggregate views
Special issue on PODS 2000We consider the problem of rewriting queries using only materialized views. We first show that if the views subsume the query from the point of view of the information content, then the query can be rewritten using only the views, but the resulting ...
Comments