Optimising the distributed execution of join queries in polynomial time

It is proposed that an optimal strategy for executing a join query in a dis tributed database system may be computed in a time which is bounded by a po lynomial function of the number of relations and the size parameters of the network. The solution so unveiled considers both the transmission costs an d the processing costs incurred in delivering the required result to the us er that issued the query. The query specifies that several relational tables are to be coalesced and presented to the appropriate user. Undertaking this task demands the utilis ation of limited system resources, so that a strategy for fulfilling the re quest that imposes minimal cost to the system should be devised. Both the p rocessor sites, and the communications links that interconnect them, are ut ilised; an optimal strategy is one that minimises a weighted sum of process ing and data transmission costs. An integer linear programming model of this problem was originally proposed in [Ij; however, no suggestion was given as to how this model might be eff iciently solved. By extending the earlier analysis, the recursive nature of the join computation is revealed. Further investigations then produce a mo dified relationship amenable to algorithmic solution; the resultant procedu re has polynomial time and space requirements. (C) 1999 Elsevier Science Lt d. All rights reserved.