More Web Proxy on the site http://driver.im/

research-article

Comparing workflow specification languages: A matter of views

Authors:

Serge Abiteboul,

Pierre Bourhis,

Victor VianuAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 37, Issue 2

Article No.: 10, Pages 1 - 59

https://doi.org/10.1145/2188349.2188352

Published: 04 June 2012 Publication History

Abstract

We address the problem of comparing the expressiveness of workflow specification formalisms using a notion of view of a workflow. Views allow to compare widely different workflow systems by mapping them to a common representation capturing the observables relevant to the comparison. Using this framework, we compare the expressiveness of several workflow specification mechanisms, including automata, temporal constraints, and pre-and postconditions, with XML and relational databases as underlying data models. One surprising result shows the considerable power of static constraints to simulate apparently much richer workflow control mechanisms.

References

[1]

Abiteboul, S., Benjelloun, O., and Milo, T. 2008a. The active xml project: An overview. VLDB J. 17, 5.

Digital Library

[2]

Abiteboul, S., Bourhis, P., and Marinoiu, A. G. B. 2009. The axml artifact model. In Time.

Digital Library

[3]

Abiteboul, S., Bourhis, P., and Vianu, V. 2011. Comparing workflow specification languages: A matter of views. In Proceedings of the International Conference on Database Technology (ICDT'11). 78--89.

Digital Library

[4]

Abiteboul, S., Herr, L., and den Bussche, J. V. 1996. Temporal versus first-order logic to query temporal databases. In Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'96).

Digital Library

[5]

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley.

Digital Library

[6]

Abiteboul, S., Segoufin, L., and Vianu, V. 2008b. Static analysis of active xml systems. ACM Trans. Datab. Syst. 34, 4.

Digital Library

[7]

Abiteboul, S., Vianu, V., Fordham, B., and Yesha, Y. 2000. Relational transducers for electronic commerce. J. Comput. Syst. Sci. 61, 2, 236--269.

Digital Library

[8]

Adam, N., Atluri, V., and Huang, W. 1998. Modeling and analysis of workflows using Petri nets. J. Intell. Inf. Syst. 10, 2, 131--158.

Digital Library

[9]

Alon, N., Milo, T., Neven, F., Suciu, D., and Vianu, V. 2003. XML with data values: Typechecking revisited. J. Comput. Syst. Sci. 66, 4, 688--727.

Digital Library

[10]

Alur, R., Benedikt, M., Etessami, K., Godefroid, P., Reps, T. W., and Yannakakis, M. 2005. Analysis of recursive state machines. ACM Trans. Program. Lang. Syst. 27, 4, 786--818.

Digital Library

[11]

Arenas, M., Fan, W., and Libkin, L. 2002. Consistency of xml specifications. In Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'02).

Digital Library

[12]

Bhattacharya, K., Gerede, C. E., Hull, R., Liu, R., and Su, J. 2007. Towards formal analysis of artifact-centric business process models. In Proceedings of the International Conference on Business Process Management (BPM'07).

Digital Library

[13]

Bojanczyk, M., Muscholl, A., Schwentick, T., Segoufin, L., and David, C. 2006. Two-Variable logic on words with data. In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS'06).

Digital Library

[14]

BPEL. 2012. http://bpel.xml.org/.

[15]

Calvanese, D., Giacomo, G. D., Hull, R., and Su, J. 2009. Artifact-Centric workflow dominance. In Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications (ICSOC'09). 130--143.

Digital Library

[16]

David, C. 2008. Complexity of data tree patterns over xml documents. In Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS'08).

Digital Library

[17]

Demri, S. and Lazić, R. 2009. LTL with the freeze quantifier and register automata. ACM Trans. Comput. Logic 10, 3, 1--30.

Digital Library

[18]

Deutsch, A., Hull, R., Patrizi, F., and Vianu, V. 2009. Automatic verification of data-centric business processes. In Proceedings of the International Conference on Database Theory (ICDT'09).

Digital Library

[19]

Deutsch, A., Sui, L., and Vianu, V. 2007. Specification and verification of data-driven web applications. J. Comput. Syst. Sci. 73, 3, 442--474.

Digital Library

[20]

Diekert, V. and Gastin, P. 2008. First-Order definable languages. In Logic and Automata: History and Perspectives, J. Flum, E. Grädel, and T. Wilke, Eds., Vol. 2, 261--306.

[21]

Dong, G., Hull, R., Kumar, B., Su, J., and Zhou, G. 1999. A framework for optimizing distributed workflow executions. In Proceedings of the DBLP'99 Conference.

Digital Library

[22]

Emerson, E. A. 1990. Temporal and modal logic. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, J. V. Leenwen, Ed., MIT Press, 995--1072.

Digital Library

[23]

Fan, W. and Libkin, L. 2001. On xml integrity constraints in the presence of the dtds. In Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'01).

Digital Library

[24]

Fritz, C., Hull, R., and Su, J. 2009. Automatic construction of simple artifact-based business processes. In Proceedings of the International Conference on Datab. Theory (ICDT'09).

Digital Library

[25]

Georgakopoulos, D., Hornick, M., and Sheth, A. 1995. An overview of workflow management: From process modeling to workflow infrastructure management. Distrib. Parallel Databases 3, 119--153.

Digital Library

[26]

Gerede, C. E., Bhattacharya, K., and Su, J. 2007. Static analysis of business artifact-centric operational models. In Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications (ICSOC'07).

Digital Library

[27]

Gerede, C. E. and Su, J. 2007. Specification and verification of artifact behaviors in business process models. In Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications (ICSOC'07).

Digital Library

[28]

Harel, D. 1987. Statecharts: A visual formulation for complex systems. Sci. Comput. Program. 8, 3, 231--274.

Digital Library

[29]

Hull, R. 2009. Artifact-Centric business process models: Brief survey of research results and challenges. In Proceedings of the OTM Conference, vol. 2, 1152--1163.

Digital Library

[30]

Hull, R., Llirbat, F., Kumar, B., Zhou, G., Dong, G., and Su, J. 2000. Optimization techniques for data-intensive decision flows. In Proceedings of the International Conference on Data Engineering (ICDE'00).

Digital Library

[31]

Hull, R., Llirbat, F., Simon, E., Su, J., Dong, G., Kumar, B., and Zhou, G. 1999. Declarative workflows that support easy modification and dynamic browsing. In Proceedings of the International Joint Conference on Work Activities Coordination and Collaboration.

Digital Library

[32]

Libkin, L. 2004. Elements of Finite Model Theory. Springer.

Digital Library

[33]

Martin, D., Burstein, M., Hobbs, J., Lassila, O., McDermott, D., McIlraith, S., et al. 2003. OWL-S: Semantic markup for web services. W3C Member Submission.

[34]

McIlraith, S. A., Son, T. C., and Zeng, H. 2001. Semantic web services. IEEE Intell. Syst. 16, 2, 46--53.

Digital Library

[35]

Milner, R. 1989. Communication and Concurrency. Prentice-Hall.

Digital Library

[36]

Mok, W. and Paper, D. 2002. Using Harel's statecharts to model business workflows. J. Datab. Manag. 13, 3, 17--34.

[37]

Narayanan, S. and McIlraith, S. 2002. Simulation, verification and automated composition of web services. In Proceedings of the International World Wide Web Conference (WWW'02).

Digital Library

[38]

Neven, F., Schwentick, T., and Vianu, V. 2004. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Logic 5, 3, 403--435.

Digital Library

[39]

Nigam, A. and Caswell, N. S. 2003. Business artifacts: An approach to operational specification. IBM Syst. J. 42, 3, 428--445.

Digital Library

[40]

Segoufin, L. 2007. Static analysis of xml processing with data values. SIGMOD Rec. 36, 1, 31--38.

Digital Library

[41]

Spielmann, M. 2003. Verification of relational transducers for electronic commerce. J. Comut. Syst. Sci. 66, 1, 40--65.

Digital Library

[42]

van Bentham, J. 1976. Modal correspondence theory. Ph.D. thesis, Mathematical Instituut and Instituut voor Grondslagenonderzoek, University of Amsterdam.

[43]

van der Aalst, W. 2004. Business process management demystified: A tutorial on models, systems and standards for workflow management. In Lectures on Concurrency and Petri Nets.

[44]

van der Aalst, W. M. P. 1998. The application of petri nets to workflow management. J. Circ. Syst. Comput. 8, 1, 21--66.

[45]

van der Aalst, W. M. P. and ter Hofstede, A. H. M. 2002. Workflow patterns: On the expressive power of (petri-net-based) workflow languages. In Proceedings of the 4^th International Workshop on Practical Use of Coloured Petri Nets and the CPN Tools.

[46]

Vardi, M. Y. 1996. An automata-theoretic approach to linear temporal logic. In Logics for Concurrency: Structure versus Automata. Lecture Notes in Computer Science, vol. 1043, Springer, 238--266.

Digital Library

[47]

Wang, J. and Kumar, A. 2005. A framework for document-driven workflow systems. In Proceedings of the International Conference on Business Process Management (BPM'05). 285--301.

Digital Library

Cited By

Segoufin LVianu VSuciu DTao YWei Z(2020)Projection Views of Register AutomataProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387651(299-313)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387651
Versluis Lvan Eyk EIosup AWolter KKnottenbelt Wvan Hoorn ANambiar MKoziolek H(2018)An Analysis of Workflow Formalisms for Workflows with Complex Non-Functional RequirementsCompanion of the 2018 ACM/SPEC International Conference on Performance Engineering10.1145/3185768.3186297(107-112)Online publication date: 2-Apr-2018
https://dl.acm.org/doi/10.1145/3185768.3186297
Abiteboul SBourhis PVianu V(2018)Highly Expressive Query Languages for Unordered Data TreesTheory of Computing Systems10.1007/s00224-015-9617-557:4(927-966)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00224-015-9617-5
Show More Cited By

Index Terms

Comparing workflow specification languages: A matter of views

Recommendations

Comparing workflow specification languages: a matter of views
ICDT '11: Proceedings of the 14th International Conference on Database Theory

We address the problem of comparing the expressiveness of workflow specification formalisms using a notion of view of a workflow. Views allow to compare widely different workflow systems by mapping them to a common representation capturing the ...
Operational specification languages
ACM '83: Proceedings of the 1983 annual conference on Computers : Extending the human resource

The “operational approach” to software development is based on separation of problem-oriented and implementation-oriented concerns, and features executable specifications and transformational implementation. “Operational specification languages” are ...
A declarative specification and semantics for visual languages

A key issue in visual languages is the specification of the relationship between pictures and their meaning. To do this, we introduce a class of declarative, constraint-based picture specification languages. These extend previous approaches to picture ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 37, Issue 2

May 2012

326 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/2188349

Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2012

Accepted: 01 January 2012

Revised: 01 January 2012

Received: 01 May 2011

Published in TODS Volume 37, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
627
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Segoufin LVianu VSuciu DTao YWei Z(2020)Projection Views of Register AutomataProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387651(299-313)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387651
Versluis Lvan Eyk EIosup AWolter KKnottenbelt Wvan Hoorn ANambiar MKoziolek H(2018)An Analysis of Workflow Formalisms for Workflows with Complex Non-Functional RequirementsCompanion of the 2018 ACM/SPEC International Conference on Performance Engineering10.1145/3185768.3186297(107-112)Online publication date: 2-Apr-2018
https://dl.acm.org/doi/10.1145/3185768.3186297
Abiteboul SBourhis PVianu V(2018)Highly Expressive Query Languages for Unordered Data TreesTheory of Computing Systems10.1007/s00224-015-9617-557:4(927-966)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00224-015-9617-5
Abiteboul SArenas MBarceló PBienvenu MCalvanese DDavid CHull RHüllermeier EKimelfeld BLibkin LMartens WMilo TMurlak FNeven FOrtiz MSchwentick TStoyanovich JSu JSuciu DVianu VYi K(2017)Research Directions for Principles of Data Management (Abridged)ACM SIGMOD Record10.1145/3092931.309293345:4(5-17)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1145/3092931.3092933
Calvanese DDe Giacomo GMontali MHull RFan W(2013)Foundations of data-aware process analysisProceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems10.1145/2463664.2467796(1-12)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463664.2467796
Abiteboul SVianu VHull RFan W(2013)Collaborative data-driven workflowsProceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems10.1145/2463664.2463672(91-102)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463664.2463672

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents