Efficient provenance storage over nested data collections

ABSTRACT

Scientific workflow systems are increasingly used to automate complex data analyses, largely due to their benefits over traditional approaches for workflow design, optimization, and provenance recording. Many workflow systems employ a simple dependency model to represent the provenance of data produced by workflow runs. Although commonly adopted, this model does not capture explicit data dependencies introduced by "provenance-aware" processes, and it can lead to inefficient storage when workflow data is complex or structured. We present a provenance model, extending the conventional approach, that supports (i) explicit data dependencies and (ii) nested data collections. Our model adopts techniques from reference-based XML versioning, adding annotations for process and data dependencies. We present strategies and reduction techniques to store immediate and transitive provenance information within our model, and examine trade-offs among update time, storage size, and query response time. We evaluate our approach on real-world and synthetic workflow execution traces, demonstrating significant reductions in storage size, while also reducing the time required to store and query provenance information.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: I. Altintas, O. Barney, E. Jaeger-Frank. Provenance collection support in the Kepler scientific workflow system. IPAW, 2006.
• 3: Roger S. Barga , Luciano A. Digiampietri, Automatic capture and efficient storage of e-Science experiment provenance, Concurrency and Computation: Practice & Experience, v.20 n.5, p.419-429, April 2008 [doi>10.1002/cpe.v20:5]
• 4: L. Bavoil, S. P. Callahan, C. E. Scheidegger, H. T. Vo, P. Crossno, C. T. Silva, J. Freire. Vistrails: Enabling interactive multiple-view visualizations, IEEE Visualization, 2005.
• 5: O. Biton, S. C. Boulakia, S. B. Davidson, and C. S. Hara. Querying and managing provenance through user views in scientific workflows. ICDE, 2008.
• 6: Shawn Bowers , Timothy Mcphillips , Sean Riddle , Manish Kumar Anand , Bertram Ludäscher, Kepler/pPOD: Scientific Workflow and Provenance Support for Assembling the Tree of Life, Provenance and Annotation of Data and Processes: Second International Provenance and Annotation Workshop, IPAW 2008, Salt Lake City, UT, USA, June 17-18, 2008. Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-89965-5_9]
• 7: S. Bowers, T. M. McPhillips, B. Ludäscher, S. Cohen, S. B. Davidson. A model for user-oriented data provenance in pipelined scientific workflows. IPAW, 2006.
• 8: S. Bowers, T. M. McPhillips, M. Wu, B. Ludäscher. Project histories: Managing data provenance across collection-oriented scientific workflow runs. DILS, LNCS, 2007.
• 9: Peter Buneman , Adriane Chapman , James Cheney, Provenance management in curated databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142534]
• 10: 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]
• 11: Sudarshan S. Chawathe , Serge Abiteboul , Jennifer Widom, Representing and Querying Changes in Semistructured Data, Proceedings of the Fourteenth International Conference on Data Engineering, p.4-13, February 23-27, 1998
• 12: S.-Y. Chien , V. J. Tsotras , C. Zaniolo, Efficient schemes for managing multiversionXML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.332-353, December 2002 [doi>10.1007/s00778-002-0079-4]
• 13: S. Cohen, S. C. Boulakia, S. B. Davidson. Towards a model of provenance and user views in scientific workflows. In DILS, pages 264--279, 2006.
• 14: Y. Cui , J. Widom, Lineage tracing for general data warehouse transformations, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.1, p.41-58, May 2003 [doi>10.1007/s00778-002-0083-8]
• 15: 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]
• 16: Ewa Deelman , Ann Chervenak, Data Management Challenges of Data-Intensive Scientific Workflows, Proceedings of the 2008 Eighth IEEE International Symposium on Cluster Computing and the Grid, p.687-692, May 19-22, 2008 [doi>10.1109/CCGRID.2008.24]
• 17: Rubing Duan , Radu Prodan , Thomas Fahringer, Run-time Optimisation of Grid Workflow Applications, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, p.33-40, September 28-29, 2006 [doi>10.1109/ICGRID.2006.310995]
• 18: Wenfei Fan , Gao Cong , Philip Bohannon, Querying xml with update syntax, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247515]
• 19: Yolanda Gil , Ewa Deelman , Mark Ellisman , Thomas Fahringer , Geoffrey Fox , Dennis Gannon , Carole Goble , Miron Livny , Luc Moreau , Jim Myers, Examining the Challenges of Scientific Workflows, Computer, v.40 n.12, p.24-32, December 2007 [doi>10.1109/MC.2007.421]
• 20: Y. Gil, V. Ratnakar, E. Deelman, G. Mehta, and J. Kim. Wings for pegasus: Creating large-scale scientific applications using semantic representations of computational workflows. In AAAI, pp. 1767--1774, 2007.
• 21: S. Gurmeet, C. Kesselman, and E. Deelman. Optimizing grid-based workflow execution. J. Grid Comput., 3(3--4):201--219, 2005.
• 22: 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]
• 23: J. Hidders, N. Kwasnikowska, J. Sroka, J. Tyszkiewicz, and J. V. den Bussche. Petri net + nested relational calculus = dataflow. In OTM Conferences, LNCS 3760, pp. 220--237, 2005.
• 24: Wesley M. Johnston , J. R. Paul Hanna , Richard J. Millar, Advances in dataflow programming languages, ACM Computing Surveys (CSUR), v.36 n.1, p.1-34, March 2004 [doi>10.1145/1013208.1013209]
• 25: Christoph Koch, Processing queries on tree-structured data efficiently, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142382]
• 26: Christoph Koch , Stefanie Scherzinger, Attribute grammars for scalable query processing on XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.3, p.317-342, July 2007 [doi>10.1007/s00778-005-0169-1]
• 27: Bertram Ludäscher , Ilkay Altintas , Chad Berkley , Dan Higgins , Efrat Jaeger , Matthew Jones , Edward A. Lee , Jing Tao , Yang Zhao, Scientific workflow management and the Kepler system: Research Articles, Concurrency and Computation: Practice & Experience, v.18 n.10, p.1039-1065, August 2006 [doi>10.1002/cpe.v18:10]
• 28: Amélie Marian , Serge Abiteboul , Gregory Cobena , Laurent Mignet, Change-Centric Management of Versions in an XML Warehouse, Proceedings of the 27th International Conference on Very Large Data Bases, p.581-590, September 11-14, 2001
• 29: Timothy McPhillips , Shawn Bowers , Daniel Zinn , Bertram Ludäscher, Scientific workflow design for mere mortals, Future Generation Computer Systems, v.25 n.5, p.541-551, May, 2009 [doi>10.1016/j.future.2008.06.013]
• 30: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, ACM Transactions on Database Systems (TODS), v.30 n.1, p.1-40, March 2005 [doi>10.1145/1061318.1061319]
• 31: Archan Misra , Marion Blount , Anastasios Kementsietsidis , Daby Sow , Min Wang, Advances and Challenges for Scalable Provenance in Stream Processing Systems, Provenance and Annotation of Data and Processes: Second International Provenance and Annotation Workshop, IPAW 2008, Salt Lake City, UT, USA, June 17-18, 2008. Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-89965-5_26]
• 32: Paolo Missier , Khalid Belhajjame , Jun Zhao , Marco Roos , Carole Goble, Data Lineage Model for Taverna Workflows with Lightweight Annotation Requirements, Provenance and Annotation of Data and Processes: Second International Provenance and Annotation Workshop, IPAW 2008, Salt Lake City, UT, USA, June 17-18, 2008. Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-89965-5_4]
• 33: Luc Moreau , Bertram Ludäscher , Ilkay Altintas , Roger S. Barga , Shawn Bowers , Steven Callahan , George Chin, Jr. , Ben Clifford , Shirley Cohen , Sarah Cohen-Boulakia , Susan Davidson , Ewa Deelman , Luciano Digiampietri , Ian Foster , Juliana Freire , James Frew , Joe Futrelle , Tara Gibson , Yolanda Gil , Carole Goble , Jennifer Golbeck , Paul Groth , David A. Holland , Sheng Jiang , Jihie Kim , David Koop , Ales Krenek , Timothy McPhillips , Gaurang Mehta , Simon Miles , Dominic Metzger , Steve Munroe , Jim Myers , Beth Plale , Norbert Podhorszki , Varun Ratnakar , Emanuele Santos , Carlos Scheidegger , Karen Schuchardt , Margo Seltzer , Yogesh L. Simmhan , Claudio Silva , Peter Slaughter , Eric Stephan , Robert Stevens , Daniele Turi , Huy Vo , Mike Wilde , Jun Zhao , Yong Zhao, Special Issue: The First Provenance Challenge, Concurrency and Computation: Practice & Experience, v.20 n.5, p.409-418, April 2008 [doi>10.1002/cpe.v20:5]
• 34: L. Moreau, J. Freire, J. Futrelle, R. McGrath, J. Myers, and P. Paulson. The open provenance model. Technical Report 14979, ECS, University of Southampton, 2007.
• 35: Leon J. Osterweil , Lori A. Clarke , Aaron M. Ellison , Rodion Podorozhny , Alexander Wise , Emery Boose , Julian Hadley, Experience in using a process language to define scientific workflow and generate dataset provenance, Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, November 09-14, 2008, Atlanta, Georgia [doi>10.1145/1453101.1453147]
• 36: Jun Qin , Thomas Fahringer, Advanced data flow support for scientific grid workflow applications, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362679]
• 37: Claudio T. Silva , Juliana Freire , Steven P. Callahan, Provenance for Visualizations: Reproducibility and Beyond, Computing in Science and Engineering, v.9 n.5, p.82-89, September 2007 [doi>10.1109/MCSE.2007.106]
• 38: 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]
• 39: N. Walsh, A. Milowski, and H. S. T. (editors). XProc: An xml pipeline language. W3C Working Draft, May 2008.
• 40: Jun Zhao , Carole Goble , Robert Stevens , Daniele Turi, Mining Taverna's semantic web of provenance, Concurrency and Computation: Practice & Experience, v.20 n.5, p.463-472, April 2008 [doi>10.1002/cpe.v20:5]
• 41: Y. Zhao, M. Wilde, and I. Foster. Applying the virtual data provenance model. In IPAW, LNCS 4145. Springer, 2006.