Query evaluation by rewriting #
This file provides an alternative approach to evaluating queries on annotated databases:
instead of directly interpreting operators over annotated tuples, a query on T is
rewritten into a query on T ⊕ K that operates on plain tuples whose values encode
both data and provenance.
The rewriting implemented here realizes rules (R1)–(R5) from Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data.
A correctness proof that Query.rewriting agrees with Query.evaluateAnnotated is
fully formalized for rules (R1)–(R4): each operator is machine-checked end-to-end.
The Diff case splits into an unmatched_eq half (proved via the semijoin
identity Multiset.semijoin_proj_eq_filter, after bridging the
LinearOrder.toDecidableEq vs instDecidableEqSum mismatch on the inner dedup
via Query.rewriting_valid_diff_inner_dd_inst) and a matched_eq half (proved
via the keyed-projection semijoin Multiset.semijoin_keyed_proj_eq_filter, after
substituting the inner aggregation with the closed-form
Query.evaluate_agg_rewriting_eq). Both halves join on the data columns with
≐, SQL's IS NOT DISTINCT FROM: difference keys on values, two nulls being
one key, where NULL = NULL would be unknown and drop the row. Rule (R5) –
aggregation – is not part of this classical rewriting: it lives on the general syntax, in
Provenance.AggQueryGroupRewriting, where an aggregate output is a symbolic
token rather than a quotiented K-tensor.
References #
Equations
- One or more equations did not get rendered due to their size.
- (Query.Rel n s).rewriting hq_2 = Query.Rel (n + 1) s
- (Π ts q_2).rewriting hq_2 = (Π fun (k : Fin (n + 1)) => if h : ↑k < n then TermIn.castToAnnotatedTuple (ts ⟨↑k, h⟩) else #(Fin.last q_2.arity)) (q_2.rewriting ⋯)
- (σ φ q_2).rewriting hq_2 = σ φ.castToAnnotatedTuple (q_2.rewriting ⋯)
- (q₁ ⊎ q₂).rewriting hq_2 = (q₁.rewriting ⋯ ⊎ q₂.rewriting ⋯)
- (ε q_2).rewriting hq_2 = Query.ProvSum (fun (k : Fin n) => Fin.castLE ⋯ k) (#(Fin.last n)) (q_2.rewriting ⋯)
- (Query.ProvSum a a_1 a_2).rewriting hq_2 = False.elim hq_2
Instances For
Dependency graph
Helper lemmas for the Dedup case of rewriting_valid #
Helper lemmas for the Diff case of rewriting_valid #
Semijoin reduction. Given multisets r : Multiset α and s : Multiset β and
a key function g : α → β, with s Nodup, the projection-after-filter of the
cartesian product (keeping pairs whose g-image matches) coincides with filtering
r to those a whose g a belongs to s. This is the multiset version of the
relational semijoin and is the structural identity behind the unmatched_eq
half of the Diff-case rewriting correctness.
Dependency graph
Keyed-projection semijoin. Generalizes Multiset.semijoin_proj_eq_filter in two
directions: the right multiset is the image S.map val of a Nodup keyset S under a
value function val : β → γ, and the projection is an arbitrary mk : α → γ → δ rather
than Prod.fst. The compatibility hypothesis h_val asserts that key_s ∘ val is the
identity on S (i.e., val reconstructs an element whose key_s-image is the original
key). The semijoin then reduces to filtering r by key_r a ∈ S and projecting through
mk a (val (key_r a)) (the unique matching γ-value). This is the structural identity
behind the matched_eq half of the Diff-case rewriting correctness.
Dependency graph
The ProvSum of q.rewriting (the inner ⊕-gate creation used in both
the Dedup and Diff rewritings) evaluates to a map over the deduped
data-projection of the inner annotated relation, with each row paired (via
AnnotatedTuple.toComposite) with the semiring sum of the matching
annotations.
Dependency graph
Instance-polymorphic restatement of Query.rewriting_valid_diff_inner_dd.
Inside the Diff case of rewriting_valid, Lean's instance synthesis picks
inconsistent DecidableEq (T⊕K) instances at different positions in the goal:
the inner Multiset.dedup is elaborated with LinearOrder.toDecidableEq (via
ValueType (T⊕K)), while the surrounding Multiset.filter's decidableMem
uses instDecidableEqSum. This wrapper accepts both as explicit parameters and
bridges to the canonical helper via Subsingleton.elim.
Dependency graph
Correctness of the rewriting, rules (R1)–(R4): the annotated semantics of a source query, read as a plain relation with the annotation in the last column, is the plain semantics of the rewritten query on the composite database.
Registered in the Lax archive as
Lax392996.RewritingCorrectness.rewriting_valid.