The challenge of providing adequate notions for semantic equivalence constitutes an important research subject in many areas. In federated databases or data warehouses, for example, data from heterogeneous sources need to be integrated within one schema. Amongst other problems, schema integration has to deal with synonyms and homonyms (Rahm & Bernstein, 2001); i.e., equivalent attribute labels describing different data, or attributes with different labels but describing same data. The capability of the integration process to handle such cases is crucial for its success.
1.1 Problem Statement
Similar problems emerge when designing distributed processes as can be found in inter-organizational partner settings. As an example consider a collaboration between partners from the US, India and Germany, which shall be implemented as Web service choreography. At least, we need to translate Web service labels between the service compositions of the partners. Still, such language-related aspects can be easily handled using ontologies since it can be taken for granted that service labels confirm and bestaetigen (German term for confirm) are homonyms. However, in many applications such knowledge is not at hand. One important use case is the mining of (completed) executions of service compositions and service orchestrations respectively; i.e., techniques to derive composition schemas from execution logs (van der Aalst & Verbeek, 2008). Since there is no a-priori knowledge on such logs, basically, it cannot be taken for granted that Web services with equivalent labels are equivalent themselves. Regarding our example, service confirm might have a different “meaning” depending on whether it is performed by a manager or a secretary. Obviously, we also need to consider information about the context of a service execution when defining equivalence notions for Web services.
Another use case concerns the evolution of service compositions. Here, a composition schema is structurally changed by adding, deleting or moving steps (i.e., activities representing Web service executions). The ability to adequately support such changes has become crucial since a turbulent market and a continuously changing environment force any enterprise to quickly and correctly adapt their running business processes and service compositions, respectively (Mutschler, Reichert, & Bumiller, 2008). In this context, a service orchestration engine must enable both ad-hoc changes of single instances of a composition schema at runtime (e.g., to react on exceptions) and changes of a composition schema itself. The latter may have to be propagated to already running instances of a composition schema and become necessary, for example, when new regulations come into effect or the composition schema is redesigned (e.g., due to business reengineering efforts). If changes are concurrently applied at composition schema and composition instance level, however, it becomes crucial to carefully decide on the equivalence of the affected Web services. If, for example, two Web services with equivalent label are inserted at both schema and instance level, we have to decide on their actual equivalence in order to avoid duplicate insertions at the instance level afterwards (Rinderle, Reichert & Dadam, 2004a).