More Web Proxy on the site http://driver.im/

Article

Free access

On the content of materialized aggregate views

Authors:

Stéphane Grumbach,

Leonardo TinininiAuthors Info & Claims

PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 47 - 57

https://doi.org/10.1145/335168.335174

Published: 01 May 2000 Publication History

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.

References

[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.]]

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.]]

Digital 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.]]

Digital 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.]]

Digital Library

[5]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]]

Digital Library

[6]

D. Barbar~ and T. Imielinski. Sleepers and workaholics: Caching strategies in mobile environments. VLDB Journal, 4(4):567-602, 1995.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

[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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital Library

Cited By

Afrati FChirkova R(2022)Answering Queries Using Views, Second EditionundefinedOnline publication date: 26-Feb-2022
Tang RWu HHe XBressan S(2015)Valuating Queries for Data Trading in Modern CitiesProceedings of the 2015 IEEE International Conference on Data Mining Workshop (ICDMW)10.1109/ICDMW.2015.11(414-421)Online publication date: 14-Nov-2015
LeFevre JSankaranarayanan JHacigumus HTatemura JPolyzotis NCarey MDyreson CLi FÖzsu M(2014)Opportunistic physical design for big data analyticsProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2610512(851-862)Online publication date: 18-Jun-2014
Show More Cited By

Index Terms

On the content of materialized aggregate views
1. Information systems
  1. Data management systems
    1. Query languages
  2. Information systems applications
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

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 2000

We 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 ...
Extended conditions for answering an aggregate query using materialized views

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

May 2000

281 pages

ISBN:158113214X

DOI:10.1145/335168

Chairmen:
Victor Vianu
Univ. of California at San Diego, La Jolla
,
Georg Gottlob
Technische Univ. Wien, Vienna, Austria

Copyright © 2000 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS00

Sponsor:

SIGMOD

SIGMOD/PODS00: ACM International Conference on Management of Data and Symposium on Principles of Database Systems

May 15 - 18, 2000

Texas, Dallas, USA

Acceptance Rates

PODS '00 Paper Acceptance Rate 26 of 119 submissions, 22%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
435
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)8

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Afrati FChirkova R(2022)Answering Queries Using Views, Second EditionundefinedOnline publication date: 26-Feb-2022
Tang RWu HHe XBressan S(2015)Valuating Queries for Data Trading in Modern CitiesProceedings of the 2015 IEEE International Conference on Data Mining Workshop (ICDMW)10.1109/ICDMW.2015.11(414-421)Online publication date: 14-Nov-2015
LeFevre JSankaranarayanan JHacigumus HTatemura JPolyzotis NCarey MDyreson CLi FÖzsu M(2014)Opportunistic physical design for big data analyticsProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2610512(851-862)Online publication date: 18-Jun-2014
Afrati F(2011)Determinacy and query rewriting for conjunctive queries and viewsTheoretical Computer Science10.1016/j.tcs.2010.12.031412:11(1005-1021)Online publication date: 1-Mar-2011
Hu YZhai WTian YGao T(2011)Research and Application of Query Rewriting Based on Materialized ViewsInformation and Automation10.1007/978-3-642-19853-3_12(85-91)Online publication date: 2011
Marx MKolaitis PLibkin L(2007)Queries determined by viewsProceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1265530.1265534(23-30)Online publication date: 11-Jun-2007
Calvanese DDe Giacomo GLenzerini MVardi M(2007)View-based query processingTheoretical Computer Science10.1016/j.tcs.2006.11.006371:3(169-182)Online publication date: 25-Feb-2007
Afrati F(2007)Rewriting Conjunctive Queries Determined by ViewsMathematical Foundations of Computer Science 200710.1007/978-3-540-74456-6_9(78-89)Online publication date: 2007
Nash ASegoufin LVianu V(2007)Determinacy and rewriting of conjunctive queries using viewsProceedings of the 11th international conference on Database Theory10.1007/11965893_5(59-73)Online publication date: 10-Jan-2007
Lin VVassalos VMalakasiotis P(2006)MiniCountProceedings of the 22nd International Conference on Data Engineering10.1109/ICDE.2006.95Online publication date: 3-Apr-2006
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents