In this article, we consider the query evaluation problem in relational multidatabases and develop a method for generating optimal plans for queries submitted to such a system. Three aspects will be discussed: query transformation, join tree balance and node allocation. For query translation, the concept of relation structure terms (RST) is introduced. Based on RSTs, we can transform a query into another form automatically by constructing derivation rules for them. Further, we extend the approach for balancing a join tree proposed by Du et al. so that more balanced join trees can be obtained. Lastly, we present the concept of dynamic time tables for performing node allocation in a dynamic programming manner.

Keywords: heterogeneous databases, join tree balance, relation structure terms, dynamic programming, dynamic time tables

Retrieve PDF document (200007_01.pdf)

Received December 28, 1998; revised May 24, 1999; accepted July 19, 1999.
Communicated by Wei-Pang Yang