Distributed query processing (DQP) strategy analysis and balanced DQP algorithm development
Shih‐Wei Chou · 1993
A new balanced DQP (BDQP) algorithm is developed by analyzing and comparing the existing DQP algorithms including Fragmented Processing (FP), Fragment Replication Strategy (FRS), Query Splitting (QS), and Semijoin Replication Strategy (SRS) algorithms. The unsolved DQP problems contained in these four algorithms are identified as follows: (1) The objective function in most of the proposed DQP algorithms are single dimension objective function and not complete. In contrast, in BDQP algorithms both the communication cost and response time are the objective functions. (2) The environments are too restricted. FP and QS consider the query processing problems in an environment without replicate copies of fragmented relation. FRS and SRS algorithms are used in a local area network only. However, the environments of the BDQP contain local area network, long-haul network, data redundancy, and data fragmentation. (3) How to process distributed querys efficiently still requires further analysis. FP does not use semijoin method to reduce communication cost. However, BDQP adopts semijoin method to reduce communication and local processing cost. (4) Different execution orders will produce dissimilar results in a DQP algorithm. BDQP uses limited and exhaustive search methods to find the heuristic and optimal execution order. The performance of the BDQP, FP, FRS, QS, and SRS algorithms are examined individually.