On the Content of Materialized Aggregate Views Stéphane Grumbach and Leonardo Tininini   View Paper (PDF)   Return to Views / Query Containment 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 Note: References link to DBLP on the Web. [1] Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi : On the Computation of Multidimensional Aggregates. VLDB 1996 : 506-521 [2] Serge Abiteboul , Oliver M. Duschka : Complexity of Answering Queries Using Materialized Views. PODS 1998 : 254-263 [3] Foto N. Afrati , Manolis Gergatsoulis , Theodoros G. Kavalieros : Answering Queries Using Materialized Views with Disjunctions. ICDT 1999 : 435-452 [4] Rakesh Agrawal , Ashish Gupta , Sunita Sarawagi : Modeling Multidimensional Databases. ICDE 1997 : 232-243 [5] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [6] Daniel Barbará , Tomasz Imielinski : Sleepers and Workaholics: Caching Strategies in Mobile Environments. VLDB Journal 4(4) : 567-602(1995) [7] Kevin S. Beyer , Raghu Ramakrishnan : Bottom-Up Computation of Sparse and Iceberg CUBEs. SIGMOD Conference 1999 : 359-370 [8] Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200 [9] Sara Cohen , Werner Nutt , Alexander Serebrenik : Rewriting Aggregate Queries Using Views. PODS 1999 : 155-166 [10] Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman : Computing Iceberg Queries Efficiently. VLDB 1998 : 299-310 [11] Oliver M. Duschka , Michael R. Genesereth : Answering Recursive Queries Using Views. PODS 1997 : 109-116 [12] Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh : Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total. ICDE 1996 : 152-159 [13] Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini : Querying Aggregate Data. PODS 1999 : 174-184 [14] Himanshu Gupta : Selection of Views to Materialize in a Data Warehouse. ICDT 1997 : 98-112 [15] Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman : Index Selection for OLAP. ICDE 1997 : 208-219 [16] Himanshu Gupta , Inderpal Singh Mumick : Selection of Views to Materialize Under a Maintenance Cost Constraint. ICDT 1999 : 453-470 [17] Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman : Implementing Data Cubes Efficiently. SIGMOD Conf. 1996 : 205-216 [18] Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104 [19] Francesco M. Malvestuto : A Universal-Scheme Approach to Statistical Databases Containing Homogeneous Summary Tables. TODS 18(4) : 678-708(1993) [20] Francesco M. Malvestuto , Marina Moscarini : Computational Issues Connected with the Protection of Sensitive Statistics by Auditing Sum Queries. SSDBM 1998 : 134-144 [21] Francesco M. Malvestuto , Marina Moscarini , Maurizio Rafanelli : Suppressing Marginal Cells to Protect Sensitive Information in a Two-Dimensional Statistical Table. PODS 1991 : 252-258 [22] Inderpal Singh Mumick , Dallan Quass , Barinderpal Singh Mumick : Maintenance of Data Cubes and Summary Tables in a Warehouse. SIGMOD Conference 1997 : 100-111 [23] Gultekin Özsoyoglu , Z. Meral Özsoyoglu , Victor Matos : Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. TODS 12(4) : 566-592(1987) [24] Dallan Quass : Maintenance Expressions for Views with Aggregation. VIEWS 1996 : 110-118 [25] Maurizio Rafanelli , Antonia Bezenchek , Leonardo Tininini : The Aggregate Data Problem: A System for their Definition and Management. SIGMOD Record 25(4) : 8-13(1996) [26] Arie Shoshani : OLAP and Statistical Databases: Similarities and Differences. PODS 1997 : 185-196 [27] Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy : Answering Queries with Aggregation Using Views. VLDB 1996 : 318-329 [28] Jennifer Widom : Research Problems in Data Warehousing. CIKM 1995 : 25-30 [29] Ouri Wolfson , A. Prasad Sistla , Son Dao , Kailash Narayanan , Ramya Raj : View Maintenance in Mobile Computing. SIGMOD Record 24(4) : 22-27(1995) BIBTEX @inproceedings{DBLP:conf/pods/GrumbachT00,   author    = {St{\'e}phane Grumbach and                 Leonardo Tininini},    title     = {On the Content of Materialized Aggregate Views},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {47-57},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.