While this submission is a draft, it cannot be used by other submissions.

Correctness of the provenance-aware rewriting, rules (R1) to (R4)

Lax392996.RewritingCorrectness · concepts/Lax392996/RewritingCorrectness.lean · lax-392996

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Let qq be a source query, K\mathbb{K} an m-semiring with decidable equality and an alternative linear order, I^\hat I a K\mathbb{K}-instance, and q^\hat q the query obtained from qq by applying the rewriting rules bottom up. Then ⟨ ⁣⟨q⟩ ⁣⟩I^=[ ⁣[q^] ⁣]I^\langle\!\langle q \rangle\!\rangle_{\hat I} = [\![\hat q]\!]_{\hat I}: the annotated semantics of qq on I^\hat I, read as a plain relation with the annotation in the last column, is the multiset semantics of q^\hat q on the composite reading of I^\hat I. This is the theorem of the paper restricted to rules (R1) to (R4): the paper's statement also covers the aggregation rule (R5), which this submission does not state; the library proves an analogue of it, on its general syntax with symbolic aggregate tokens, outside the paper's syntax.

    Concept map
    8 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    • page 5 of this submission's paper
    • page 17 of this submission's paper

    Lean source view on GitHub

    1import Lax392996.SemiringsWithMonus
    2import Lax392996.Databases
    3import Lax392996.AnnotatedDatabases
    4import Lax392996.RelationalAlgebra
    5import Lax392996.MultisetSemantics
    6import Lax392996.AnnotatedSemantics
    7import Lax392996.RewritingRules
    8
    9/-!
    10---
    11title: Correctness of the provenance-aware rewriting, rules (R1) to (R4)
    12type: theorem
    13---
    14Let qq be a source query, K\mathbb{K} an m-semiring with decidable
    15equality and an alternative linear order, I^\hat I a K\mathbb{K}-instance,
    16and q^\hat q the query obtained from qq by applying the rewriting rules
    17bottom up. Then ⟨ ⁣⟨q⟩ ⁣⟩I^=[ ⁣[q^] ⁣]I^\langle\!\langle q \rangle\!\rangle_{\hat I} = [\![\hat q]\!]_{\hat I}
    18: the annotated semantics of qq on I^\hat I, read as a plain
    19relation with the annotation in the last column, is the multiset semantics
    20of q^\hat q on the composite reading of I^\hat I. This is the theorem of the
    21paper restricted to rules (R1) to (R4): the paper's statement also covers
    22the aggregation rule (R5), which this submission does not state; the
    23library proves an analogue of it, on its general syntax with symbolic
    24aggregate tokens, outside the paper's syntax.
    25-/
    26
    27namespace Lax392996.RewritingCorrectness
    28
    29open Lax392996.SemiringsWithMonus Lax392996.Databases Lax392996.AnnotatedDatabases
    30open Lax392996.RelationalAlgebra Lax392996.MultisetSemantics Lax392996.AnnotatedSemantics
    31open Lax392996.RewritingRules
    32
    33/-- `⟪q⟫_Î = ⟦q̂⟧_Î`, for `q` in the fragment the rules (R1)–(R4) cover. -/
    34axiom rewriting_valid : ∀ {T : Type} [ValueType T] {K : Type} {n : ℕ}
    35 [SemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K]
    36 (q : Query T n) (hq : q.source) (d : AnnotatedDatabase T K),
    37 (Query.evaluateAnnotated q hq d).toComposite
    38 = Query.evaluate (Query.rewriting q hq) d.toComposite
    39
    40end Lax392996.RewritingCorrectness
    41
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…