Foreign functions have been considered in the advanced database systems to support complex applications. We consider optimizing queries with foreign functions in a distributed environment. In traditional distributed query processing, selection operations are locally processed before joins as much as possible so that the size of relations being transmitted and joined can be reduced. However, if selection predicates involve foreign functions, the cost of evaluating selections cannot be ignored. As a result, the execution order of selections and joins becomes significant, and the trade-off for reducing the costs of data transmission, join processing, and selection predicate evaluation needs to be carefully considered in query optimization. A response time model is developed for estimating the cost of distributed query processing involving foreign functions. We explore the property of the problem and find an optimal algorithm with polynomial complexity for a special case of it. However, finding the optimal execution plan for the general case is NP-hard. We propose an efficient heuristic algorithm for solving the problem and the simulation result shows its good quality. The research result can also be applied to the advanced database systems and the multidatabase systems where the conversion function defined for the need of schema integration can be considered a type of foreign functions.

We consider processing entity join queries in a wide area multidatabase environment where the query processing cost is dominated by the cost of data transmission. An entity join operation "integrates" tuples representing the same entities from different relations in which inconsistent data may exist. The semijoin technique has been successfully used in a distributed database system to reduce the cost of data transmission. However, it cannot be directly applied to process the entity join query. An extension of the traditional semijoin, named extended semijoin is proposed to reduce the cost of data transmission for entity join query processing in a wide area multidatabase environment.