The View-Selection Problem Has an Exponential-Time Lower Bound for Conjunctive Queries and Views Rada Chirkova   View Paper (PDF)   Return to Views and Warehousing Abstract 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. DiSC'03 © 2003 Association for Computing Machinery