XML Based Schema Definition for Support of Inter-organizational Workflow W.M.P. van der Aalst1,2 and Akhil Kumar1,3 1 College of Business and Administration, University of Colorado, Campus Box 419, Boulder, CO 80309-0419, USA. 2 Faculty of Technology and Management, Eindhoven University of Technology, PO Box 513, NL-5600 MB, Eindhoven, The Netherlands. 3 Database Systems Research Department, Bell Laboratories, 600 Mountain Avenue, Room 2A-406, Murray Hill, NJ 07974. E-mail: [email protected],[email protected] Abstract The full potential of the web as a medium for electronic commerce can be realized only when multiple partners in a supply chain can route information among themselves in a seamless way. Commerce on the Internet is still far from being "friction-free" because business partners cannot exchange information about their business processes in an automated manner. In this paper, we propose the design for an eXchangeable Routing Language (XRL) using XML syntax. XML (eXtendible Markup Language) is a means for trading partners to exchange business data electronically. The novel contribution of our work is to show how XML can also be used to describe workflow process schemas to support flexible routing of documents in the Internet environment. The design of XRL is grounded in Petri nets, which is a well- known formalism. By using this formalism, it is possible to analyze correctness and performance of workflows described in XRL. Architectures to facilitate inter-operation through loose and tight integration are also discussed. Examples illustrate how this approach can be used for implementing inter- organizational electronic commerce applications. As a proof of concept we have also developed XRL/flower, a prototype implementation of a workflow management system based on XRL. 1. Introduction With the rapid expansion seen in electronic commerce1, there is a major need for infrastructures and frameworks that can be used to implement inter-organizational applications. In particular it is essential to provide support for routing of documents across organizations in a standardized and yet flexible manner to enable open electronic commerce [18,19,26,27,33,36,53]. Developing more homogeneous languages for various electronic commerce activities [21] is one way to facilitate increased productivity and interoperability. In this paper, we describe an architecture and a language called XRL (eXchangeable Routing Language) that provide support for routing of workflow among trading partners for Internet- based electronic commerce services. 1 In 1998, about $ 43 billion worth of business was done over the Web. This volume was projected to increase to $1.3 Trillion by 2003. 1 Current workflow products are generally intra-organizational and based on centralized architectures. Therefore, they typically lack scalability and are also not very useful for implementing inter- organizational applications [1,4,5,6,36]. Moreover, these systems use propriety languages for specifying workflow processes. Despite efforts by the Workflow Management Coalition (WfMC, [30]), a lingua franca for workflow management is lacking. The Workflow Process Definition Language (WPDL) of the WfMC has no formal semantics, i.e., the dynamics of many of its constructs are ill-defined, and most systems only support a subset of WPDL. The standard proposed by the WfMC for interoperability among different workflow systems (Wf-XML [50]) is based on WPDL and traditional centralized architectures. Such an approach does not address some of the fundamental problems related to cross-organizational, highly-dynamic workflows. The only way to support such workflows is for each organization to have a common understanding for the workflow processes at hand. Therefore, we propose a new language which enables the easy and unambiguous exchange of process information, i.e., a lingua franca for cross- organizational workflow. An inter-organizational workflow involves communication between two (or more) parties with different information systems. Although various suppliers of products and services, such as Dell, Federal Express, etc., already make order tracking information available on their web sites, the next level of customer support will allow customers to perform more detailed order status inquiries, and to make changes dynamically to their orders (e.g., "change the cd-rom in my laptop order to a DVD"). For instance, a customer should be able to find out why his or her order is delayed, and what are possible alternatives for expediting it (perhaps, the delayed component or feature is not so important and can be omitted, or a substitute can be used, etc.). Process information is also very useful because it encapsulates the business rules of an organization. For instance, one supplier may expect to receive payment after delivery, while another may have the opposite policy. Therefore, a customer who deals with both suppliers, and does not pay careful attention to these rules, may be held up waiting for the shipments to arrive not realizing that the payment has not been made in one case. Currently, such misunderstandings are prevented by paying careful attention to business rules of organizations, which are available in hardcopy form. Often considerable manual interaction between personnel of the buyer and supplier organizations is required to parse and understand these rules. This is time consuming and expensive, and incurs delays, especially in setting up new arrangements between two partners. We anticipate that friction-less e-commerce will only be possible if such arrangements can be established on the fly, in an automated manner. This requires that each partner make its processes (at least, selectively) transparent to its other partners (e.g., the process schema would show whether payment occurs prior to, or after, delivery). Inter-organizational workflows are problematic because the process information of each partner is hidden from other partners, and there is no easy or common way of describing such information. While the 2 partners are able to exchange transactional data based on prior arrangements, through means such as EDI (described shortly), it is not possible to exchange detailed process level information. Such information is crucial for close interaction and cooperation to enable frictionless e-commerce. XML and EDI are two technologies for data exchange. While EDI is a well-known standard for data exchange, XML is not a standard in the same sense; instead, it has the capability to define the contents of documents through a set of elements or tags. EDI is based on the notion of transaction sets, which are standard, formatted documents such as a purchase order, delivery agreement, etc. Each transaction set defines the precise structure of the corresponding document, and is used to exchange business information between partners. XML, on the other hand, is designed to be "extendible" by allowing users to define various entities on a form such as, name, address, price, quantity, etc. as tags or elements, thus creating user-defined forms. The structure or schema of an XML document is described by its Document Type Definition (DTD). When setting up a relationship through EDI or XML, business partners must still agree before hand on the sequence in which these documents are exchanged, and what action a partner must perform upon receiving a certain document. Partners must agree, for example, on how stock-outs will be handled, who specifies delivery dates and what is done if a delivery date cannot be met, and what is done if a trading partner specifies an improper product number or there is a disagreement on pricing. This is essentially process information, which is not automated in current solutions. These issues are typically agreed to outside of the electronic exchange and can cause significant problems if partners do not agree to them in advance. Our proposal in this paper is an attempt to extend data exchange technologies such as EDI and XML with the exchange of process information as well, by making inter- organizational workflows explicit. This is the main motivation for developing XRL. At the outset, it is important to clarify that XRL is not XML; rather, XRL uses XML syntax to define a DTD, consisting of a set of elements or tags for describing workflow applications. It consists of routing constructs that are used as building blocks to design routing schemas for inter-organizational applications. It is described in XML syntax because XML parsers are easily available and XML is rapidly becoming an international standard [15,39,52]. According to InformationWeek [24], a widely-read magazine, “As a basis for universal data interchange among companies, XML has permeated every sector of business, from aviation and accounting to weather and workflow.” Moreover, query languages for XML data (such as Xpath) are also becoming available; thus, if a workflow is described in XML, it can be queried [16]. In Section 7, we compare XRL with existing standards for workflow management (e.g. SWAP, JFLOW, and Wf-XML), and electronic commerce solutions (e.g., ebXML, OBI, xCBL, RosettaNet, UDDI, and OAGIS). Four important features of XRL should be noted. One core feature of XRL is that it provides a mechanism to describe processes at an instance level, i.e., an XRL routing schema describes the partial ordering of 3 tasks for one specific instance. Traditional workflow modeling languages describe processes at a class or type level [20,25,30,44]. However, in the context of inter-organizational workflow, it is unrealistic to assume that the different organizations share a common process model. Moreover, it should be possible to modify and migrate instances (or parts of instances) from one organization to another without prior agreement on the precise order in which tasks are executed. Therefore, while modeling at a schema level is still possible, instance level modeling gives additional flexibility. A second important feature is that XRL lends itself well to both distributed and asynchronous modes of operation. Section 3 will describe a distributed architecture, which is more scalable and reliable than a centralized one [12]. Moreover, in many real applications (e.g., in supply chain management [13,14,31]), asynchronous transmission of messages can be more reliable and efficient than synchronous transmission. A third feature is that the semantics of XRL are expressible in terms of Petri nets [7,11,17,41]. Such formal semantics allow for powerful analysis techniques, an efficient and compact implementation, interfaces to many existing tools, and, last but not least, an unambiguous understanding of XRL. As workflows get increasingly complex the need for tools for analysis and formal verification of workflows will assume even greater importance. A fourth important feature is the expressive power of the language, i.e., the ability to realize desirable routing constructs in a succinct and direct manner. In our research on workflow patterns [9,10], we compared the expressive power of many contemporary workflow management systems including COSA, HP Changengine, Forté Conductor, I-Flow, InConcert, MQ Series Workflow, R/3 Workflow, Staffware, Verve, and Visual WorkFlo using a set of workflow patterns (http://www.tm.tue.nl/it/research/patterns/). Based on the workflow patterns supported by these systems and their relative use in practice, we carefully selected the most relevant constructs for XRL. Note that the extendible nature of XRL allows for the addition of new constructs by simply adding the construct to the XRL DTD (see Appendix 1) and providing the corresponding Petri-net semantics (see Appendix 2). A prototype workflow management system named XRL/flower has been developed as a proof of concept. XRL/flower provides full support for the XRL language presented in this paper. This paper is organized as follows. Section 2 provides background material related to workflow support for electronic commerce. Section 3 gives an overview of the architecture based on the idea of routing slips. Next, Section 4 describes the various constructs of the XRL routing language. Then, Section 5 shows how XRL can be mapped into Petri nets. Section 6 illustrates the language with real examples and screenshots of our workflow management system XRL/flower. Finally, Section 7 discusses related work and Section 8 concludes the paper. 4 2. Basic Background and Motivation 2.1. Why use XML and what is XML? The Web has ushered an era of "any time, anywhere, any place" communication. Widely-accepted standards, like HTML, are crucial to using the Web to its full potential. However, HTML is a visual display and user interface standard. It allows a page to be created once and be displayed at different times by anyone with a browser. Since browsers have become universal, millions of people world-wide can have access to the same content within seconds of its creation. Clearly, although visual and user interface standards are important, they are insufficient for representing and managing data. Today, the Internet is primarily an access medium for text and pictures. There are no standards for intelligent search, data exchange, adaptive presentation, and personalization. As a next step what is required is a common way of representing data so that software can better search, move, display, and manipulate information hidden in contextual obscurity. HTML cannot do this because it is a format that describes how a Web page should look; it does not represent data. For example, HTML does not: • provide a standard way for a customer to send an order to a supplier. • specify a standard way for a doctor to send a prescription to a pharmacist. • enable a company to publish a catalog of products and prices in a standard way that allows a salesperson to work offline, show the catalog to clients, take orders, and upload those orders in a standard format. • describe an electronic payment in a form that any recipient can decode and process. • provide a standard way to search law libraries for all litigation documents about a certain topic. In short, while HTML provides rich facilities for display, it does not provide any standards-based way to manage data. This is where XML serves a useful purpose. XML is a markup language that allows users to define a set of tags, which describe the structure of a document [15,39,45,46]. For example, a user may specify tags for NAME, AGE, DEPARTMENT, EMAIL, etc. This logical structure may be stored either in the document file itself and/or in an associated file called the Document Type Definition (DTD) file [15] or the XML Schema (XSD) file [52], which is linked to the document file. This facilitates more precise declaration of content and more meaningful search results across multiple platforms. In addition, XML will enable a new generation of customized Web-based data manipulation applications. XML provides a structured representation of data that can be implemented broadly and is easy to deploy. XML is a subset of SGML (Standard Generalized Markup Language), modified and optimized for delivery over the Web. This standard has been defined by the World Wide Web Consortium (W3C) [15]. 5 XML, which provides a data standard that can encode the content, semantics, and schemata for a wide variety of cases, ranging from simple to complex, can be used to mark up a purchase order, an invoice, a payment advice, a doctor’s prescription, information about people and organizations, etc. Thus, XML ensures that structured data will be uniform and understandable across a variety of applications, vendors and customers. This resulting interoperability is kick-starting a new generation of business and electronic- commerce Web applications. XML is valuable to the Internet, as well as to large corporate Intranet environments, because it provides interoperability using a flexible, open, standards-based format, with new ways of accessing legacy databases and delivering data to Web clients. Applications can be built more quickly, are easier to maintain, and can easily provide multiple views on the structured data. XML has already opened up a wide variety of new uses, all based on a standard representation for moving structured data around the Web as easily as we move HTML pages today. While XML can help in exchange of semantic information, it still lacks routing information. Such information is critical to enable proper routing of a document within an organization and across organizations. Our proposal in this paper is to further use XML for not just data exchange but also for exchange of routing information. We view this as a natural evolution of XML, which will expand the Internet in much the same way that the HTML standard for displaying content did a few years ago. Therefore, in a simplistic way, one may think in terms of three evolutionary stages of Web development: Stage 1: HTML standard for visual display and user interface Stage 2: XML standard for data exchange within and among organizations. Stage 3: Add workflow features with routing semantics and enable interoperability. Therefore, while stage 2 is an important step towards data integration, our proposal aims towards tighter interoperability. In the next subsection we provide background on features of workflow systems, application areas where workflow support is required and the role XML can play. 2.2. Workflows in XML Workflows are used to represent business processes in a systematic manner. A typical business process consists of a series of tasks to be performed in accordance with coordination requirements that ensure that the workflow proceeds correctly. Some tasks have a sequential routing constraint between them, while others may be done in parallel. Moreover, a workflow should be able to select a path based on the result of a condition test. Finally, some workflows also allow for iteration so that work can be redone (for example in case of errors). Therefore, some basic coordination constructs that are present in most workflow systems are sequential routing, conditional routing, parallel routing, and iterative routing (see Figure 1). An OR-split is used to specify a choice among several alternatives; an OR-join specifies a node 6 where several alternative paths in the workflow process definition come together. The routing decisions in OR-splits are often based on data, such as whether a task was performed correctly, the age of a customer, or the contents of a letter from the customer. On the other hand, an AND-split and AND-join can be used to specify the start and end of multiple parallel paths. A B C D sequential routing B conditional routing A OR-split OR-join D C B parallel routing A AND-split AND-join D C OR-join OR-split A B C D iterative routing Figure 1: Four basic routing types using AND/OR and split/join building blocks Clearly any workflow language should support the four constructs shown in Figure 1. However, as shown in [9,10] these basic constructs are inadequate. More advanced constructs are needed to easily model and enact complex real-life workflows. In our research on workflow patterns [9,10], we compared the expressive power of some of the leading workflow management systems on the market. Using a set of workflow patterns we evaluated COSA (Thiel Logistik AG/Ley GmbH/COSA Solutions BV), HP Changengine (Hewlett-Packard), Forté Conductor (Forte/SUN), I-Flow (Fujitsu), InConcert (TIBCO), MQ Series Workflow (IBM), R/3 Workflow (SAP AG), Staffware (Staffware PLC), Verve (Verve Inc.), Visual WorkFlo (FileNET), and some research prototypes (cf. http://www.tm.tue.nl/it/research/patterns/ [10]). Based on the workflow patterns supported by these systems and their relative use in practice, we carefully selected the most relevant constructs for XRL. Petri nets allow for the modeling of the four constructs shown in Figure 1 and have been proposed for modeling workflow process definitions long before the term “workflow management” was coined (cf. 7 [17] for some historical remarks). However, we do not propose Petri nets as a modeling language. Instead we propose high-level constructs inspired by our research on workflow patterns [9,10]. Nevertheless, we provide a mapping from XRL to Petri nets. As a result, we can use the strong theoretical results from Petri nets, apply various analysis techniques, and use an efficient workflow engine based on Petri nets. For a more elaborate introduction to Petri nets and the application of Petri nets to workflow management, we refer the reader to [7,11,17,25,41]. Workflow management systems such as COSA, HP Changengine, Forté Conductor, I-Flow, InConcert, MQ Series Workflow, R/3 Workflow, Staffware, Verve, and Visual WorkFlo are not interoperable and they all use proprietary formats to represent workflow schemas. XML, which is rapidly becoming universal on the Web, can serve as a common language for unifying disparate workflows from different vendors and reconcile them. Three broad application areas in which support for workflows and inter-operability is important are: • Enterprise resource planning (ERP) applications (e.g., from Oracle, PeopleSoft, SAP, etc.) • Customer relationship management (CRM) applications (e.g., from Siebel, Clarify, etc.) • Supply chain management (SCM) applications (e.g., from i2, Manugistics, etc.) In all three areas, vendors are working hard to workflow enable their products. The kinds of problems that arise in supply chain management are especially suitable for use of workflow technology. The common aspects of these problems are multiple business partners, flow of information through exchange of documents, and need for complex coordination using some of the constructs discussed above. In the next subsection, we describe an example problem that exhibits the characteristics of supply chain problems. Later we will return to this problem to show how it can be solved using our framework. 2.3. Workflow in Mail Order Processing In this subsection, we describe an example of a workflow related to electronic commerce in some detail. This example will be used later to illustrate our techniques. The following description accompanies Figure 2, where the numbers denote the approximate sequence in which various steps are performed. Suppose that a customer places an order for three books with Amazon.com. Since these three books come from different publishers, Amazon in turn places three different orders (one for each book) with the publishers. Then Amazon must wait for confirmations from the publishers about whether they can deliver the books within the deadline specified by the customer. Moreover, the customer may also have stated conditions like "all or nothing" or "at least two out of three" etc. If the conditions stipulated by the customer cannot be met, then he/she must be notified accordingly. If they can be met, then Amazon must confirm the order with the publishers involved, and next find a shipper. The shipper coordinates the receipt of and onward delivery of the three different shipments from the publishers. Here again, several 8 situations can arise. The books are likely to arrive separately, possibly even on different days, and the shipper must determine whether to batch the order into one shipment or in multiple shipments as they arrive. (It is interesting to note that in general, there are 2n - 1 combinations of partial shipments.) Finally, billing must be handled. Since customers are normally billed upon shipment, the shipper must notify Amazon immediately after the shipment is sent, and Amazon or its billing company will bill the customer at this point. Again, billing can also be either batched, or done singly for each partial order that is shipped. This simple example illustrates the complexity that can arise in performing a simple workflow over the Internet. There are seven parties who have to coordinate among themselves in order to successfully complete the order. Other complications that can arise are: • The customer may cancel or change the order before it is shipped. • A publisher may not be able to ship the book as committed. • The shipper may not be able to deliver on time. In all these scenarios there is need for additional coordination, and, possibly negotiation. Publisher 1 Publisher2 Publisher 3 (3) (4) (2) (7) (5) Billing Amazon Shipping Co. Co. (8) (6) (1) Customer (Joe or Jane) Figure 2: A mail order example. 3. Architecture Our general approach is based on the metaphor of a routing slip that defines the routing schema. A routing slip is a simple sequence of roles or users who must review the documents in a certain sequence. One or more documents can be attached to, modified, and detached from the routing slip by various workers. An owner creates the routing slip and defines the routing patterns in terms of various constructs, to be discussed in the next section. Each slip has a unique ID that can be used to trace the routing slip. 9 XRL extends the routing slip metaphor, as we will see at length in Section 4. However, this section will focus mainly on overall architectural issues. Figure 3 shows the WfMC (Workflow Management Coalition, [30]) reference architecture which is centered around the workflow engine. The various interfaces shown here have been partly specified by WfMC. Unfortunately, precise semantics of these interface specifications are not given and most vendors have generated their own definitions. The client applications can access the workflow engine over a network. The process definition tools allow the process to be specified. The administration tools are for managing the workflow engine. There is also support for additional services. Very recently, the WfMC has issued a specification for Interface 4 of Figure 3 based on XML [50]. This specification is named Wf- XML and models the data transfer requirements among different workflow engines in XML. It allows process status and results to be exchanged among multiple engines. Unfortunately, it does not go into the specifics of routing. In Section 7, we shall compare XRL with Wf-XML further. Process Definition Tools Interface 1 Workflow API and Interchange formats Interface 4 Interface 5 Workflow Enactment Service Other Workflow Administration Enactment Service(s) & Monitoring Tools Workflow Workflow Engine(s) Engine(s) Interface 2 Interface 3 Workflow Invoked Client Applications Applications Figure 3: WfMC reference model architecture (©WfMC [30]). Figure 4 shows our own architecture of the workflow engine. Our workflow management system XRL/flower uses this architecture. The routing schema in XRL is received at a node through email. It is parsed using a standard XML parser and stored as an XML data structure. The core of the engine reads this parsed structure and creates a Petri-net representation. This representation is used by the engine to determine the next step(s) to be performed and then to present them to the user through a user interface. The user then enters the action taken by him/her to complete the step and notifies the workflow engine which determines the next step(s). When all the steps at this node are completed, the workflow engine writes out the revised XRL data structure and sends it to the next node in the workflow. 10