W3C home > Mailing lists > Public > www-ws@w3.org > April 2003

Re: Partial modeling using constraints

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
Message-Id: <20030424214113.6BFD51EA32A@lmcgw.cs.sunysb.edu>

>>>>> "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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 3 July 2007 12:25:41 GMT