Abstract: In the process of query in Deep Web data integration system, it is hard to avoid the so-called failed query that brings unsatisfactory result. So it is more cooperative to modify the raw query to return non-empty result set than to notify the user that there is no result corresponding to the query at all. Inspired by the observations and analysis on deep Web, a query relaxation solution applied in a deep Web data integration system is proposed in this paper, in which, all the Deep Web sources are grouped based on their query interface attributes and constructed as a global database relationship graph (DRG), the global database relationship graph (DRG) is transformed to database relationship graph fitting a specified query, and then the query is relaxed and executed based on the DRG. However, because of query relaxation the amount of the results from the data sources may be very large, and part of them may be not similar to the user’s query. Therefore after receiving the results from the data sources, a part of the results is first selected by using the skyline method, and then is sorted based on the similarity between the results and the user’s query, Finally the results satisfying the user’s requirement are returned to the user. Experiments demonstrate the availability of the query relaxation strategy.