This paper aims to provide a service-oriented data integration solution over data Grids for cases where distributed data sources are partitioned with overlapping sections of various proportions. This is an interesting variation which combines both replicated and partitioned data within the same data management framework. Thus, the data management infrastructure has to deal with specific challenges regarding the identification, access and aggregation of partitioned data with varying proportions of overlapping sections. In order to provide a solution we have extended a well-known data access and integration middleware, namely Open Grid Services Architecture-Data Access and Integration Distributed Query Processing (OGSA-DAI DQP), with distributed query processing facilities, by incorporating the new 'UnionPartitions' operator into its algebra in order to cope with various unusual forms of horizontally partitioned databases. Our solution extends OGSA-DAI DQP in two aspects: (1)a new operator type is added to the algebra to handle the union of the partitions with different characteristics, and (2)OGSA-DAI DQP Federation Description is extended to include some more metadata to facilitate the successful execution of the newly introduced operator. (C) 2010 Elsevier B.V. All rights reserved.