The View-Selection Problem Has an Exponential-Time Lower Bound for Conjunctive Queries and Views

Summary: Shows that view-selection for conjunctive queries and views has an exponential-time lower bound under the practical sum-cost model, extending prior product-cost impossibility results. Hence no data-independent algorithm can always output polynomially many views and be optimal. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1261
Venue: PODS
Year: 2002
Pagerank: -
Overall Rank: 13,754 | 4.32%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Rada Chirkova

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,259	Materializing Views with Minimal Size To Answer Queries	2003	PODS	4.3690661e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,032	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS	4.1945683e-05
6,881	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	4.8964953e-05
6,567	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.0069599e-05
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028596715
1,112	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013917776
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
584	Answering Queries with Aggregation Using Views	1996	VLDB	0.0001971526
3,074	On the Complexity of the View-Selection Problem	1999	PODS	7.6110034e-05
9,259	Materializing Views with Minimal Size To Answer Queries	2003	PODS	4.3690661e-05
3,583	A Formal Perspective on the View Selection Problem	2001	VLDB	6.9463532e-05