The state transition model is general enough to account for the possibility of parallel processing among the various sites, as well as for redundancy in the database. The model also permits significant reductions of the necessary computations by taking advantage of simple additivity and site-uniformity properties of a cost model, and of clever strategies that improve on the basic dynamic programming algorithm. This paper describes a state transition model for the optimization of query processing in a distributed database. The i th component of a state vector is a list of the relations currently existing at the i th site. A final state is one that contains the answer to the query in one of its components.
Dynamic programming is used to compute the costs of the states and the optimal solution.
The Digital Library is published by the Association for Computing Machinery.