Automatic construction of simple artifact-based business processes

ABSTRACT

Almost all medium- and large-scale businesses rely on electronic workflow systems to manage their business processes. A key challenge is to enable the easy re-use and modification of these workflow schemas and their piece-parts, so that they can be adapted to new business situations. This paper describes an approach for automatic construction (and thus, evolution) of a workflow schema that satisfies a specified condition (or "goal"), starting from a set of basic building block services (or "tasks"). We use a workflow model based on "business artifacts", which represent key (real or conceptual) business entities, and include both the business-relevant data about them and a specification of their lifecycle, that is, how they can evolve over time as they move through the workflow as the result of services being applied to them.

This paper uses a declarative form of artifact-centric workflow. The services are non-deterministic, which corresponds to the intuition that humans performing the services may rely on information that is not modeled within the framework. We study the problem of, given a goal to be achieved, automatically finding the "maximal" workflow schema that has the following property: every execution is either complete or can be completed, and every complete execution satisfies the goal. We also study a complimentary problem, in which exception-handling is used to deal with executions that would otherwise not complete successfully. These problems are non-trivial because the workflow services are non-deterministic.

This paper provides a general framework for studying these problems, and shows a tight relationship between workflow systems specified using logics that permit quantifier elimination and the ability to construct maximal schemas with the desired properties. The paper then studies a restricted setting to provide insights into complexity issues. Even in the restricted setting, the problem of testing properties of maximal workflows is PSPACE-complete.

REFERENCES

• 1: J. Baier and S. McIlraith. Planning with first-order temporally extended goals using heuristic search. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI06), pages 788--795, Boston, MA, July 2006.
• 2: S. Battle et al. Semantic Web Services Ontology (SWSO) Version 1.0. http://www.daml.org/services/swsf/1.0/swso/, May 2005.
• 3: Daniela Berardi , Diego Calvanese , Giuseppe De Giacomo , Richard Hull , Massimo Mecella, Automatic composition of transition-based semantic web services with messaging, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: D. Berardi, D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Mecella. Automatic composition of e-services that export their behavior. In Proc. 1st Int. Conf. on Service Oriented Computing (ICSOC), volume 2910 of LNCS, pages 43--58, 2003.
• 5: K. Bhattacharya , N. S. Caswell , S. Kumaran , A. Nigam , F. Y. Wu, Artifact-centered operational modeling: lessons from customer engagements, IBM Systems Journal, v.46 n.4, p.703-721, October 2007
• 6: K. Bhattacharya, C. Gerede, R. Hull, R. Liu, and J. Su. Towards formal analysis of artifact-centric business process models. In Proceedings of 5th International Conference on Business Process Management (BPM), Brisbane, Australia, September 2007.
• 7: K. Bhattacharya , R. Guthman , K. Lyman , F. F. Heath, III , S. Kumaran , P. Nandi , F. Wu , P. Athma , C. Freiberg , L. Johannsen , A. Staudt, A model-driven approach to industrializing discovery processes in pharmaceutical research, IBM Systems Journal, v.44 n.1, p.145-162, January 2005
• 8: K. Bhattacharya, R. Hull, and J. Su. A Data-centric Design Methodology for Business Processes. In J. Cardoso and W. van der Aalst, editors, Handbook of Research on Business Process Management. 2009. to appear.
• 9: Craig Boutilier , Richard Dearden , Moisés Goldszmidt, Stochastic dynamic programming with factored representations, Artificial Intelligence, v.121 n.1-2, p.49-107, Aug. 2000 [doi>10.1016/S0004-3702(00)00033-3]
• 10: C. Boutilier, R. Reiter, and B. Price. Symbolic dynamic programming for first-order MDPs. In Proc. IJCAI'01, pages 690--700, 2001.
• 11: Jan Chomicki, Efficient checking of temporal integrity constraints using bounded history encoding, ACM Transactions on Database Systems (TODS), v.20 n.2, p.149-186, June 1995 [doi>10.1145/210197.210200]
• 12: E. Clarke, O. Grumberg, and D. A. Peled. Model Checking. The MIT Press, Cambridge, Massachusetts, 2000.
• 13: O. S. Coalition. OWL-S: Semantic markup for web services, November 2003.
• 14: Alin Deutsch , Richard Hull , Fabio Patrizi , Victor Vianu, Automatic verification of data-centric business processes, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia [doi>10.1145/1514894.1514924]
• 15: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 16: M. Fränzle. Verification of hybrid systems. In Proc. 19th Int. Conf. on Computer Aided Verification (CAV), 2007.
• 17: Çagdaş Evren Gerede , Richard Hull , Oscar H. Ibarra , Jianwen Su, Automated composition of e-services: lookaheads, Proceedings of the 2nd international conference on Service oriented computing, November 15-19, 2004, New York, NY, USA [doi>10.1145/1035167.1035203]
• 18: Cagdas E. Gerede , Kamal Bhattacharya , Jianwen Su, Static Analysis of Business Artifact-centric Operational Models, Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications, p.133-140, June 19-20, 2007 [doi>10.1109/SOCA.2007.42]
• 19: Cagdas E. Gerede , Jianwen Su, Specification and Verification of Artifact Behaviors in Business Process Models, Proceedings of the 5th international conference on Service-Oriented Computing, September 17-20, 2007, Vienna, Austria [doi>10.1007/978-3-540-74974-5_15]
• 20: M. L. Ginsberg, Universal planning: an (almost) universally bad idea, AI Magazine, v.10 n.4, p.40-44, Winter 1989
• 21: R. Glushko and T. McGrath. Document Engineering: Analyzing and Designing Documents for Business Informatics and Web Services. MIT Press, Cambridge, MA, 2005.
• 22: Stéphane Grumbach , Jianwen Su, Finitely representable databases, Journal of Computer and System Sciences, v.55 n.2, p.273-298, Oct. 1997 [doi>10.1006/jcss.1997.1524]
• 23: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 24: Richard Hull, Artifact-Centric Business Process Models: Brief Survey of Research Results and Challenges, Proceedings of the OTM 2008 Confederated International Conferences, CoopIS, DOA, GADA, IS, and ODBASE 2008. Part II on On the Move to Meaningful Internet Systems, November 09-17, 2008, Monterrey, Mexico [doi>10.1007/978-3-540-88873-4_17]
• 25: Optimization Techniques for Data-Intensive Decision Flows, Proceedings of the 16th International Conference on Data Engineering, p.281, February 28-March 03, 2000
• 26: Richard Hull , Francois Llirbat , Eric Siman , Jianwen Su , Guozhu Dong , Bharat Kumar , Gang Zhou, Declarative workflows that support easy modification and dynamic browsing, Proceedings of the international joint conference on Work activities coordination and collaboration, p.69-78, February 22-25, 1999, San Francisco, California, United States
• 27: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 28: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 29: Dexter Kozen , Chee-Kang Yap, Algebraic cell decomposition in NC, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.515-521, October 21-23, 1985 [doi>10.1109/SFCS.1985.4]
• 30: G. Kuper, L. Libkin, and J. Paredarns, editors. Constraint Databases. Springer Verlag, 2000.
• 31: J. Kuster, K. Ryndina, and H. Gall. Generation of BPM for object life cycle compliance. In Proceedings of 5th International Conference on Business Process Management (BPM), 2007.
• 32: R. Liu, K. Bhattacharya, and F. Y. Wu. Modeling business contexture and behavior using business artifacts. In CAiSE, volume 4495 of LNCS, 2007.
• 33: M. Moreno and P. Kearney. Integrating AI planning techniques with workflow management system. Kowledge-Based Systems, 15(5--6):285--291, 2002.
• 34: Carroll Morgan, The specification statement, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.3, p.403-419, July 1988 [doi>10.1145/44501.44503]
• 35: Srini Narayanan , Sheila A. McIlraith, Simulation, verification and automated composition of web services, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511457]
• 36: Greg Nelson, A generalization of Dijkstra's calculus, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.517-561, Oct. 1989 [doi>10.1145/69558.69559]
• 37: A. Nigam , N. S. Caswell, Business artifacts: An approach to operational specification, IBM Systems Journal, v.42 n.3, p.428-445, July 2003
• 38: J. Penberthy and D. Weld. UCPOP: A sound, complete, partial order planner for ADL. In Proceedings of the Third International Conference on Knowledge Representation and Reasoning, pages 103--114, 1992.
• 39: S. Sardina, F. Patrizi, and G. De Giacomo. Behavior composition in the presence of failure. In G. Brewka and J. Lang, editors, Proceedings of Principles of Knowledge Representation and Reasoning (KR), pages 640--650, Sydney, Australia, Sept. 2008.
• 40: M. J. Schoppers. Universal plans for reactive robots in unpredictable environments. In J. McDermott, editor, Proc. IJCAI'87, pages 1039--1046, Milan, Italy, 1987. Morgan Kaufmann publishers Inc.: San Mateo, CA, USA.
• 41: J. K. Strosnider , P. Nandi , S. Kumaran , S. Ghosh , A. Arsanjani, Model-driven synthesis of SOA solutions, IBM Systems Journal, v.47 n.3, p.415-432, July 2008
• 42: R. Waldinger. Achieving several goals simultaneously. In E. W. Elcock and D. Michie, editors, Machine Intelligence, volume 8, pages 94--136. Wiley, 1977.
• 43: J. Wang and A. Kumar. A framework for document-driven workflow systems. In Business Process Management, pages 285--301, 2005.
• 44: Web Service Modeling Ontology. http://www.wsmo.org/.