Detecting and resolving unsound workflow views for correct provenance analysis

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 between tasks in the workflow, i.e., it may not be sound. Unsound views can be misleading and cause incorrect provenance analysis.

This paper studies the problem of efficiently 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 unsound views to meet these conditions. Experiments show that our proposed algorithms are effective and efficient, and that the strong local optimality algorithm produces better solutions than the weak local optimality algorithm with little processing overhead.

REFERENCES

• 1: myExperiment. http://www.myexperiment.org/Workflows.
• 2: Open provenance model, 2008.
• 3: Martín Abadi , Anindya Banerjee , Nevin Heintze , Jon G. Riecke, A core calculus of dependency, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.147-160, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292555]
• 4: Ilkay Altintas , Chad Berkley , Efrat Jaeger , Matthew Jones , Bertram Ludascher , Steve Mock, Kepler: An Extensible System for Design and Execution of Scientific Workflows, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.423, June 21-23, 2004 [doi>10.1109/SSDBM.2004.44]
• 5: Olivier Biton , Sarah Cohen-Boulakia , Susan B. Davidson , Carmem S. Hara, Querying and Managing Provenance through User Views in Scientific Workflows, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1072-1081, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497516]
• 6: Olivier Biton , Susan B. Davidson , Sanjeev Khanna , Sudeepa Roy, Optimizing user views for workflows, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia [doi>10.1145/1514894.1514931]
• 7: Shawn Bowers , Timothy M. McPhillips , Bertram Ludäscher, Provenance in collection-oriented scientific workflows, Concurrency and Computation: Practice & Experience, v.20 n.5, p.519-529, April 2008 [doi>10.1002/cpe.v20:5]
• 8: Adriane P. Chapman , H. V. Jagadish , Prakash Ramanan, Efficient provenance storage, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376715]
• 9: J. Cheney. Program Slicing and Data Provenance. In IEEE Data Eng. Bull., volume 30(4), pages 22--28, 2007.
• 10: J. Cheney, A. Ahmed, and U. A. Acar. Provenance as Dependency Analysis. In Database Programming Languages, pages 138--152, 2007.
• 11: Dickson K. W. Chiu , S. C. Cheung , Sven Till , Kamalakar Karlapalem , Qing Li , Eleanna Kafeza, Workflow View Driven Cross-Organizational Interoperability in a Web Service Environment, Information Technology and Management, v.5 n.3-4, p.221-250, July-October 2004 [doi>10.1023/B:ITEM.0000031580.57966.d4]
• 12: S. Cohen, S. C. Boulakia, and S. B. Davidson. Towards a Model of Provenance and User Views in Scientific Workflows. In DILS, 2006.
• 13: Sérgio Manuel Serra da Cruz , Patrícia M. Barros , Paulo M. Bisch , Maria Luiza Machado Campos , Marta Mattoso, Provenance Services for Distributed Workflows, Proceedings of the 2008 Eighth IEEE International Symposium on Cluster Computing and the Grid, p.526-533, May 19-22, 2008 [doi>10.1109/CCGRID.2008.73]
• 14: Susan B. Davidson , Juliana Freire, Provenance and scientific workflows: challenges and opportunities, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376772]
• 15: Rik Eshuis , Paul Grefen, Constructing customized process views, Data & Knowledge Engineering, v.64 n.2, p.419-438, February, 2008 [doi>10.1016/j.datak.2007.07.003]
• 16: Thomas Heinis , Gustavo Alonso, Efficient lineage tracking for scientific workflows, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376716]
• 17: R. B. A. Kamel Barkaoui and Z. Sbai. Workflow Soundness Verification based on Structure Theory of Petri Nets. In International Journal of Computing and Information Sciences, 2007.
• 18: Ekkart Kindler , Axel Martens , Wolfgang Reisig, Inter-operability of Workflow Applications: Local Criteria for Global Soundness, Business Process Management, Models, Techniques, and Empirical Studies, p.235-253, January 2000
• 19: Duen-Ren Liu , Minxin Shen, Modeling Workflows with a Process-View Approach, Proceedings of the 7th International Conference on Database Systems for Advanced Applications, p.260-267, April 18-20, 2001
• 20: Duen-Ren Liu , Minxin Shen, Workflow modeling for virtual processes: an order-preserving process-view approach, Information Systems, v.28 n.6, p.505-532, September 2003 [doi>10.1016/S0306-4379(02)00028-5]
• 21: Tom Oinn , Matthew Addis , Justin Ferris , Darren Marvin , Martin Senger , Mark Greenwood , Tim Carver , Kevin Glover , Matthew R. Pocock , Anil Wipat , Peter Li, Taverna: a tool for the composition and enactment of bioinformatics workflows, Bioinformatics, v.20 n.17, p.3045-3054, November 2004 [doi>10.1093/bioinformatics/bth361]
• 22: Shrija Rajbhandari , Omer F. Rana , Ian Wootten, A fuzzy model for calculating workflow trust using provenance data, Proceedings of the 15th ACM Mardi Gras conference: From lightweight mash-ups to lambda grids: Understanding the spectrum of distributed computing requirements, applications, tools, infrastructures, interoperability, and the incremental adoption of key capabilities, January 29-February 03, 2008, Baton Rouge, Louisiana [doi>10.1145/1341811.1341823]
• 23: M. R. Ralph Bobrik and T. Bauer. View-Based Process Visualization. In Business Process Management, pages 88--95, 2007.
• 24: Wasim Sadiq , Maria E. Orlowska, Applying Graph Reduction Techniques for Identifying Structural Conflicts in Process Models, Proceedings of the 11th International Conference on Advanced Information Systems Engineering, p.195-209, June 14-18, 1999
• 25: Zhe Shan , Dickson K. W. Chiu , Qing Li, Systematic Interaction Management in a Workflow View Based Business-to-Business Process Engine, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences, p.162.2, January 03-06, 2005 [doi>10.1109/HICSS.2005.573]
• 26: Qihong Shao , Yi Chen , Shu Tao , Xifeng Yan , Nikos Anerousis, EasyTicket: a ticket routing recommendation engine for enterprise problem resolution, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454193]
• 27: Qihong Shao , Yi Chen , Shu Tao , Xifeng Yan , Nikos Anerousis, Efficient ticket routing by resolution sequence mining, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401964]
• 28: Qihong Shao , Peng Sun , Yi Chen, Efficiently discovering critical workflows in scientific explorations, Future Generation Computer Systems, v.25 n.5, p.577-585, May, 2009 [doi>10.1016/j.future.2008.06.005]
• 29: Qihong Shao , Peng Sun , Yi Chen, WISE: A Workflow Information Search Engine, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1491-1494, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.89]
• 30: J. Siegeris and A. Zimmermann. Workflow Model Compositions Preserving Relaxed Soundness. In Business Process Management, pages 177--192, 2006.
• 31: Yogesh L. Simmhan , Beth Plale , Dennis Gannon, A Framework for Collecting Provenance in Data-Centric Scientific Workflows, Proceedings of the IEEE International Conference on Web Services, p.427-436, September 18-22, 2006 [doi>10.1109/ICWS.2006.5]
• 32: Wil M. P. van der Aalst, Workflow Verification: Finding Control-Flow Errors Using Petri-Net-Based Techniques, Business Process Management, Models, Techniques, and Empirical Studies, p.161-183, January 2000
• 33: Jussi Vanhatalo , Hagen Völzer , Frank Leymann, Faster and More Focused Control-Flow Analysis for Business Process Models Through SESE Decomposition, Proceedings of the 5th international conference on Service-Oriented Computing, September 17-20, 2007, Vienna, Austria [doi>10.1007/978-3-540-74974-5_4]
• 34: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Scientific databases

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
provenance, soundness, view, workflow