Web service interactions have triggered the initiative to identify and solve mismatches from a behavioral aspect. However, current approaches are limited because they mainly focus on control- ow and largely ignore data- ow. Such ignorance may cause unexpected or wrong, even unsupported interactions. To address these problems, we propose a scenario-view based approach, which considers both control- ow and data- ow, to support Web service interactions. We rstly generate scenarios and views for describing a public process. Then, the degree of compatibility of two public processes is computed based on pairwise compatibility of their views. A process mediator is generated for compatible public processes, and thus an interaction is carried out despite mismatches exist among them. This novel approach will bene t service modelers and users not only for a better understanding of public processes, but also for improved capability to identify and solve mismatches, which will further facilitate Web service interactions.
Nowadays, enterprises are able to encapsulate (parts of) their business processes
and publish them as Web services [
Current approaches for checking compatibility, e.g. [
To address these problems above, we propose a scenario-view based approach
to support mediated service interactions:
{ We automatically generate scenarios and views for a public process
considering both control- ow and data- ow. A scenario is a complete execution path
[
To the best of our knowledge, our scenario-view based approach is the rst
study to support mediated service interactions considering both control- ow and
data- ow. Because our approach focuses on a behavioral aspect of Web services,
it is very useful to support intra-/inter-organizational work ow cooperation [
Our work in this study will be presented as follows. A motivation example is presented in Section 2. A de nition and graphical notations for a public process is shown in Section 3. Scenarios and views are generated for describing a public process in Section 4. Then compatibility of public processes is computed based on pairwise compatibility of their views in Section 5, and process mediators are presented in Section 6. Finally, related work is discussed and a conclusion is drawn in Section 7 and 8.
ReqA expects a discount from ToyS. However, Figure 2 shows a snippet of an interaction that ReqA gets a normal price: "S: Customer Information " is sent out by ReqA. But for some reasons, it is later than "S: Toy Items " of t1. For his side, ToyS waits "R: Customer Information " for t2 after receiving "R: Toy Items". If t1 > t2, ToyS improperly assume that ReqA should not send "S: Customer Information" and then give a normal price.
If there is a process mediator in the middle, ToyS will be noti ed by the process mediator that "S: Customer Information " has been sent out by ReqA. Then ToyS will wait for "S: Customer Information " and give a discount.
This example indicates that, without the support of a process mediator, Web
services may carry out an unexpected, or wrong, interaction.
According to current approaches, e.g. [
If a process mediator exists in the middle considering both control dependencies and data dependencies, a successful interaction is possible. To do this, ToyS is noti ed by the process mediator that ReqB will not send "S: Customer Information" before receiving "R: Price", and thus a null message is sent from the process mediator to ToyS as "S: Customer Information ". Then ToyS can executes the following activity "S: Price". However, ToyS will update this message whenever "S: Customer Information " is provided by ReqB. Figure 3 shows how this mediated service interaction is carried out. For simplicity, activities that do not contribute to this interaction are not presented. Our motivating example shows that current approaches are insu cient to check compatibility of public processes, and are limited to support mediated service interactions. Their main shortcoming is that: they only consider control dependencies, but largely ignore data dependencies. As illustrated in the toy shop shown in Figure 1-c, a sequence constraint between "R: Customer Information " and "S: Price" speci es a control dependency. However, a data dependency between them is optional. This feature causes that a direct service interaction shown in Figure 2 is unexpected or wrong, and a mediated service interaction shown in Figure 3 can be successfully carried out. 3
Below we give a de nition for a public process where messages and guard functions are the rst-class elements.
De nition 1 (Public Process). A public process p is the ve-tuple (MSG, ACT, CNT, GRD, ARC), where MSG=fmsgg is is a nite set of messages, ACT=factg is a nite set of activities for sending or receiving messages, CNT=fStart, Failure, End, Xor Split, Xor Join, And Split, And Joing are control elements, GRD=fgrdg is a nite set of guard functions related to control elements, and ARC=farcg is a nite set of arcs that connect activities and control elements.
We assume that one message contains one data. Both activities and control elements are the nodes in a public process. Figure 4 shows six basic graphical notations to model a public process. These notations are supported by JGraphPad 1, based on which our prototype is implemented. In addition, our notations can model six ordering structures speci ed by WfMC 2.
2 http://www.wfmc.org/standards/docs.htm.
We rstly generate all scenarios for a public process. Data dependencies are presented as a data dependency graph, which presents a nite set of mandatory or optional data dependencies in a public process or a scenario. However, a data dependency is redundant and can be safely removed if it is implicitly speci ed by other data dependencies. A minimal data dependency graph is generated where there are no redundant data dependencies. Then we propose three reduction rules to identify and remove unnecessary control dependencies speci ed by sequence, And and Loop blocks in a scenario. With the help of a minimal data dependency graph, we generate a view for a scenario by applying three reduction rules recursively. A public process includes a nite set of scenarios. A scenario has a corresponding view which represents this scenario for analysis purposes. A public process can be described as a nite set of views. For the sake of space limitation, our algorithms are not presented. 4.1
Only one path of a Xor block can be enabled in a given execution depending on the status of guard functions. Similarly, only one branch can be enabled in a given execution for a Branch control elements that contribute to exclusive relation. Then, a nite set of scenarios can be generated for a public process.
De nition 2 (Scenario). A scenario sce is a complete execution path for a public process p, which is de ned by the ve-tuple (M SGsce, ACTsce, CN Tsce, GRDsce, ARCsce) generated from those of p. For any node in a scenario except Start, Failure/End, And Split, And Join, and Branch control elements for modeling loops, it has only one entering and one leaving edge.
There are two scenarios for ToyS, and Figure 3-a shows one of them. There are two scenarios for ReqB, and Figure 3-b shows one of them. 4.2
Similar as [
De nition 3 (Data Dependency Graph). A data dependency graph dg for a public process (MSG, ACT, CNT, GRD, ARC) is a directed, connected and acyclic graph, which is de ned by the two-tuple (DAT Adg, DEdg), where DAT Adg = fdatag is a nite set of data generated from MSG, which are the nodes in this graph. DEdg = DEd(Mg) [ DEd(Og) a nite set of edges, which are the direct links in this graph specifying the dependency relations among data. DEd(Mg) is for mandatory dependencies, and DEd(Og) is for optional dependencies.
One data is regarded as dependent on another data if (1) a direct link connects them (directly dependent), or (2) several direct links form a path leading from one data to another (indirectly dependent). Then a data dependency graph can be represented as a nite set of dependent relations. A data dependency graph is called functionally equivalent to another data dependency graph if any dependency relation in one data dependency graph can exist in another data dependency graph directly or indirectly.
De nition 4 (Minimal Data Dependency Graph). A minimal data dependency
graph dgmin: (DAT Amin, DEmin) is generated from a data dependency graph
(DATA, DE), where DAT Amin = DATA, DEmin DE. (DAT Amin, DEmin)
is functionally equivalent to (DATA, DE), but 8 de 2 DEmin: (DAT Amin,
(DEmin fdeg)) is not functionally equivalent to (DATA, DE).
Control- ow structures of a scenario specify execution orders of activities.
However, the execution of some activities may not follow these orders. An example
is "R: Toy Items" and "R: Customer Information" in Figure 3-a since they
are not data dependent on each other. Thus, we present three reduction rules
to identify and remove unnecessary control dependencies speci ed by Sequence,
And and Loop blocks. In a scenario, only one path is allowed for a Xor block
and a branch for a Branch control element that speci es an exclusive relation.
They are functionally equivalent to Sequences. We follow [
Rule 1 (Sequence). A sequence of activities are folded into a single node if data dependencies among them are not mandatary.
Rule 2 (And). An And block with its And Split and And Join is folded into (1) a single node if all activities in each path can be folded into a single node or (2) a sequence of nodes otherwise.
The rule for And block is shown by Figure 6-a and 6-b. An And block suggests that all its paths are executed in parallel. However, there are no control and data dependencies among activities of di erent paths. This means that an And block can be converted into a sequence of activities as shown in Figure 6-c.
Rule 3 (Loop). A Loop block is folded into (1) a single node if the Loop body can be folded into one node or (2) a sequence of nodes otherwise. Guard functions are de ned in the last node to specify the exit conditions of the Loop block. There are possibly multiple instances for any node during execution phases.
This rule is shown by Figure 6-d and 6-e. A Loop block iterates over one or
several nodes until its exit conditions are satis ed, but it doesn't iterate forever
in real cases. As suggested by [
De nition 5 (Checkpoint). A checkpoint cp includes a nite set of contiguous activities in a scenario in which data dependencies among them are not mandatory. A checkpoint is de ned by the four-tuple (label, ACT, DATA, GRD), where label for its label. ACT for activities, DATA for required data, and GRD for guard functions, are generated from those of the scenario.
Required data are generated with the help of the minimal data dependency graph of a scenario. E.g., according to Figure 5, "R: Toy Items" is required to "S: Price", but "R: Customer Information" not.
De nition 6 (View for a Scenario). A view vw for a scenario (M SGsce, ACTsce, CN Tsce, GRDsce, ARCsce) is the ve-tuple (M SGvw, CP, cp0, cpf , DEvw). M SGvw = M SGsce, CP=fcpg is a nite set of checkpoints, cp0 is the initial checkpoint, and cpf is the nal one, while DEvw = fdeg is a nite set of direct links connecting checkpoints to specify data dependencies among them.
With the help of a minimal data dependency graph, reduction rules can be applied to a scenario recursively until no nodes can be folded anymore. Then checkpoints can be generated and a view can be derived. 5
In this section, we focus on the compatibility of two public processes since the majority of interactions are related to two partners, and an interaction involving multiple partners can often be decomposed into several pairwise interactions.
Compatibility aims to check whether two public processes can carry out a successful interaction. Before discussing compatibility, we present what an interaction is, and how an interaction is regarded as successful. Then we compute the degree of compatibility of two public processes based on pairwise compatibility of their views. Due to the space limitation, our algorithms are not presented. 5.1
An interaction means that several public processes, if compatible, can be composed into a complex one for achieving a given goal. Since a scenario represents a complete execution path of a public process, an interaction of public processes is actually an interaction among scenarios of these public processes.
A scenario, or a public process, speci es a set of messages sent to or received from its potential partner(s) following a pre-de ned order. Therefore, an interaction can be regarded as a ow of messages exchanged among scenarios. If this ow of message can lead each scenario from its Start control element to its nal control element, this interaction is regarded as successful. Some mismatches may exist among these scenarios. However, the mismatches are resolvable and can be handled by a process mediator. 5.2
For any two scenarios, if a ow of messages exchanged between them can carry out a successful interaction, this indicates that this ow of messages can lead their views from their initial checkpoints to their nal checkpoints. In this case, these two views are regarded as compatible. On the other hand, if two views are not compatible, these two views cannot interact since at least one checkpoint in a view cannot be guaranteed.
Based on pairwise compatibility of their views, we can de ne the degree of compatibility for two public processes p1 and p2. We assume that there are n1 views in p1. For a view vi (1 i n1) in p1, we de ne a function comp(vi j p2) to specify whether there is a compatible view in p2 if comp(vi j p2) = 1, or comp(vi j p2) = 0 otherwise. Thus, the degree of compatibility for p1 to p2 is: Compatibility(p1; p2) = (1) P1n1 comp(vi j p2) n1
Compatibility at a view level is a symmetric relation. However, compatibility at a public process level is an antisymmetric relation, and Compatibility(p1; p2) and Compatibility(p2; p1) are often di erent. Based on the degree of compatibility, we de ne three classes of compatibility for two public processes p1 and p2: { No compatibility if Compatibility(p1; p2) = 0. { Partial compatibility if 0 < Compatibility(p1; p2) < 1.
{ Full compatibility if Compatibility(p1; p2) = 1.
No compatibility means that two public processes cannot interact in any case, and full compatibility means that one public process can interact with another in any case, while partial compatibility means that one public process can interact with another in at least one but not all cases.
ToyS and ReqB are fully compatible with each other. Since there are two views for ToyS and two views for ReqB, and any view in ToyS has a compatible view in ReqB and vise versa. 6
A process mediator aims to facilitate an interaction if mismatches exist among public processes. Since how to generate process mediators is our ongoing work, in this section, we present our strategies: { There is a space for a process mediator, in which each public process has a sub-space for saving messages. Public processes do not communicate with each other directly. Instead, they send or receive messages to or from a process mediator. This means that production and consumption of messages are time-independent. { For any message sent by one public process, (1) a process mediator immediately forward it to other public processes that are ready to receive it, and (2) a process mediator checks whether it is potentially expected by other public processes in the future. If yes, the process mediator saves this message for these public processes for possible later usage.
It is possible that a message is consumed by several public processes. However, if no public process interests in this message now and in the future, it is dropped o immediately and silently. { In case that a message is expected by a public process and this message is not available in its sub-space. A process mediator will check whether this message is sent out by other public processes already. If yes, this public process blocks and waits until this message is available. { In case that all public processes are expecting to receive messages and thus an interaction blocks. A process mediator will check each public process: whether data dependencies between current activities and their following activities are not mandatory. If true, the process mediator will generate a null message (or an ACK message if acknowledgement is needed) for this public process to execute current activities. 7
We discuss the related work from the following four aspects: analysis of public processes, compatibility, process mediation and service interaction.
Analysis of public processes: This aspect includes: Control- ow based
methods [
Compatibility: In [
Process mediation: There are mainly two kinds of approaches: in [
Service interaction: In [
In this paper, we rstly identi ed that, without a process mediator, some Web service interactions could be unexpected or wrong, and some could fail. We also revealed that current approaches are insu cient to check compatibility and to support process mediators because they mainly focus on control- ow and largely
4 http://www.wsmx.org/. ignore data- ow. To solve these problems, we have proposed a novel approach to automatically generate scenarios and views for describing public processes, to compute the degree of compatibility of public processes based on pairwise compatibility of their views, and to generate process mediators for supporting mediated service interactions.
We have implemented the prototype to generate scenarios and views for
public processes, and to compute the degree of compatibility. Furthermore, we
propose to support replacement [
Acknowledgments. The work presented in this paper was supported (in part) by the EU funded TripCom Speci c Targeted Research Project under Grant No. FP6-027324, and (in part) by the Lion project supported by Science Foundation Ireland under Grant No. SFI/02/CE1/I131.
We thank Sami Bhiri and Laurentiu Vasiliu for their continuous discussion and valuable comments on purging research problems and solutions.