SCIENCE@home

Provenance Traces

J. Cheney,Umut A. Acar,Amal Ahmed

Published 2008 in arXiv.org

ABSTRACT

Provenance is information about the origin, derivation, ow nership, or history of an object. It has recently been studied extensi v ly in scientific databases and other settings due to its importa nce in helping scientists judge data validity, quality and integr ity. However, most models of provenance have been stated as ad hoc defi nitions motivated by informal concepts such as “comes from”, “ influences”, “produces”, or “depends on”. These models lack clea r formalizations describing in what sense the definitions captur e these intuitive concepts. This makes it difficult to compare appro aches, evaluate their effectiveness, or argue about their validit y. We introduceprovenance traces , a general form of provenance for the nested relational calculus(NRC), a core database query language. Provenance traces can be thought of as concrete da ta structures representing the operational semantics deriva tion of a computation; they are related to the traces that have been us d in self-adjusting computation, but differ in important res p cts. We define a tracing operational semantics for NRC queries that p roduces both an ordinary result and a trace of the execution. We show that three pre-existing forms of provenance for the NRC can b e extracted from provenance traces. Moreover, traces satisf y two semantic guarantees: consistency , meaning that the traces describe what actually happened during execution, and fidelity, meaning that the traces “explain” how the expression would behave if the i nput were changed. These guarantees are much stronger than those contemplated for previous approaches to provenance; thus, pro venance traces provide a general semantic foundation for comparing and unifying models of provenance in databases.

PUBLICATION RECORD

  • Publication year

    2008

  • Venue

    arXiv.org

  • Publication date

    2008-12-02

  • Fields of study

    Computer Science

  • Identifiers
    arXiv 0812.0564
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-30 of 30 references · Page 1 of 1

CITED BY

Showing 1-22 of 22 citing papers · Page 1 of 1