QUERY PROCESSING IN DISTRIBUTED DATABASES
Victor O. K. Li, Victor O. K. Li · 1981
This paper describes two new distributed query processing algorithms. The MST Algorithm minimizes the total communication costs associated with a query while the MDT Algorithm minimizes the response time. These two algorithms are easy to analyze and to implement, since they are based on the minimum spanning tree and the shortest path problems, for which numerous algorithms exist. In addition, these two algorithms can be implemented using distributed computation, i.e., each node using only information available from adjacent nodes. We also develop the 'artificial file node' technique to extend existing query processing algorithms which are designed for non-redundant databases to that for general, redundant databases. The two algorithms are illustrated by simple examples. (Author)