nucleation

LIT-1104: Why and Where: A Characterization of Data Provenance

2 min read

Properties4
StatusActive — read in full 2026-10-15 (NOTE-920) from the authors' postprint in the University of Pennsylvania's ScholarlyCommons repository (repository.upenn.edu/handle/20.500.14332/6246, file k50.pdf, 15 pp., camera-ready text of October 2000 without LNCS page numbers), found through Unpaywall and OpenAlex (green, submittedVersion) and fetched through the repository's API because the landing page is script-only; the Edinburgh repository handle (hdl.handle.net/20.500.11820/46e660d2-8247-4d26-ae49-65fd1bf8364b) returned an error. Worth reading as the source of the distinction between why-provenance, a set of witnesses with one per derivation, and where-provenance, the location a value was copied from, and of the result that only the first can be made independent of how a positive query is written (minimal witness basis, for queries with equality conditions; where-provenance only for "traceable" queries; proofs omitted) (THEORY-367). For QUESTION-105 it shows that a minimal witness basis is a retained state that decides survival under deletion of source facts in set semantics, and that "provenance" names two structures of which only one is invariant; it covers no additions, no negation or aggregation, no strengths of support and no measure of how much is retained. For CLAIM-303 it shows that why-provenance can be recomputed on demand from the query and the source rather than filed; for CLAIM-306 it has nothing for absence, since both notions are defined only for what is in the output.
Tagsdatabases, logic
Cited as “paper” byNOTE-920 — Buneman, Khanna & Tan — Why and where: a characterization of data provenance
Cited as “source” byTHEORY-367 — For SPJU relational queries, which Buneman, Khanna and Tan's tree model encodes, the minimal witnesses of an output tuple, the inclusion-minimal sets of source facts from which the query still derives it, are the minimal sets matched by single derivations and so are the same for every equivalent query, while where-provenance, the source location a value was copied from, can differ between equivalent queries

Graph View

Buneman, P., Khanna, S. and Tan, W.-C. (2001). Why and where: a characterization of data provenance. In Database Theory — ICDT 2001, LNCS 1973, pp. 316–330. DOI 10.1007/3-540-44503-X_20

Key takeaways

Read in full (NOTE-920). The paper separates two meanings of the provenance of a piece of output data. Why-provenance is the witness basis: for each valuation of the query that produces the value, the part of the source the query’s patterns matched, one witness per derivation. Where-provenance is the location in the source a value was copied from. For a hierarchical data model and a query language that covers positive (SPJU) relational queries, the witness basis is preserved by the paper’s query rewriting, and the minimal witness basis is the same for equivalent queries with equality conditions, while where-provenance is not invariant over equivalent queries in general and is preserved by rewriting only for a restricted class it calls traceable. Proofs are omitted, and nothing covers negation, aggregation, updates or additions to the source.

Why this is here

QUESTION-105: why-provenance as a witness basis, one witness per derivation, and where-provenance as the location a value was copied from, for positive queries. The witness basis distinguishes derivations, which a single set of contributing inputs does not.

Backlinks