As an important part of service-oriented software engineering, service retrieval receives much attention from industry and academia, but which still leaves much to be expected: how the truth of the advertisement of service can be assured; how incomplete retrieval requirement can be dealt with; how a service fit a user?s need, existing methods based on ontology service model, which can be roughly classified as based on logic reasoning or similarity computing, still involve much effort of users to judge the fitness of the service in the result set. The paper introduces a new approach with Dominance-Based Rough Sets to obtain knowledge from past applications of services to deal with the three problems. Experiments verify the efficiency of the approach introduced in the paper.