Paper Info
Title
Histogram methods in query optimization: the relation between accuracy and optimality
Abstract
We have solved the following problem using pattern classification techniques (PCT): given two histogram methods, M/sub 1/ and M/sub 2/, used in query optimization, if the estimation accuracy of M/sub 1/ is greater than that of M/sub 2/, then M/sub 1/ has a higher probability of leading to the optimal query evaluation plan (QEP) than M/sub 2/. To the best of our knowledge, this problem has been open for at least two decades, the difficulty of the problem partially being due to the hurdles involved in the formulation itself. By formulating the problem from a pattern recognition perspective, we use PCT to present a rigorous mathematical proof of this fact, and show some uniqueness results. We also report empirical results demonstrating the power of these theoretical results on well-known histogram estimation methods.
Year
DOI
Venue
2001
10.1109/DASFAA.2001.916393
Hong Kong, China
Keywords
Field
DocType
database theory,estimation theory,graphs,optimisation,pattern classification,probability,query processing,estimation accuracy,histogram methods,optimal query evaluation plan,optimality,pattern classification techniques,pattern recognition,probability,query optimization,rigorous mathematical proof,uniqueness results
Query optimization,Uniqueness,Graph,Histogram,Data mining,Computer science,Theoretical computer science,Mathematical proof,Estimation theory,Database theory,Database
Conference
ISBN
Citations 
PageRank 
0-7695-0996-7
0
0.34
References 
Authors
9
2
Name
Order
Citations
PageRank
B. John Oommen1759143.24
Luis Rueda239553.42