Optimizing user views for workflows

ABSTRACT

A technique called user views has recently been proposed to focus user attention on relevant information in response to provenance queries over workflow executions [1, 2]: Given user input on what modules in the workflow specification are relevant to the user, a user view is a concise representation that clusters together modules to create a small number of composite modules (or clusters) such that (1) each composite module in a user view contains at most one relevant (atomic) module, thus assuming the "meaning" of that module; and (2) no control or data dependencies (either direct or indirect) are introduced (soundness) or removed (completeness) between relevant modules. The goal is to find a user view with a smallest number of composite modules.

We show that for workflow specifications that are general graphs, regardless of the number of distinct modules in the input workflow and the structure of interaction between them, there always exists a user view of size at most (2^k--1 -- k)² + k, where k is the number of relevant modules. Moreover, a good user view with at most (2^k--1 -- k)² + k clusters can be computed in polynomial time in the size of the graph. We also show that this upper bound is tight. Thus in general graphs, the number of composite modules can be exponentially large in k even in an optimum user view for the specification. We also give a characterization of a good user view in terms of structural properties of each cluster in the user view.

However, for series-parallel workflow graphs, we show that there is always a user-view with at most 2k -- 3 composite modules; further, there exist series-parallel graphs where every user view requires at least 2k -- 3 composite modules. Such graphs capture the structure of many scientific and other workflows that we have encountered in practice. For this class of graphs, we give a simple, linear time algorithm for constructing an optimum user view for a given specification.

REFERENCES

• 1: Olivier Biton , Sarah Cohen-Boulakia , Susan B. Davidson, Zoom*UserViews: querying relevant provenance in workflow systems, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 2: O. Biton, S. Cohen-Boulakia, S. Davidson, and C. Hara. Querying and managing provenance through user views in scientific workflows. In ICDE, 2008.
• 3: Rajendra Bose , Ian Foster , Luc Moreau, Report on the International Provenance and Annotation Workshop: (IPAW'06) 3-5 May 2006, Chicago, ACM SIGMOD Record, v.35 n.3, September 2006 [doi>10.1145/1168092.1168102]
• 4: Rajendra Bose , James Frew, Lineage retrieval for scientific data processing: a survey, ACM Computing Surveys (CSUR), v.37 n.1, p.1-28, March 2005 [doi>10.1145/1057977.1057978]
• 5: S. Bowers and B. Ludäscher. Actor-oriented design of scientific workflows. In ER, 2005.
• 6: 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]
• 7: BPEL. business process execution language for web services. http://www-128.ibm.com/developerworks/library/specification/ws-bpel/.
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: S. B. Davidson, S. Cohen-Boulakia, A. Eyal, B. Ludĺascher, T. McPhillips, S. Bowers, M. K. Anand, and J. Freire. Provenance in scientific workflow systems. IEEE Data Engineering Bulletin, 30(4):44--50, December 2007.
• 10: 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]
• 11: Ian T. Foster , Jens-S. Vöckler , Michael Wilde , Yong Zhao, Chimera: AVirtual Data System for Representing, Querying, and Automating Data Derivation, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.37-46, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029704]
• 12: J. Freire, C. T. Silva, S. P. Callahan, E. Santos, C. E. Scheidegger, and H. T. Vo. Managing rapidly-evolving scientific workflows. In IPAW, 2006.
• 13: L. Moreau and B. Ludäscher, editors. Concurrency and Computation: Practice and Experience -- Special Issue on the First Provenance Challenge. Wiley, 2007 (in press). (see also http://twiki.ipaw.info/bin/view/Challenge/).
• 14: 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]
• 15: Yogesh L. Simmhan , Beth Plale , Dennis Gannon, A survey of data provenance in e-science, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084812]
• 16: Jacobo Valdes , Robert E. Tarjan , Eugene L. Lawler, The recognition of Series Parallel digraphs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.1-12, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804393]