Query optimization in distributed databases by predicate analysis and semijoin techniques
David Vineyard · Michigan State University Libraries · 1989
In a distributed database system, the cost of answering queries is strongly dependent on the cost to transmit information between sites. Methods of reducing transmission costs for selection and join are developed. Selection queries on relations which are fragmented among sites are made more efficient by accessing a subset of all sites containing relation fragments. Fragmentation predicates are compared with the qualification of the selection query. Disagreement between a predicate and the qualification determines that no tuples from that fragment will be selected. If fragmentation is disjoint, then all sites in which the fragmentation predicate does not disagree with the query qualification must be accessed. If fragmentation is non-disjoint, a subset of the remaining fragments may be sufficient to answer the query. Heuristics are given which determine a subset of fragments to access. The method of optimizing selection queries is extended to recursive queries. A method for describing the contents of a fragment of a recursive relation is given which uses the properties of partial order sets and lattices. Heuristics are given to determine a subset of fragments of the recursive relation. An effective method to access these fragments is given for recursive queries when then fragments are closed under the recursive operation. A method for optimizing join queries is also given. Join queries are optimized by using semijoin programs. A reduced cover set of the set of full reducer semijoin programs is given. The elements of this reduced cover set are used in an algorithm to find the optimal full reducer program. A method is also presented which determines the optimal profitable semijoin program. The cost of finding the optimal profitable semijoin program is high. A low cost method for finding a near optimal profitable semijoin program is presented. This method uses a semijoin program as input and outputs a partial order graph showing the optimal sequence of performing the semijoins. The partial order graph also shows the maximal concurrency for the semijoin program. It is also shown that the least upper bound on the length of any profitable semijoin program is $N$ x $(N - 1)$ for a query graph of N nodes.