Query processing for fragmented databases on broadcast local networks

Abstract

This thesis presents a new approach to distributed query processing in the environment where relations are horizontally fragmented over a broadcast local area network. Partitioning relations into horizontal fragments is useful is reducing query processing costs for most queries. However, only a few query processing algorithms have been proposed specifically for fragmented databases. In framented databases, optimizing a join is difficult even if the problem is restircted to a single join between two fragmented relations, which is called two-way join. Two-way joins are the most popular distributed queries, and the optimization of two-way joins serves as a basis for the optimization of multiple joins. In this thesis, we focus on optimizing two-way joins on broadcast local area netwokrs. In order to optimize the total processing costs of two-way joins, a new fourphase approach is proposed:(1) query transformation, (2) semijion optimization, (3) join optimization, and (4) final processing. In our approach, replicated copies of a fragment are used to improve parallelism and transmission cost, and both of local processing cost and transmission cost are considered to optimize the query processing cost. In addition, the broadcasting capability of local area networks is put to use to reduce data transmissions. In order to perform query transformation efficiectly, the qualification of each fragment is restricted to be represented as a conjunction of comparisons. Then, the query transformation problem is transformed into a rectangle intersection problem, and an efficient algorithm is developed for the transformed problem. In the semijoin optimization phase, a greedy algorithm is developed to obtain beneficial semijoins. For a given set of semijoins, the problem that optimizes the transmission order of the joining attributes is transformed into a minimum weight feedback vertex set problem. The transformed problem is proved to be NP-hard, thus a heuirstic algorithm that opti...