Provenance as Dependency Analysis

James Cheney; Amal Ahmed; UmutA. Acar

doi:10.1007/978-3-540-75987-4_10

Provenance as Dependency Analysis

James Cheney, Amal Ahmed, UmutA. Acar

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Provenance is information recording the source, derivation, or history of some information. Provenance tracking has been studied in a variety of settings; however, although many design points have been explored, the mathematical or semantic foundations of data provenance have received comparatively little attention. In this paper, we argue that dependency analysis techniques familiar from program analysis and program slicing provide a formal foundation for forms of provenance that are intended to show how (part of) the output of a query depends on (parts of) its input. We introduce a semantic characterization of such dependency provenance, show that this form of provenance is not computable, and provide dynamic and static approximation techniques.

Original language	English
Title of host publication	Database Programming Languages
Subtitle of host publication	11th International Symposium, DBPL 2007, Vienna, Austria, September 23-24, 2007, Revised Selected Papers
Editors	Marcelo Arenas, MichaelI. Schwartzbach
Publisher	Springer Berlin Heidelberg
Pages	138-152
Number of pages	15
Volume	4797
ISBN (Electronic)	978-3-540-75987-4
ISBN (Print)	978-3-540-75986-7
DOIs	https://doi.org/10.1007/978-3-540-75987-4_10
Publication status	Published - 2007

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	4797

Access to Document

10.1007/978-3-540-75987-4_10

http://dx.doi.org/10.1007/978-3-540-75987-4_10

Cite this

Cheney, J., Ahmed, A., & Acar, U. (2007). Provenance as Dependency Analysis. In M. Arenas, & M. Schwartzbach (Eds.), Database Programming Languages: 11th International Symposium, DBPL 2007, Vienna, Austria, September 23-24, 2007, Revised Selected Papers (Vol. 4797, pp. 138-152). (Lecture Notes in Computer Science; Vol. 4797). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-75987-4_10

@inproceedings{efde6bbb60964c0a888717ef396b0328,

title = "Provenance as Dependency Analysis",

abstract = "Provenance is information recording the source, derivation, or history of some information. Provenance tracking has been studied in a variety of settings; however, although many design points have been explored, the mathematical or semantic foundations of data provenance have received comparatively little attention. In this paper, we argue that dependency analysis techniques familiar from program analysis and program slicing provide a formal foundation for forms of provenance that are intended to show how (part of) the output of a query depends on (parts of) its input. We introduce a semantic characterization of such dependency provenance, show that this form of provenance is not computable, and provide dynamic and static approximation techniques.",

author = "James Cheney and Amal Ahmed and UmutA. Acar",

year = "2007",

doi = "10.1007/978-3-540-75987-4_10",

language = "English",

isbn = "978-3-540-75986-7",

volume = "4797",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "138--152",

editor = "Marcelo Arenas and MichaelI. Schwartzbach",

booktitle = "Database Programming Languages",

}

Cheney, J, Ahmed, A & Acar, U 2007, Provenance as Dependency Analysis. in M Arenas & M Schwartzbach (eds), Database Programming Languages: 11th International Symposium, DBPL 2007, Vienna, Austria, September 23-24, 2007, Revised Selected Papers. vol. 4797, Lecture Notes in Computer Science, vol. 4797, Springer Berlin Heidelberg, pp. 138-152. https://doi.org/10.1007/978-3-540-75987-4_10

Provenance as Dependency Analysis. / Cheney, James; Ahmed, Amal; Acar, UmutA.

Database Programming Languages: 11th International Symposium, DBPL 2007, Vienna, Austria, September 23-24, 2007, Revised Selected Papers. ed. / Marcelo Arenas; MichaelI. Schwartzbach. Vol. 4797 Springer Berlin Heidelberg, 2007. p. 138-152 (Lecture Notes in Computer Science; Vol. 4797).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Provenance as Dependency Analysis

AU - Cheney, James

AU - Ahmed, Amal

AU - Acar, UmutA.

PY - 2007

Y1 - 2007

N2 - Provenance is information recording the source, derivation, or history of some information. Provenance tracking has been studied in a variety of settings; however, although many design points have been explored, the mathematical or semantic foundations of data provenance have received comparatively little attention. In this paper, we argue that dependency analysis techniques familiar from program analysis and program slicing provide a formal foundation for forms of provenance that are intended to show how (part of) the output of a query depends on (parts of) its input. We introduce a semantic characterization of such dependency provenance, show that this form of provenance is not computable, and provide dynamic and static approximation techniques.

AB - Provenance is information recording the source, derivation, or history of some information. Provenance tracking has been studied in a variety of settings; however, although many design points have been explored, the mathematical or semantic foundations of data provenance have received comparatively little attention. In this paper, we argue that dependency analysis techniques familiar from program analysis and program slicing provide a formal foundation for forms of provenance that are intended to show how (part of) the output of a query depends on (parts of) its input. We introduce a semantic characterization of such dependency provenance, show that this form of provenance is not computable, and provide dynamic and static approximation techniques.

U2 - 10.1007/978-3-540-75987-4_10

DO - 10.1007/978-3-540-75987-4_10

M3 - Conference contribution

SN - 978-3-540-75986-7

VL - 4797

T3 - Lecture Notes in Computer Science

SP - 138

EP - 152

BT - Database Programming Languages

A2 - Arenas, Marcelo

A2 - Schwartzbach, MichaelI.

PB - Springer Berlin Heidelberg

ER -

Provenance as Dependency Analysis

Abstract

Publication series

Access to Document

Fingerprint

Cite this