TY - GEN
T1 - Detecting and resolving unsound workflow views for correct provenance analysis
AU - Sun, Peng
AU - Liu, Ziyang
AU - Davidson, Susan
AU - Chen, Yi
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Connectivity
KW - Network
KW - Provenance
KW - Soundness
KW - View
KW - Workflow
UR - http://www.scopus.com/inward/record.url?scp=70849121002&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70849121002&partnerID=8YFLogxK
U2 - 10.1145/1559845.1559903
DO - 10.1145/1559845.1559903
M3 - Conference contribution
AN - SCOPUS:70849121002
SN - 9781605585543
T3 - SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems
SP - 549
EP - 561
BT - SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems
T2 - International Conference on Management of Data and 28th Symposium on Principles of Database Systems, SIGMOD-PODS'09
Y2 - 29 June 2009 through 2 July 2009
ER -