The rewriting rules (R1)–(R4), natively on the general syntax #
The rewriting of Sen, Maniu & Senellart, ProvSQL
turns a query over annotated relations into an ordinary query over the
composite encoding: one extra column carries the annotation, of the
lifted value type T ⊕ K. With the three-kind discipline the rewriting
is expressible natively: the annotation column is marked prov
(ColKind.rewKinds), read back by TermGIn.provIndex terms, aggregated by
AggQueryIn.ProvSum (the ⊕-gate creation of ε and ∖), and the
value-kind bookkeeping is AggQueryIn.Retag – semantically the identity.
AggQueryIn.rewriting below mirrors the classical Query.rewriting
rule for rule on the classical fragment (AggQueryIn.classical) of the
general syntax. Its correctness against evaluateAnnotated is assembled
in stages, over the next two modules: the strip to the classical syntax
and its faithfulness (Provenance.AggQueryStrip), then the
plain-semantics agreement of the two rewritten queries and the
correctness theorem itself (Provenance.AggQueryRewritingValid).
This module holds the syntax of the rewriting: the target kind vector,
the classical fragment, the casts into the composite domain, and
AggQueryIn.rewriting.
The target kind vector #
The kind vector of a rewritten query: n data columns followed by
the provenance column.
Equations
- ColKind.rewKinds n k = if ↑k < n then ColKind.reg else ColKind.prov
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Retag any pointwise value-kinded query to the rewriting kinds.
Equations
- AggQueryIn.retagToRew h q = AggQueryIn.Retag ⋯ q
Instances For
Dependency graph
The classical fragment #
The classical (R1)–(R4) source fragment of the general syntax: no grouping, no provenance aggregation, no retagging, projections through regular terms only, selections without aggregate atoms.
Equations
- (AggQueryIn.Rel x✝ a).classical = True
- (AggQueryIn.Hole x✝¹ s x✝).classical = False
- (AggQueryIn.Param pv x✝).classical = False
- AggQueryIn.Empty.classical = True
- (AggQueryIn.Proj ps q).classical = ((∀ (j : Fin x✝¹), (ps j).kind = ColKind.reg) ∧ q.classical)
- (AggQueryIn.Sel φ q hφ).classical = (φ.hasAggAtom = false ∧ q.classical)
- (q₁.Prod q₂).classical = (q₁.classical ∧ q₂.classical)
- (q₁.Sum q₂).classical = (q₁.classical ∧ q₂.classical)
- q.Dedup.classical = q.classical
- (q₁.Diff q₂).classical = (q₁.classical ∧ q₂.classical)
- (a.Apply a_1).classical = False
- (AggQueryIn.Explode k a a_1).classical = False
- (AggQueryIn.Mu s a a_1).classical = False
- (AggQueryIn.MuSet s a a_1).classical = False
- (AggQueryIn.Gamma is ts fs a keep ord).classical = False
- (AggQueryIn.GammaScalar ts fs a ord).classical = False
- (AggQueryIn.GammaNest is his p f a).classical = False
- (AggQueryIn.ProvSum is his t a).classical = False
- (AggQueryIn.Retag h a).classical = False
- (AggQueryIn.GammaTok is his ts fs a a_1 keep).classical = False
- (AggQueryIn.Win P O o w t f a a_1 dist keep).classical = False
- (AggQueryIn.WinExpr P O o ws ts fs g a keeps).classical = False
Instances For
Dependency graph
Classical queries have all-regular kinds (pointwise).
Dependency graph
Casting terms, predicates and columns to the composite domain #
A term over all-regular columns, over the composite domain with its columns shifted into the data block of the rewritten schema.
Equations
- One or more equations did not get rendered due to their size.
- TermGIn.castComposite hκ (TermGIn.const a) = TermGIn.const (Sum.inl a)
- TermGIn.castComposite hκ (TermGIn.outer a) = TermGIn.const (Sum.inl 0)
- TermGIn.castComposite hκ (TermGIn.index k a) = TermGIn.index (Fin.castLE ⋯ k) ⋯
- TermGIn.castComposite hκ (TermGIn.provIndex k h) = absurd ⋯ ⋯
- TermGIn.castComposite hκ (TermGIn.cmpAgg k h a a_1) = absurd ⋯ ⋯
- TermGIn.castComposite hκ (TermGIn.chiGate a a_1 a_2) = TermGIn.const (Sum.inl 0)
- TermGIn.castComposite hκ (t₁.add t₂) = TermGIn.add (TermGIn.castComposite hκ t₁) (TermGIn.castComposite hκ t₂)
- TermGIn.castComposite hκ (t₁.sub t₂) = TermGIn.sub (TermGIn.castComposite hκ t₁) (TermGIn.castComposite hκ t₂)
- TermGIn.castComposite hκ (t₁.mul t₂) = TermGIn.mul (TermGIn.castComposite hκ t₁) (TermGIn.castComposite hκ t₂)
- TermGIn.castComposite hκ (t₁.coalesce t₂) = TermGIn.coalesce (TermGIn.castComposite hκ t₁) (TermGIn.castComposite hκ t₂)
Instances For
Dependency graph
An aggregate-atom-free predicate, over the composite domain.
Equations
- GenPredIn.castComposite hκ (GenPredIn.cmp op t₁ t₂) x_2 = GenPredIn.cmp op (TermGIn.castComposite hκ t₁) (TermGIn.castComposite hκ t₂)
- GenPredIn.castComposite hκ (GenPredIn.aggCmp k a a_1 a_2) hφ = Bool.noConfusion hφ
- GenPredIn.castComposite hκ (φ.and ψ) hφ = GenPredIn.and (GenPredIn.castComposite hκ φ ⋯) (GenPredIn.castComposite hκ ψ ⋯)
- GenPredIn.castComposite hκ (φ.or ψ) hφ = GenPredIn.or (GenPredIn.castComposite hκ φ ⋯) (GenPredIn.castComposite hκ ψ ⋯)
- GenPredIn.castComposite hκ φ.not hφ = GenPredIn.not (GenPredIn.castComposite hκ φ hφ)
Instances For
Dependency graph
A regular projection column, over the composite domain.
Equations
- ProjColIn.castComposite hκ (ProjColIn.term t) x_2 = ProjColIn.term (TermGIn.castComposite hκ t)
- ProjColIn.castComposite hκ (ProjColIn.token k a) hp = ColKind.noConfusion hp
- ProjColIn.castComposite hκ (ProjColIn.aggTerm k a a_1) hp = ColKind.noConfusion hp
- ProjColIn.castComposite hκ (ProjColIn.aggTermOf k a a_1) hp = ColKind.noConfusion hp
- ProjColIn.castComposite hκ (ProjColIn.provTerm a) hp = ColKind.noConfusion hp
Instances For
Dependency graph
Dependency graph
The rewriting #
The (R1)–(R4) rewriting, natively on the general syntax. Each
rule mirrors the classical Query.rewriting: the base relation exposes
its provenance column (R1), projections keep it verbatim (R2, key case),
selections filter the data columns (R2), joins multiply the two
provenance columns (R3), unions concatenate (R4, first case),
deduplication ⊕-sums the provenance per surviving tuple (R4, ε), and
difference combines the unmatched branch with the matched branch's
α ⊖ Σβ (R4, ∖).
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x_1 s).rewriting x_7 = AggQueryIn.retagToRew ⋯ (AggQueryIn.Rel (x_1 + 1) s)
- (AggQueryIn.Hole x_1 s x_2).rewriting hq = False.elim hq
- (AggQueryIn.Param pv x_2).rewriting hq = False.elim hq
- AggQueryIn.Empty.rewriting x_7 = AggQueryIn.retagToRew ⋯ (AggQueryIn.Proj (fun (x : Fin 1) => ProjColIn.term (TermGIn.const 0)) AggQueryIn.Empty)
- (AggQueryIn.Sel φ q hφ).rewriting hq = AggQueryIn.Sel (GenPredIn.castComposite ⋯ φ ⋯) (q.rewriting ⋯) ⋯
- (q₁.Sum q₂).rewriting hq = AggQueryIn.Sum (q₁.rewriting ⋯) (q₂.rewriting ⋯)
- q.Dedup.rewriting hq = AggQueryIn.retagToRew ⋯ (AggQueryIn.ProvSum (fun (k : Fin x_1) => Fin.castLE ⋯ k) ⋯ (TermGIn.provIndex (Fin.last x_1) ⋯) (q.rewriting hq))