Nowadays, Web services are emerging as a major technology for achieving automated interactions between distributed and heterogeneous applications (Benatallah, Sheng, & Dumas, 2003). Various technologies are behind this achievement including WSDL, UDDI, and SOAP1. (Curbera, Duftler, Khalaf et. al. 2002) These technologies aim at supporting the definition of services2, their advertisement, and their binding for triggering purposes. The advantages of Web services have already been demonstrated and highlight their capacity to be composed into high-level business process (Benatallah et al., 2003). Usually, composite services (CS) denote business processes and are meant to be offered to users who have needs to satisfy.