Optimal distributed execution of join queries (Q1328829)

The author D. J. Reid solves the problem: how to execute a special class of queries in a distributed computer system? The queries are moved to contain the join operation only and are presupposed to compose a chain. That is the relations to be join can be arranged \(r = \{r_i \mid i = 1, \ldots, m\}\) such that the corresponding schemes \(R_i\), \(R_{i + n}\), \((i = 1, \ldots, u - 1)\) have attributes in common. The distributed network is represented by a directed graph, with a linear cost function of the amount of data sent and coefficients for the capacity limit of amount of data transmitted between two nodes. Each node (site) has allocated a subset of the relations named in the query. The processor cost are negligated. The author developed a solution of the above mentioned problem based on a tree search algorithm. The algorithm is outlined in pseudocode. It belongs to linear integer programming. Problem size and efficiency are considered. Because of the strong restrictions to the considered queries the results are especially of theoretical interest. The author intends to generalize his results in considering the costs of computation at processor facilities and the response time in answering a query.