In this thesis, a new query processing strategy is proposed for a distributed join between two fragmented relations on a non-broadcast network. For the linear integer programming formulation in the literature, a reduction algorithm which effectively reduces the search space of the problem is proposed. In addition, a heuristic algorithm is proposed for this reduced problem. Finally, the heuristic algorithm is compared with the optimal algorithm using simulation study. Accoring to the simulation results, the proposed heuristic algorithm obtains optimal solutions for most queries (from 95% to 100%) with shorter execution time than the optimal algorithm.
