Name
Abstract | ||
|---|---|---|
In this work, we study the complexity of the problem of approximate query optimization. We show that, for any δ 0, the problem of finding a join order sequence whose cost is within a factor 2Θ(log1-δ(K)) of K, where K is the cost of the optimal join order sequence is NP-Hard. The complexity gap remains if the number of edges in the query graph is constrained to be a given function e(n) of the number of vertices n of the query graph, where n(n - 1)/2 - Θ(nτ) ≥ e(n) ≥ n + Θ(nτ) and τ is any constant between 0 and 1. These results show that, unless P=NP, the query optimization problem cannot be approximately solved by an algorithm that runs in polynomial time and has a competitive ratio that is within some polylogarithmic factor of the optimal cost. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/543613.543650 | PODS |
Keywords | Field | DocType |
order sequence,competitive ratio,query optimization problem,optimal cost,vertices n,approximate query optimization,query graph,polynomial time,polylogarithmic factor,complexity gap,query optimization,complexity | Query optimization,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Theoretical computer science,Optimal cost,Time complexity,Mathematics,Competitive analysis | Conference |
ISBN | Citations | PageRank |
1-58113-507-6 | 6 | 0.46 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Chatterji | 1 | 6 | 0.46 |
| S. S. K. Evani | 2 | 6 | 0.46 |
| Sumit Ganguly | 3 | 813 | 236.01 |
| M. D. Yemmanuru | 4 | 6 | 0.46 |