- From: Michael Kifer <kifer@cs.sunysb.edu>
- Date: Thu, 24 Apr 2003 17:41:08 -0400
- To: Austin Tate <a.tate@ed.ac.uk>
- Cc: www-ws@w3.org
>>>>> "AT" == Message from Austin Tate <<a.tate@ed.ac.uk> > writes:
AT> At 08:21 PM 22/04/2003 -0400, Michael Kifer wrote:
>> 1. Partial modeling using constraints.
>> The constraints can be pre/post conditions, but also dependencies among
>> actions (temporal, causality, etc.)
AT> This is an underlying abstraction I am keen on and that I think has very
AT> nice extendability yet provides a very simple underlying
AT> abstraction - one
AT> we know that NIST PSL in particular can be built over.
To give more context, I am attaching my original message to which Austin is
replying.
AT> Processes and their description can be described as a set of
AT> constraints on
AT> the whole space of potential behaviours/processes of interest.
AT> This is anchored by describing a process model as including
AT> a specific set
AT> of activities (think of this as "include a specific activity"
AT> constraint).
AT> Activities each have an associated begin and end time point (also
AT> describing an interval over which they occur).
AT> The activities are described by a verb along with 0 or more arguments
AT> which can refer to any of a set of process-relatable objects and
AT> features in the domain.
AT> A set of constraints of any conceivable kind can be stated for the
AT> activities. This provides the generality.
This is all good, but there is a feeling that it is also needed to be able
to model processes as executable specifications -- at least to a certain
level of detail.
--michael
------------------------ original message ------------------------
Process Modeling for SWS: What might be needed and why
======================================================
We can identify two different, but related, ways of modeling processes that
might be useful for SWS:
1. Partial modeling using constraints.
2. Complete modeling as an executable specification.
Ideally we would like the SWSL to be able to handle both aspects. Some
formalisms can do this (e.g., Concurrent Transaction Logic). But it is
also possible to use one formal approach to do (1) and another (2) as long
as they are integrated in a way that serves our purposes.
1. Partial modeling using constraints.
The constraints can be pre/post conditions, but also dependencies among
actions (temporal, causality, etc.)
The need for modeling using constraints arises in the following two
situations (amont others -- please supply):
a. The user want to query services based on the constraints
that the services promise to obey.
For instance, in a travel reservation scenario, one might want
to select a service that promises that the service fee is not
charged to the credit card until booking is confirmed.
b. The user might want to impose additional constraints on a
service that doesn't advertise those constraints, but might be
willing to live by them.
This can be viewed as a form of negotiation. For instance, one
might not be able to find a service that promises not to charge
the credit card before booking is confirmed. In this case, the
user can try to invoke another service and attach a desired
constraint. The service may or may not agree to execute under
that constraint. (For instance, if the service is specified
declaratively then one of the execution traces might satisfy the
constraint and the service can be made to respect the constraint
without compromising its internal logic.)
c. Imposition of constraints on the service or by the service can
be viewed as a form of negotiation.
There are several works that study constraints on workflow execution:
M. Singh's algebra, Davulcu et al.'s logical constraints. etc.
These constraints are in the category of temporal and causality constraints.
Developing more intuitive language for specifying these constraints
based on those formalisms is not hard.
For negotiation some form of deontic logic could be a thing to look at.
(Need use scenarios.)
Examples of temporal and causality constraints:
events A and B must both occur.
if event A occurs then event B or C must also occur (before or after B).
if both A and B occur then A must occur before B.
The other kind of constraints deal with resource allocation. For
instance, one might want to see if a service can execute under certain
cost constraints (time is viewed as one kind of a cost).
Resource allocation constraints are very different from causality
constraints, and the formalisms for handling them are quite different,
too.
Rules can also be used as constraints, but we must design the language
carefully to make verification of constraints feasible.
2. Complete modeling as an executable specification.
The need for this latter kind of modeling for SWS is much less
clear. This is the domain of WS Choreography and we need to better
understand how these things can be useful in conjunction with semantics
and such.
The following reasons can be given:
a. A complete declarative specification of the process model might
enable us to tell if a process can be scheduled subject to user's
constraints and in this way satisfy user's requirements (see 1b).
There are works that discuss workflow scheduling under constraints.
b. This will enable automatic creation of composite services
based on user specification of what she wants (probably will
need a "query" language for that?). Such a composition can be
supported by planners.
c. We can provide a *simple* language for process composition
that will also be useful for deploying simple, but useful services.
Rationale: Although this goa interferes with Choreography
(service composition language) and, in part, with Orchestration
(programming of individual services), the
Choreography/Orchestration languages are very complex and have
no useful semantics. They are largely incompatible with each
other and none became truly standard (despite the relatively
long efforts of the Workflow Management Coalition).
The paper http://citeseer.nj.nec.com/vanderaalst03dont.html
nicely summarizes the unsatisfactory state of affairs in this
area.
Even if there were just one standard, the language would be too
complex for any kind of non-trivial reasoning. So, we need to
have good reasons (from SWS point of view) to plunge into this
controversy.
Meanwhile, the proposal is to provide a simple, limited
language, which can be useful in practice and would be supported
by most industrial proposals, like BPEL4WS, WSCI, BPML as well
as the formal methods, like Petri Nets, Golog, Concurrent
Transaction Logic, etc. In this way the language can have
several different implementations and might be widely accepted.
What such a language might contain:
Composition sublanguage:
------------------------
i. Sequential composition of processes: a,b
ii. Parallel composition of processes: a|b
(a|b),c means execute a and be in parallel.
Then execute c after both a and b are done.
iii. Choice: a\/b
Means execute a or b
iv. Preconditions (like in STRIPS)
v. Postconditions.
For instance, pre, a, post means check "pre".
If it is true in the current state, execute action "a".
In the resulting state check "post".
If true, the whole thing is done. If "post" is not
true, then rollback the execution of a.
vi. Process definition.
Like the subroutine mechanism. The ability to define
a composite process and use it as a component in
defining another, even more complex, process.
vii. Possible specification of transactional isolation.
This can be useful if one needs to ensure
transactional behavior of a part of the service.
Constraints sublanguage:
------------------------
i. A sublanguage for temporal and causality constraints
Probably at the level of Singh's algebra and Davulcu
et al. languages. (See examples of such constraints
above.)
ii. A sublanguage for resource allocation constraints
(time, money, etc.)
Probably something like CLP (Constraint Logic
Programming). There has been some work on that in
the context of workflow management.
These limited tools are sufficient for building very complex
processes.
Here is an example in the logic programming style, which captures
both the control flow and the data flow.
To buy a product, pay a fee to the broker and the cost of the
product to the seller. These steps can be done in parallel:
transfer(Fee,Buyer,Broker) | transfer(Cost,Buyer,Seller)
This can be regarded as a composition where the same service
(money transfer) is invoked twice. We can elaborate on this
service as follows (where "," denotes sequential composition):
transfer(Amount,Account1,Account2) :-
withdraw(Amount,Account1), deposit(Amount,Account2).
withdraw(Amount,Account):-
balance(Account,Balance), Balance >= Amount, % Precondition
change_balance(Account,Balance,Balance-Amount).
deposit(Amount,Account) :-
balance(Account,Balance), Amount >= 0, % Precondition
change_balance(Account,Balance,Balance+Amount).
change_balance(Account,Balance1,Balance2) :-
delete(balance(Account,Balance1)),
insert(balance(Account,Balance2)).
In the above, delete and insert are actions that change the
database. The predicate "balance" is a database query. The
above example illustrates the use of preconditions,
parallel/serial composition, and process definition. It is an
actual program in Concurrent Transaction Logic. This logic can
also be used to handle temporal/causality constraints, message
passing, and its combination with CLP can handle resource
allocation constraints.
Received on Thursday, 24 April 2003 17:52:42 UTC