Web service selection has been a challenging task for automated workflow composition. This is mainly due to the heterogeneity of the web service structure, non-standardization of registry format and complexity in capturing the semantic part of the web service functionalities. Relation-based Case Retrieval (RCR) establishes the relationship between cases and the web service invocation information. The cases contain the business proposals and the business operations in which they are measured using similarity function. RCR builds the cluster information of the cases that is able to 1) search replacement for the unavailability of the web services, 2) find dissimilarities in the repeated requests and 3) determine partiality in matching. RCR approach allows the retrieval of web services independently from the semantic and syntactic description of web service structure or registry format.