The explosion of digital data and the dependence on data-intensive services have been recognized as the most significant characteristics of the decade. Providing efficient mechanisms for optimized data-intensive services will become critical to meet the expected growing demand. In order to create a cost minimizing data-intensive service composition solution, we design two steps and two negotiation processes over the lifetime of a data-intensive service composition. The solution for the first step is presented in this paper. The proposed service selection algorithm is based on a modified genetic algorithm, which some modifications of crossover and mutation operators are adopted in order to escape from local optima. The performance of the algorithm has been tested by simulations.