Provenance as dependency analysis

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 seman...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical structures in computer science 2011-12, Vol.21 (6), p.1301-1337
Main Authors: CHENEY, JAMES, AHMED, AMAL, ACAR, UMUT A.
Format: Article
Language:English
Subjects:
Approximation
Computer programming
Computer science
Derivation
Foundations
Mathematical analysis
Mathematical models
Programming languages
Semantics
Tracking
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0960-1295
1469-8072
DOI:10.1017/S0960129511000211