Documentation

Provenance.QueryRewriting

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 #

def Query.rewriting {T : Type} {n : ℕ} {K : Type} [ValueType T] (q : Query T n) (hq : q.source) :
Query (T ⊕ K) (n + 1)
Equations
Instances For
    Dependency graph

    Helper lemmas for the Dedup case of rewriting_valid #

    Helper lemmas for the Diff case of rewriting_valid #

    theorem Multiset.semijoin_proj_eq_filter {α : Type u_1} {β : Type u_2} [DecidableEq β] (r : Multiset α) (s : Multiset β) (g : α → β) (hs : s.Nodup) :
    map Prod.fst (filter (fun (pair : α × β) => g pair.1 = pair.2) (r.product s)) = filter (fun (a : α) => g a ∈ s) r

    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
    theorem Multiset.semijoin_keyed_proj_eq_filter {α : Type u_1} {γ : Type u_2} {δ : Type u_3} {β : Type u_4} [DecidableEq β] (r : Multiset α) (S : Multiset β) (val : β → γ) (key_r : α → β) (key_s : γ → β) (mk : α → γ → δ) (hS : S.Nodup) (h_val : ∀ v ∈ S, key_s (val v) = v) :
    map (fun (pair : α × γ) => mk pair.1 pair.2) (filter (fun (pair : α × γ) => key_r pair.1 = key_s pair.2) (r.product (map val S))) = map (fun (a : α) => mk a (val (key_r a))) (filter (fun (a : α) => key_r a ∈ S) r)

    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
    theorem Query.rewriting_valid_diff_inner_dd_inst {T K : Type} [ValueType T] [SemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} (AR₁ AR₂ : AnnotatedRelation T K n) (instA : DecidableEq (Tuple (T ⊕ K) n)) (instDP : DecidablePred fun (u : Tuple (T ⊕ K) n) => u ∉ Multiset.map (fun (u' : Tuple (T ⊕ K) (n + 1)) (k : Fin n) => u' (Fin.castLE ⋯ k)) AR₂.toComposite) :
    (Multiset.filter (fun (u : Tuple (T ⊕ K) n) => u ∉ Multiset.map (fun (u' : Tuple (T ⊕ K) (n + 1)) (k : Fin n) => u' (Fin.castLE ⋯ k)) AR₂.toComposite) (Multiset.map (fun (u' : Tuple (T ⊕ K) (n + 1)) (k : Fin n) => u' (Fin.castLE ⋯ k)) AR₁.toComposite)).dedup = Multiset.map (fun (v : Tuple T n) (k : Fin n) => Sum.inl (v k)) (Multiset.filter (fun (v : Tuple T n) => v ∉ Multiset.map Prod.fst AR₂) (Multiset.map Prod.fst AR₁)).dedup

    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.

    Dependency graph