This paper studies the problem of query optimization in a distributed database. Assuming a linear additive cost function (in volume of data moved), we present a fast algorithm for finding the optimal program that answers a class of common queries, called chain queries. The key to the problem formulation and to the derivation of an efficient algorithm is an elegant parameterization of the database state against which the query is to be answered. This parameterization then enables us to characterize the set of potentially optimal programs, which in turn leads to a fast dynamic programming algorithm. Since in practice the needed parameters may not be available to the database system, we also discuss how to deal with partial parameterizations of the database state.

The semi-join is a relational algebraic operation that selects a set of tuples in one relation that match one or more tuples of another relation on the joining domains.Semi-joins have been used as a basic ingredient in query processing strategies for a number of hardware and software database systems.However, not all queries can be solved entirely using semi-joins.In this paper the exact class of relational queries that can be solved using semi-joins is shown.It is also shown that queries outside of this class may not even be partially solvable using "short" semi-join programs.In addition, a linear-time membership test for this class is presented.