CSE 703 Provenance and lineage

Registration #20919

Instructor

Dr. Jan Chomicki, Professor. Office hours: W 4-5, F 1-2.

Time and location

Mon 11:00-12:50 pm, Davis 338A.

Talks

Date	Topics	Presenter	References
02/12/18	Basics of provenance	Dr. Jan Chomicki	James Cheney, Laura Chiticariu, Wang Chiew Tan: Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases 1(4): 379-474 (2009)
02/12/18	Data citation	Rajiv Ranjan	Peter Buneman, Susan B. Davidson, James Frew: Why data citation is a computational problem. Commun. ACM 59(9): 50-57 (2016)
02/19/18	Beyond the semiring model for provenance	Dr. Oliver Kennedy
02/26/18	Database schema evolution	Bharadwaj Parthasarathy	Carlo Curino, Hyun Jin Moon, Alin Deutsch, Carlo Zaniolo: Automating the database schema evolution process. VLDB J. 22(1): 73-98 (2013)
02/26/18	Causality in Databases	Charanya Sudharsanan	Alexandra Meliou, Wolfgang Gatterbauer, Joseph Y. Halpern, Christoph Koch, Katherine F. Moore, Dan Suciu: Causality in Databases. IEEE Data Eng. Bull. 33(3): 59-67 (2010).
03/05/18	Provenance for natural language processing	Deep Narayan Mishra	Daniel Deutch, Nave Frost, Amir Gilad: Provenance for Natural Language Queries. PVLDB 10(5): 577-588 (2017).
03/05/18	Provenance for curated databases	Raman Keswani	Peter Buneman, Adriane Chapman, James Cheney: Provenance management in curated databases. SIGMOD Conference 2006: 539-550.
03/12/18	Workflow provenance in PIG	Varun Jain	Yael Amsterdamer, Susan B. Davidson, Daniel Deutch, Tova Milo, Julia Stoyanovich, Val Tannen: Putting Lipstick on Pig: Enabling Database-style Workflow Provenance. PVLDB 5(4): 346-357 (2011).
04/02/18	Provenance in the cloud	Parikshit Desmukh	Kiran-Kumar Muniswamy-Reddy, Peter Macko, Margo I. Seltzer: Provenance for the Cloud. FAST 2010: 197-210
04/09/18	Provenance and Visualization	Jayant Solanki	Eric D. Ragan, Alex Endert, Jibonananda Sanyal, Jian Chen: Characterizing Provenance in Visualization and Data Analysis: An Organizational Framework of Provenance Types and Purposes. IEEE Trans. Vis. Comput. Graph. 22(1): 31-40 (2016)
04/16/18	Crowdsourcing	Anant Gupta	Michael J. Franklin, Donald Kossmann, Tim Kraska, Sukriti Ramesh, Reynold Xin: CrowdDB: answering queries with crowdsourcing. SIGMOD Conference 2011: 61-72.
04/16/18	Provenance and slicing	Yuze Liu	James Cheney: Program Slicing and Data Provenance. IEEE Data Eng. Bull. 30(4): 22-28 (2007)
04/23/18	Fault injection	Zeba Khan	Peter Alvaro, Joshua Rosen, Joseph M. Hellerstein: Lineage-driven Fault Injection. SIGMOD Conference 2015: 331-346.
04/30/18	Provenance in workflows	Nitish Shokeen	Robert Ikeda, Akash Das Sarma, Jennifer Widom: Logical provenance in data-oriented workflows? ICDE 2013: 877-888.
04/30/18	Provenance and versioning	Shivam Upadhyay	Amit Chavan, Silu Huang, Amol Deshpande, Aaron J. Elmore, Samuel Madden, Aditya G. Parameswaran: Towards a Unified Query Language for Provenance and Versioning. TaPP 2015

Resources

To access the papers in the UB digital library, you may need to use the proxy server and reload the appropriate page:

 http://libweb.lib.buffalo.edu/help/help.asp?ID1=442

Many papers can be googled on the author pages or retrieved from

dblp

Workload

Prepare and present a talk based on one or more papers from the current computer science literature (I will distribute the papers and help with the presentation).
The presentations will be problem-oriented, not paper-oriented. It may be necessary to read more than one paper and/or split the work with another presenter. For example, one presenter may give a general introduction to the area and the other present a specific approach in depth.
Prepare a report based on the same material.
Attend all the classes and participate in the discussions.
There will also be presentations by the instructor and/or invited speakers.

Prerequisites

Required background: a course in databases. Some knowledge of logic is helpful.

Grading

The seminar is graded S/U and can be taken for 3 credits. An implementation project is a possibility: see the instructor.

Policies

Academic integrity
Class attendance is mandatory. No late arrivals in class.
Other relevant university policies.

Accessibility resources

Students with physical or learning disabilities should register with the Accessibility Resources in order to receive accommodation.

Summary

Provenance is one of the central topics in Big Data. Data provenance keeps track of how the data is derived from the sources. Workflow provenance/lineage represents the information about specific processes and makes it possible to query and replay them. An important class of provenance applications deals with query result explanation. Another class deals with scientific workflows. This seminar will address practical and theoretical issues in provenance, lineage and related areas. Each participating student will present one or more research papers from the current database literature, and prepare a report.

Topics

General

James Cheney, Laura Chiticariu, Wang Chiew Tan: Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases 1(4): 379-474 (2009).

Todd J. Green, Val Tannen: The Semiring Framework for Database Provenance. PODS 2017: 93-99.

Provenance

Yael Amsterdamer, Susan B. Davidson, Daniel Deutch, Tova Milo, Julia Stoyanovich, Val Tannen: Putting Lipstick on Pig: Enabling Database-style Workflow Provenance. PVLDB 5(4): 346-357 (2011).

Peter Buneman, Adriane Chapman, James Cheney: Provenance management in curated databases. SIGMOD Conference 2006: 539-550.

Chen Chen, Harshal Tushar Lehri, Lay Kuan Loh, Anupam Alur, Limin Jia, Boon Thau Loo, Wenchao Zhou: Distributed Provenance Compression. SIGMOD Conference 2017: 203-218.

Amit Chavan, Silu Huang, Amol Deshpande, Aaron J. Elmore, Samuel Madden, Aditya G. Parameswaran: Towards a Unified Query Language for Provenance and Versioning. TaPP 2015

Luc Moreau, Paul T. Groth, James Cheney, Timothy Lebo, Simon Miles: The rationale of PROV. J. Web Sem. 35: 235-257 (2015).

Umut A. Acar, Peter Buneman, James Cheney, Jan Van den Bussche, Natalia Kwasnikowska, Stijn Vansummeren: A Graph Model of Data and Workflow Provenance. TaPP 2010.

Peter Buneman, James Cheney, Stijn Vansummeren: On the expressiveness of implicit provenance in query and update languages. ACM Trans. Database Syst. 33(4): 28:1-28:47 (2008).

Yael Amsterdamer, Daniel Deutch, Val Tannen: Provenance for aggregate queries. PODS 2011: 153-164.

Yael Amsterdamer, Daniel Deutch, Tova Milo, Val Tannen: On Provenance Minimization. ACM Trans. Database Syst. 37(4): 30:1-30:36 (2012).

Applications

Daniel Deutch, Yuval Moskovitch, Val Tannen: Provenance-based analysis of data-centric processes. VLDB J. 24(4): 583-607 (2015).

Marcin Wylot, Philippe Cudré-Mauroux, Manfred Hauswirth, Paul T. Groth: Storing, Tracking, and Querying Provenance in Linked Data. IEEE Trans. Knowl. Data Eng. 29(8): 1751-1764 (2017).

Daniel Deutch, Nave Frost, Amir Gilad: Provenance for Natural Language Queries. PVLDB 10(5): 577-588 (2017).

Val Tannen: Provenance analysis for FOL model checking. SIGLOG News 4(1): 24-36 (2017).

Peter Buneman, Susan B. Davidson, James Frew: Why data citation is a computational problem. Commun. ACM 59(9): 50-57 (2016).

Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan: Archiving scientific data. ACM Trans. Database Syst. 29: 2-42 (2004)

Zhepeng Yan, Val Tannen, Zachary G. Ives: Fine-grained Provenance for Linear Algebra Operators. TaPP 2016.

Saumen C. Dey, Sven Köhler, Shawn Bowers, Bertram Ludäscher: Computing Location-Based Lineage from Workflow Specifications to Optimize Provenance Queries. IPAW 2014: 180-193.

Grigoris Karvounarakis, Todd J. Green, Zachary G. Ives, Val Tannen: Collaborative data sharing via update exchange and provenance. ACM Trans. Database Syst. 38(3): 19:1-19:42 (2013)

David W. Archer, Lois M. L. Delcambre, David Maier: User Trust and Judgments in a Curated Database with Explicit Provenance. In Search of Elegance in the Theory and Practice of Computation 2013: 89-111.

Paolo Missier, Jacek Cala, Manisha Rathi: Preserving the value of large scale data analytics over time through selective re-computation. CoRR abs/1610.04752 (2016).

Saumen C. Dey, Khalid Belhajjame, David Koop, Meghan Raul, Bertram Ludäscher: Linking Prospective and Retrospective Provenance in Scripts. TaPP 2015

Lineage

Rajendra Bose, James Frew: Lineage retrieval for scientific data processing: a survey. ACM Comput. Surv. 37(1): 1-28 (2005).

Susan B. Davidson, Sanjeev Khanna, Tova Milo: To Show or Not to Show in Workflow Provenance. In Search of Elegance in the Theory and Practice of Computation 2013: 217-226.

Peter Alvaro, Joshua Rosen, Joseph M. Hellerstein: Lineage-driven Fault Injection. SIGMOD Conference 2015: 331-346.

Paolo Missier, Norman W. Paton, Khalid Belhajjame: Fine-grained and efficient lineage querying of collection-based workflow provenance. EDBT 2010: 299-310.

Robert Ikeda, Akash Das Sarma, Jennifer Widom: Logical provenance in data-oriented workflows? ICDE 2013: 877-888.

Query result explanation, causality

Seokki Lee, Sven Köhler, Bertram Ludäscher, Boris Glavic: A SQL-Middleware Unifying Why and Why-Not Provenance for First-Order Queries. ICDE 2017: 485-496.

Sudeepa Roy, Laurel Orr, Dan Suciu: Explaining Query Answers with Explanation-Ready Databases. PVLDB 9(4): 348-359 (2015).

Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, Dan Suciu: The Complexity of Causality and Responsibility for Query Answers and non-Answers. PVLDB 4(1): 34-45 (2010).

Alexandra Meliou, Wolfgang Gatterbauer, Joseph Y. Halpern, Christoph Koch, Katherine F. Moore, Dan Suciu: Causality in Databases. IEEE Data Eng. Bull. 33(3): 59-67 (2010).

Melanie Herschel: A Hybrid Approach to Answering Why-Not Questions on Relational Query Results. J. Data and Information Quality 5(3): 10:1-10:29 (2015).

Data profiling

Ziawasch Abedjan, Lukasz Golab, Felix Naumann: Profiling relational data: a survey. VLDB J. 24(4): 557-581 (2015).

Jens Ehrlich, Mandy Roick, Lukas Schulze, Jakob Zwiener, Thorsten Papenbrock, Felix Naumann: Holistic Data Profiling: Simultaneous Discovery of Various Metadata. EDBT 2016: 305-316.

Schema evolution

Carlo Curino, Hyun Jin Moon, Alin Deutsch, Carlo Zaniolo: Automating the database schema evolution process. VLDB J. 22(1): 73-98 (2013).

Ramanathan V. Guha, Dan Brickley, Steve Macbeth: Schema.org: evolution of structured data on the web. Commun. ACM 59(2): 44-51 (2016)