Optimization of multiple-disjunct queries in a relational database system
M. Muralikrishna · Minds at UW (University of Wisconsin) · 1988
In this thesis, we describe the optimization of arbitrarily complex queries expressed in relational calculus. The qualification list is allowed to be any complex boolean expression involving both ANDs and ORs. In other words, the qualification list may have an arbitrary number of disjuncts. The query graph of each disjunct may also have any number of components. Optimizing the various disjuncts independently of each other can be very inefficient. Considerable savings in cost can be achieved by optimizing the various disjuncts together. In a multiple-relation multiple-disjunct query, it may be possible to combine two or more disjuncts into one term. This will cut down the number of scans on each relation and also the number of times each join is performed. The objective will be to merge the disjuncts into the minimum number of terms. Minimizing the number of terms can be formulated as the problem of covering a merge graph with the minimum number of complete merge graphs, which are a restricted class of cartesian product graphs. The problem of minimizing the number of terms is NP-complete. We present polynomial time algorithms for special classes of merge graphs. We provide a heuristic for general merge graphs. For single-relation multiple-disjunct queries involving more than one attribute, an optimal access path might consist of more than one index. The cost in our optimization model, for single relation queries, is measured in terms of the number of pages fetched from disk. We will formulate the problem of finding a set of optimal access paths for a single-relation multiple-disjunct query as one of finding a minimum weighted vertex cover in a hypergraph. Finding the cheapest vertex cover in a hypergraph is NP-complete. We present a new approximation algorithm that gives near optimal vertex covers for random hypergraphs over a wide range of edge probabilities. We also demonstrate the usefulness of equi-depth multi-dimensional histograms in optimizing queries using multi-dimensional indices.