Service discovery over the Web is considered a crucial issue; in particular, flexibility of the discovery process, that is, the ability of recognizing not only exact matches between the requests and offers, but also partial ones, needs to be enhanced. We have defined a composite approach to flexible service matchmaking with different matching models. In this paper we present the novel difference-based matching model. The approach is based on an ontological framework adding semantics to service descriptions. Optimization and ranking techniques are provided.