Materializing views with minimal size to answer queries

ABSTRACT

In this paper we study the following problem. Given a database and a set of queries, we want to find, in advance, a set of views that can compute the answers to the queries, such that the size of the viewset (i.e., the amount of space, in bytes, required to store the viewset) is minimal on the given database. This problem is important for many applications such as distributed databases, data warehousing, and data integration. We explore the decidability and complexity of the problem for workloads of conjunctive queries. We show that results differ significantly depending on whether the workload queries have self-joins. If queries can have self-joins, then a disjunctive viewset can be a better solution than any set of conjunctive views. We show that the problem of finding a minimal-size disjunctive viewset is decidable, and give an upper bound on its complexity. If workload queries cannot have self-joins, there is no need to consider disjunctive viewsets, and we show that the problem is in NP. We describe a very compact search space of conjunctive views, which contains all views in at least one optimal disjunctive viewset. We give a dynamic-programming algorithm for finding minimal-size disjunctive viewsets for queries without self-joins, and discuss heuristics to make the algorithm efficient.

REFERENCES

• 1: Foto N. Afrati , Chen Li , Jeffrey D. Ullman, Generating efficient plans for queries using views, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.319-330, May 21-24, 2001, Santa Barbara, California, United States
• 2: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 3: Elena Baralis , Stefano Paraboschi , Ernest Teniente, Materialized Views Selection in a Multidimensional Database, Proceedings of the 23rd International Conference on Very Large Data Bases, p.156-165, August 25-29, 1997
• 4: Randall G. Bello , Karl Dias , Alan Downing , James J. Feenan, Jr. , James L. Finnerty , William D. Norcott , Harry Sun , Andrew Witkowski , Mohamed Ziauddin, Materialized Views in Oracle, Proceedings of the 24rd International Conference on Very Large Data Bases, p.659-664, August 24-27, 1998
• 5: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 6: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Answering Queries Using Views over Description Logics Knowledge Bases, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.386-391, July 30-August 03, 2000
• 7: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 8: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 9: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 10: An Algebraic Compression Framework for Query Results, Proceedings of the 16th International Conference on Data Engineering, p.177, February 28-March 03, 2000
• 11: Rada Chirkova, The view-selection problem has an exponential-time lower bound for conjunctive queries and views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543634]
• 12: R. Chirkova and M. R. Genesereth. Linearly bounded reformulations of conjunctive databases. DOOD, 2000.
• 13: Rada Chirkova , Alon Y. Halevy , Dan Suciu, A Formal Perspective on the View Selection Problem, Proceedings of the 27th International Conference on Very Large Data Bases, p.59-68, September 11-14, 2001
• 14: Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.331-342, May 21-24, 2001, Santa Barbara, California, United States
• 15: Himanshu Gupta, Selection of Views to Materialize in a Data Warehouse, Proceedings of the 6th International Conference on Database Theory, p.98-112, January 08-10, 1997
• 16: H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman. Index selection in olap. In ICDE, 1997.
• 17: Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang, Optimizing Queries Across Diverse Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.276-285, August 25-29, 1997
• 18: H. Hacigümüş, B. Iyer, C. Li, and S. Mehrotra. Executing SQL over encrypted data in the database-service-provider model. In SIGMOD, 2002.
• 19: H. Hacigümüş, B. Iyer, and S. Mehrotra. Providing database as a service. In ICDE, 2002.
• 20: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 21: 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
• 22: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 23: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 24: Chen Li , Mayank Bawa , Jeffrey D. Ullman, Minimizing View Sets without Losing Query-Answering Power, Proceedings of the 8th International Conference on Database Theory, p.99-113, January 04-06, 2001
• 25: J. Li, R. Chirkova, and C. Li. Minimizing data-communication costs by decomposing query results in client-server environments. Technical report, Information and Computer Science, UC Irvine, 2003.
• 26: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 27: Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
• 28: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 29: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 30: Dimitri Theodoratos , Spyros Ligoudistianos , Timos K. Sellis, Designing the Global Data Warehouse with SPJ Views, Proceedings of the 11th International Conference on Advanced Information Systems Engineering, p.180-194, June 14-18, 1999
• 31: Dimitri Theodoratos , Timos K. Sellis, Data Warehouse Configuration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.126-135, August 25-29, 1997
• 32: TPC-H. http://www.tpc.org/tpch/.
• 33: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 34: Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]
• 35: Jian Yang , Kamalakar Karlapalem , Qing Li, Algorithms for Materialized View Design in Data Warehousing Environment, Proceedings of the 23rd International Conference on Very Large Data Bases, p.136-145, August 25-29, 1997
• 36: M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of VLDB, pages 82--94. IEEE Computer Society Press, 1981.
• 37: Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.105-116, May 15-18, 2000, Dallas, Texas, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

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

General Terms:
Experimentation, Theory