article · 2001

On Finding Approximate Solutions to the Query Optimization Problem

To The, Sourav Chatterji, Sourav Chatterji, Y. Mahesh Datt, Y. Mahesh Datt, Dr. Sumit Ganguly, Dr. Sumit Ganguly

Cited by 0Abstract and details only

Abstract

In this project, we consider the problem of computing the optimal join order sequences for general queries. We considered nested loops join model. The use of cartesian products is avoided and only linear trees are considered for query execution. We show that the problem of computing the optimal join order sequence for genreral queries is NP-Complete when the join methods are restricted to nested loop joins only. We then show that the problem of finding a join order sequence whose cost is within a factor of 2 ( logK) of K, where K is the optimal cost, is NP-Hard. The result is valid when the number of edges in the query graph is restricted to a given function of the number of its vertices, except for very sparse or very dense graphs. The join method is restricted to nested loops joins only, but, the result remains true when other join methods are also considered. To the best of our knowledge, this is the first inapproximabilty result in Query Optimization We also prove some results which are not directly relevant to the problem in hand and are only of theoretical interest to the problem at present. However they also provide some insight to the complexity of the problem. We prove that nding an approximate solution to the lexicographic ordering is NP complete. We also provide a procedure to transform a graph to another graph with all vertices of some degree without changing the max clique size. Lastly, we suggest some heuristics for finding the join order.

Cite this paper

APA 7

The, T., Chatterji, S., Chatterji, S., Datt, Y. M., Datt, Y. M., Ganguly, D. S., & Ganguly, D. S. (2001). On Finding Approximate Solutions to the Query Optimization Problem.

MLA 9

The, To, et al. “On Finding Approximate Solutions to the Query Optimization Problem.” 2001.

Chicago

The, To, Sourav Chatterji, Sourav Chatterji, Y. Mahesh Datt, Y. Mahesh Datt, Dr. Sumit Ganguly, and Dr. Sumit Ganguly. 2001. “On Finding Approximate Solutions to the Query Optimization Problem.”

Harvard

The, T. et al. (2001) ‘On Finding Approximate Solutions to the Query Optimization Problem’.

BibTeX

@article{the2001finding,
  title = {{On Finding Approximate Solutions to the Query Optimization Problem}},
  author = {The, To and Chatterji, Sourav and Chatterji, Sourav and Datt, Y. Mahesh and Datt, Y. Mahesh and Ganguly, Dr. Sumit and Ganguly, Dr. Sumit},
  year = {2001}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.