Tree query optimization in distributed object-oriented databases

Much of the work in query optimization in object-oriented database is devoted to finding efficient ways of path traversals expressed in a query. In the environment where a query involves classes distributed across several sites, communication cost must be taken into consideration. In this paper we describe a tree query optimization algorithm using dynamic programming technique for a distributed object-oriented database. The primary objective of the optimization is to minimize the total processing time including local processing and communication costs. In contrast to optimizers which consider a restricted search space, the proposed optimizer searches the execution plans which may be deep or bushy trees. Especially the plans can start traversal anywhere in a query graph and not only from either end of the query graph