This chapter explores new trends of query relaxation strategies that allow to implement a cooperative query processing paradigm. This new paradigm is based on the belief that the user has an idea of what he/she wants and the system has to automatically lead him/her to formulate meaningful queries by relaxing query constraints. Three kinds of query relaxation mechanisms are investigated: semantic, structural and topological query relaxation. Moreover, as similarity is an important, widely used concept in the co-operative query processing since it supports the identification of objects that are close, we intend to give an extensive overview of existing similarity definitions and methodologies for evaluating it.