Abstract On the Complexity of the View-Selection Problem

commonly used and powerful technique for improving query response time over very large databases is to precompute (‘Lmaterialize”) fre-quently ’ asked queries (“views”). The problem is to select an appropriate set of views, given a lim-ited amount of resources. Harinarayan, Rajaraman and Ullman formalized this technique by propos-ing a framework in which queries are modeled by a weighted partial order, and selecting a set of views whose materialization minimizes the average query response time is equivalent to selecting a subset of nodes of the partial order that minimizes a suitably defined cost function. Because this problem is NP-Hard, the focus is on approximability and heuris-tics. Harinarayan, Rajaraman and Ullman proposed a greedy heuristic together with a “benefit ” crite-rion to measure its performance; this heuristic and performance measure are used in several subsequent papers which generalize their work. We prove the following lower bounds: (a) The greedy heuristic of Harinarayan, Rajaraman and Ull-man has query response time at least n/12 times op-timal for infinitely many n. (Compare this to the fact that no algorithm, regardless of how naive it is, ever has query response time exceeding n times optimal.) (b) If PfNP, then for every e> 0, every polynomial-time approximation algorithm for the view-selection problem will output solutions with query response time at least n’- ’ times optimal, for infinitely many n, even for partial orders with bounded degrees an