Detecting and resolving unsound workflow views for correct provenance analysis

Peng Sun, Ziyang Liu, Susan Davidson, Yi Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Abstract

Workflow views abstract groups of tasks in a workflow into high level composite tasks, in order to reuse sub-workflows and facilitate provenance analysis. However, unless a view is carefully designed, it may not preserve the dataflow be- tween tasks in the workflow, i.e., it may not be sound. Un-sound views can be misleading and cause incorrect prove- nance analysis. This paper studies the problem of eficiently identifying and correcting unsound workflow views with minimal changes. In particular, given a workflow view, we wish to split each unsound composite task into the minimal number of tasks, such that the resulting view is sound. We prove that this problem is NP-hard by reduction from independent set. We then propose two local optimality conditions (weak and strong), and design polynomial time algorithms for correcting un- sound views to meet these conditions. Experiments show that our proposed algorithms are efective and eficient, and that the strong local optimality algorithm produces better solutions than the weak local optimality algorithm with little processing overhead.

Original languageEnglish (US)
Title of host publicationSIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems
Pages549-561
Number of pages13
DOIs
StatePublished - 2009
Externally publishedYes
EventInternational Conference on Management of Data and 28th Symposium on Principles of Database Systems, SIGMOD-PODS'09 - Providence, RI, United States
Duration: Jun 29 2009Jul 2 2009

Publication series

NameSIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems

Other

OtherInternational Conference on Management of Data and 28th Symposium on Principles of Database Systems, SIGMOD-PODS'09
Country/TerritoryUnited States
CityProvidence, RI
Period6/29/097/2/09

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Connectivity
  • Network
  • Provenance
  • Soundness
  • View
  • Workflow

Fingerprint

Dive into the research topics of 'Detecting and resolving unsound workflow views for correct provenance analysis'. Together they form a unique fingerprint.

Cite this