Stripping the classical fragment to the classical syntax #
The classical fragment AggQueryIn.classical of the general syntax maps
back, operator for operator, to the classical Query syntax of
Provenance.Query. AggQueryIn.strip is that map, and
AggQueryIn.strip_bridge says it is faithful: the general annotated
evaluator and the classical one agree on it. The rewriting correctness
of Provenance.AggQueryRewritingValid goes through this bridge and the
classical theorem Query.rewriting_valid.
The strips of terms, predicates and projection columns send an outer
column to the constant 𝟘, which is what the valuation a closed query
reads gives it, so the agreement statements below hold as they stand.
Stripping to the classical syntax #
The classical fragment of the general syntax maps back to the classical
Query syntax; the correctness of the native rewriting is assembled
through this strip, the classical correctness theorem, and the
plain-semantics agreement of the two rewritten queries.
Strip a term over regular columns to a classical term (the
provIndex arm is unreachable on the classical fragment and mapped
harmlessly).
Equations
- (TermGIn.const a).strip = TermIn.const a
- (TermGIn.index k a).strip = #k
- (TermGIn.provIndex k a).strip = #k
- (TermGIn.cmpAgg k a a_1 a_2).strip = TermIn.const 0
- (TermGIn.chiGate a a_1 a_2).strip = TermIn.const 0
- (TermGIn.outer a).strip = TermIn.const 0
- (t₁.add t₂).strip = TermIn.add t₁.strip t₂.strip
- (t₁.sub t₂).strip = TermIn.sub t₁.strip t₂.strip
- (t₁.mul t₂).strip = TermIn.mul t₁.strip t₂.strip
- (TermGIn.caseWhen op t₁ t₂ t₃ t₄).strip = TermIn.caseWhen op t₁.strip t₂.strip t₃.strip t₄.strip
- (t₁.coalesce t₂).strip = TermIn.coalesce t₁.strip t₂.strip
Instances For
Dependency graph
Strip an aggregate-atom-free predicate to a classical selection.
Equations
- (GenPredIn.cmp CompOp.eq t₁ t₂).strip = Selection.BT (BoolTerm.EQ t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.ne t₁ t₂).strip = Selection.BT (BoolTerm.NE t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.le t₁ t₂).strip = Selection.BT (BoolTerm.LE t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.lt t₁ t₂).strip = Selection.BT (BoolTerm.LT t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.ge t₁ t₂).strip = Selection.BT (BoolTerm.GE t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.gt t₁ t₂).strip = Selection.BT (BoolTerm.GT t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.syneq t₁ t₂).strip = Selection.BT (BoolTerm.SYNEQ t₁.strip t₂.strip)
- (GenPredIn.cmp CompOp.synne t₁ t₂).strip = Selection.BT (BoolTerm.SYNNE t₁.strip t₂.strip)
- (GenPredIn.aggCmp k a a_1 a_2).strip = Selection.True
- (GenPredIn.aggRange k a a_1 a_2 a_3 a_4).strip = Selection.True
- (φ.and ψ).strip = φ.strip.And ψ.strip
- (φ.or ψ).strip = φ.strip.Or ψ.strip
- φ.not.strip = φ.strip.Not
Instances For
Dependency graph
Strip a regular projection column to a classical term.
Equations
- (ProjColIn.term t).strip = t.strip
- (ProjColIn.token k a).strip = TermIn.const 0
- (ProjColIn.aggTerm k a a_1).strip = TermIn.const 0
- (ProjColIn.aggTermOf k a a_1).strip = TermIn.const 0
- (ProjColIn.provTerm t).strip = t.strip
Instances For
Dependency graph
Strip a classical-fragment query to the classical syntax.
Equations
- (AggQueryIn.Rel x_1 s).strip x_7 = Query.Rel x_1 s
- (AggQueryIn.Hole x_1 s x_2).strip hq = False.elim hq
- (AggQueryIn.Param pv x_2).strip hq = False.elim hq
- AggQueryIn.Empty.strip x_7 = σ Selection.True.Not (Query.Rel 0 "")
- (AggQueryIn.Proj ps q).strip hq = (Π fun (j : Fin x_1) => (ps j).strip) (q.strip ⋯)
- (AggQueryIn.Sel φ q hφ).strip hq = σ φ.strip (q.strip ⋯)
- (q₁.Prod q₂).strip hq = (q₁.strip ⋯).Prod (q₂.strip ⋯)
- (q₁.Sum q₂).strip hq = (q₁.strip ⋯ ⊎ q₂.strip ⋯)
- q.Dedup.strip hq = ε (q.strip hq)
- (q₁.Diff q₂).strip hq = (q₁.strip ⋯ - q₂.strip ⋯)
- (AggQueryIn.Gamma is ts fs a keep ord).strip hq = False.elim hq
- (AggQueryIn.GammaScalar ts fs a ord).strip hq = False.elim hq
- (AggQueryIn.ProvSum is his t a).strip hq = False.elim hq
- (AggQueryIn.Retag h a).strip hq = False.elim hq
- (AggQueryIn.GammaTok is his ts fs a a_1 keep).strip hq = False.elim hq
- (AggQueryIn.Win P O o w t f a a_1 dist keep).strip hq = False.elim hq
Instances For
Dependency graph
The strip is aggregation-free.
Dependency graph
Faithfulness of the strip #
Faithfulness of the strip: on the classical fragment the general annotated evaluator computes the classical annotated semantics of the stripped query.