Provenance as dependency analysis

James Cheney, Amal Ahmed, Umut A. Acar

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Provenance is information recording the source, derivation or history of some information. Provenance tracking has been studied in a variety of settings, particularly database management systems. However, although many candidate definitions of provenance have been proposed, 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 characterisation of such dependency provenance for a core database query language, show that minimal dependency provenance is not computable, and provide dynamic and static approximation techniques. We also discuss preliminary implementation experience with using dependency provenance to compute data slices, or summaries of the parts of the input relevant to a given part of the output.
Original languageEnglish
Pages (from-to)1301-1337
Number of pages37
JournalMathematical Structures in Computer Science
Issue number6
Publication statusPublished - 2011


Dive into the research topics of 'Provenance as dependency analysis'. Together they form a unique fingerprint.

Cite this