The view-selection problem has an exponential-time lower bound for conjunctive queries and views

ABSTRACT

The view-selection problem is to design and materialize a set of views over a database schema, such that the choice of views minimizes the cost of evaluating the selected workload of queries, and the combined size of the materialized views does not exceed a prespecified storage limit. Important applications of the view-selection problem include query optimization, data warehouse design, and information integration.We consider the view-selection problem in relational databases, for conjunctive queries and views. Suppose somebody wants to design a view-selection algorithm that outputs a polynomial number of views for all query workloads and storage limits and produces optimal selections of views independently of actual database contents. In previous work it was shown that it is impossible to design such an algorithm when the product (as for nested-loop joins) cost model is used. That is, there exist databases for which the number of views in an optima] viewset is exponential in the size of the database schema and query workload. As a consequence, under the product-cost model the view-selection problem has an exponential-time lower bound.Efficient join algorithms have a cost that is proportional to the sum of the sizes of the input and output relations. In this paper we prove that under the more practical sum-cost model, the view-selection problem also has an exponential time lower bound. As a consequence, under the sum-cost model it is also impossible to come up with a view-selection algorithm that outputs a polynomial number of views for all query workloads and databases, yet produces optimal selections of views.

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: Rada Chirkova , Michael R. Genesereth, Linearly Bounded Reformulations of Conjunctive Databases, Proceedings of the First International Conference on Computational Logic, p.987-1001, July 01, 2000
• 5: 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
• 6: 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
• 7: 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
• 8: Himanshu Gupta , Inderpal Singh Mumick, Selection of Views to Materialize Under a Maintenance Cost Constraint, Proceeding of the 7th International Conference on Database Theory, p.453-470, January 10-12, 1999
• 9: Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000 [doi>10.1145/369275.369284]
• 10: 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
• 11: Howard Karloff , Milena Mihail, On the complexity of the view-selection problem, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-173, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303993]
• 12: 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]
• 13: Kenneth A. Ross , Divesh Srivastava , S. Sudarshan, Materialized view maintenance and integrity constraint checking: trading space for time, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.447-458, June 04-06, 1996, Montreal, Quebec, Canada
• 14: 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
• 15: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 16: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Search process

General Terms:
Design, Languages, Theory