nucleation

QUESTION-225: Are why-provenance and, for traceable queries, where-provenance preserved by Buneman, Khanna and Tan's rewrite system, and is traceability necessary for where-provenance to be preserved?

1 min read

Properties4
StatusOpen
Tagsdatabases, logic
Linenucleating-argument
RefinesQUESTION-105 — What is the least an evolving inquiry must retain, beyond its current conclusions and a closed belief set, which do not fix its revisions, to support a stated family of future revisions, and does the optimal retained state look like provenance, dependencies and defeated alternatives, or like something else?

Graph View

Why it is a question

Buneman, Khanna and Tan (2001) state that their rewrite system preserves the witness basis (Lemma 1), and that it preserves where-provenance for traceable queries (Proposition 2). The paper does not give the rules or the proofs, so the record cannot check either result. THEORY-367’s former title also said where-provenance is preserved “only” for traceable queries. The paper shows that traceable queries preserve it, not that queries outside the class fail to.

An answer is a read proof of Lemma 1 and Proposition 2 for a stated rewrite system, from a full or journal version. A further answer would be a non-traceable query and a rewriting that changes its where-provenance, or a proof that preservation needs traceability. For the revision question QUESTION-105 asks, the rewrite results matter less than the invariance THEORY-367 now holds. They decide whether a stored witness basis survives query optimisation.

Backlinks