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

research-article

Collaborative data-driven workflows: think global, act local

Authors:

Serge Abiteboul,

Victor VianuAuthors Info & Claims

PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

Pages 91 - 102

https://doi.org/10.1145/2463664.2463672

Published: 22 June 2013 Publication History

Abstract

We introduce and study a model of collaborative data-driven workflows. In a local-as-view style, each peer has a partial view of a global instance that remains purely virtual. Local updates have side effects on other peers' data, defined via the global instance. We also assume that the peers provide (an abstraction of) their specifications, so that each peer can actually see and reason on the specification of the entire system.

We study the ability of a peer to carry out runtime reasoning about the global run of the system, and in particular about actions of other peers, based on its own local observations. A main contribution is to show that, under a reasonable restriction (namely, key-visibility), one can construct a finite symbolic representation of the infinite set of global runs consistent with given local observations. Using the symbolic representation, we show that we can evaluate in PSPACE a large class of properties over global runs, expressed in an extension of first-order logic with past linear-time temporal operators, PLTL-FO. We also provide a variant of the algorithm allowing to incrementally monitor a statically defined property, and then develop an extension allowing to monitor an infinite class of properties sharing the same temporal structure, defined dynamically as the run unfolds. Finally, we consider an extension of the language, that permits workflow control with PLTL-FO formulas. We prove that this does not increase the power of the workflow specification language, thereby showing that the language is closed under such introspective reasoning.

References

[1]

P. A. Abdulla and B. Jonsson. Verifying programs with unreliable channels. Inf. and Comp., 127(2), 1996.

[2]

S. Abiteboul, E. Antoine, and J. Stoyanovich. Viewing the web as a distributed knowledge base. In ICDE, 2012.

Digital Library

[3]

S. Abiteboul, O. Benjelloun, and T. Milo. The Active XML project: an overview. VLDB J., 17(5), 2008.

Digital Library

[4]

S. Abiteboul, M. Bienvenu, A. Galland, and E. Antoine. A rule-based language for web data management. In PODS, pages 293--304, 2011.

Digital Library

[5]

S. Abiteboul, P. Bourhis, and V. Vianu. Comparing workflow specification languages: A matter of views. TODS, 37(2), 2012.

Digital Library

[6]

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

Digital Library

[7]

S. Abiteboul and V. Vianu. Datalog extensions for database queries and updates. JCSS, 43(1), 1991.

Digital Library

[8]

P. Alvaro, W. R. Marczak, N. Conway, J. M. Hellerstein, D. Maier, and R. Sears. Dedalus: Datalog in time and space. In Datalog, pages 262--281, 2010.

Digital Library

[9]

M. Arenas, V. Kantere, A. Kementsietsidis, I. Kiringa, R. J. Miller, and J. Mylopoulos. The hyperion project: from data integration to data coordination. SIGMOD Record, 32(3):53--58, 2003.

Digital Library

[10]

D. Brand and P. Zafiropulo. On communicating finite-state machines. JACM, 30(2), 1983.

Digital Library

[11]

J. Brzozwski and E. Leiss. Finite automata and sequential networks. Theoretical Computer Science, 10, 1980.

[12]

A. Deutsch, L. Sui, V. Vianu, and D. Zhou. Verification of communicating data-driven web services. In PODS, 2006.

Digital Library

[13]

E. A. Emerson. Temporal and modal logic. In J. V. Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics. North-Holland Pub. Co./MIT Press, 1990.

Digital Library

[14]

R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, 1995.

[15]

T. J. Green, G. Karvounarakis, N. E. Taylor, O. Biton, Z. G. Ives, and V. Tannen. Orchestra: facilitating collaborative data sharing. In SIGMOD, 2007.

Digital Library

[16]

J. M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record, 39(1), 2010.

Digital Library

[17]

R. Hull. Web services composition: A story of models, automata, and logics. In ICSOC, 2005.

[18]

R. Hull and J. Su. Tools for composite web services: a short overview. SIGMOD Record, 34(2):86--95, 2005.

Digital Library

[19]

T. Imieliński and W. Lipski. Incomplete information in relational databases. JACM, 31(4), 1984.

Digital Library

[20]

Z. G. Ives, T. J. Green, G. Karvounarakis, N. E. Taylor, V. Tannen, P. P. Talukdar, M. Jacob, and F. Pereira. The orchestra collaborative data sharing system. SIGMOD Record, 37(3), 2008.

Digital Library

[21]

A. Nigam and N. S. Caswell. Business artifacts: An approach to operational specification. IBM Systems Journal, 42(3):428--445, 2003.

Digital Library

[22]

I. Tatarinov, Z. G. Ives, J. Madhavan, A. Y. Halevy, D. Suciu, N. N. Dalvi, X. Dong, Y. Kadiyska, G. Miklau, and P. Mork. The piazza peer data management project. SIGMOD Record, 32(3):47--52, 2003.

Digital Library

[23]

M. Vardi. An automata-theoretic approach to linear temporal logic. In Banff Higher Order Workshop, 1995.

Digital Library

Cited By

Vianu VLibkin LPichler RGuagliardo P(2021)Datalog UnchainedProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458815(57-69)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458815
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
Bourhis PHélouët LMiklos ZSingh R(2020)Data Centric Workflows for CrowdsourcingApplication and Theory of Petri Nets and Concurrency10.1007/978-3-030-51831-8_2(24-45)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-51831-8_2
Show More Cited By

Index Terms

Collaborative data-driven workflows: think global, act local

Recommendations

Explanations and Transparency in Collaborative Workflows

PODS '18: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We pursue an investigation of data-driven collaborative workflows. In the model, peers can access and update local data, causing side-effects on other peers' data. In this paper, we study means of explaining to a peer her local view of a global run, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

June 2013

334 pages

ISBN:9781450320665

DOI:10.1145/2463664

General Chair:
Richard Hull
IBM T.J. Watson Research Center, USA
,
Program Chair:
Wenfei Fan
University of Edinburgh, UK

Copyright © 2013 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]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

PODS '13 Paper Acceptance Rate 24 of 97 submissions, 25%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
271
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vianu VLibkin LPichler RGuagliardo P(2021)Datalog UnchainedProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458815(57-69)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458815
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
Bourhis PHélouët LMiklos ZSingh R(2020)Data Centric Workflows for CrowdsourcingApplication and Theory of Petri Nets and Concurrency10.1007/978-3-030-51831-8_2(24-45)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-51831-8_2
Abiteboul SBourhis PVianu VVan den Bussche JArenas M(2018)Explanations and Transparency in Collaborative WorkflowsProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196975(409-424)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196975
Hull R(2017)BlockchainProceedings of the 11th ACM International Conference on Distributed and Event-based Systems10.1145/3093742.3097982(2-4)Online publication date: 8-Jun-2017
https://dl.acm.org/doi/10.1145/3093742.3097982
Hull RBatra VChen YDeutsch AHeath III FVianu V(2016)Towards a Shared Ledger Business Collaboration Language Based on Data-Aware ProcessesService-Oriented Computing10.1007/978-3-319-46295-0_2(18-36)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-319-46295-0_2
Bozzon ABrambilla MCeri SMauri AVolonterio R(2015)Designing complex crowdsourcing applications covering multiple platforms and tasksJournal of Web Engineering10.5555/2871274.287127914:5-6(443-473)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.5555/2871274.2871279
Deutsch AHull RVianu V(2014)Automatic Verification of Database-Centric SystemsACM SIGMOD Record10.1145/2694428.269443043:3(5-17)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.1145/2694428.2694430

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten